Q1 Study of The Producer-Consumer Problem (Bounded Buffer Problem)(i) Using pseudo code to represent the problem;(ii) Provides a solution using semaphore;(iii) Provides a solution using monitor;
(i) Description of the problem
. Two processes share a common, fixed-size buffer
. One process, the producer, puts data into the buffer, the other process, the consumer, takes it out.
. When producer wants to put a datum into the buffer, but it is full, producer goes to sleep, to be awakened when the consumer removes one or more data.
. When consumer wants to remove a datum from the buffer, when the buffer is empty, consumer goes to sleep, until producer put one datum into the buffer.
nRepresentation of the producer-consumer problem
. count = variable, to keep track of the number of data in buffer
N = maximum number of data number the buffer can hold
. consumer test count,
either count = 0 , go to sleep
or count = count -1
. each process tests if the other process should be sleeping, if not, wakes it up
. SLEEP and WAKEUP are system call for process manipulation
. enter_data and remove_data are procedures for putting and taking data in and out of the buffer
Code representing the Producer-consumer problem :
#include “prototypes.h”
#define N 100 /* number of slots in the buffer */
int count = 0; /* number of data items in buffer */
void producer (void)
{
int data;
while (TRUE) { /* repeat forever */
data = produce_data(); /* generate next data */
if (count == N) sleep(); /* if buffer is full, go to sleep */
enter_data(data); /* put data in buffer */
count ++; /* increment count of data number in buffer */
if (count == 1) wakeup(consumer); /* buffer not empty now and can be consumed now, notify consumer…*/
}
}
void consumer(void)
{
int data;
while (TRUE) { /* repeat forever */
if (count == 0) sleep(); /* if buffer is empty, go to sleep */
data = remove_data(); /* take data out of buffer */
count --; /* decrement count of data number in buffer */
if (count == N -1) wakeup(producer); /* buffer becomes not full and can be put more data, should notify producer */
consume_data(data); /* print data */
}
}
. Race Condition can occur executing the above code :
count++ could be implemented as
register1 = count
register1 = register1 + 1
count = register1
count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
(ii) Semaphores
. Semaphore is an integer variable
. When semaphore = 0, no resource is available
when semaphore > 0, # of resource abailable
. Semaphore can be operated in two operations ( Wait, Signal) :
Wait (sleep)
(i) checks to see if the semaphore value > 0 or = 0
(ii) if semaphore > 0, decrement the value, process execute critical section…,
if semaphore = 0, process put to sleep
Signal (wakeup)
(i) increment semaphore by 1
(ii) one of the sleeping process is awaken
. Wait () and Signal () operations are all done as a single, indivisible atomic action
. Signal and Wait are implemented as system calls; interrupts are disabled during execution to ensure atomic action ( protected by a lock variable mutex if necessary, as mutual exclusion)
The producer-consumer problem using semaphore
. Three semaphores are used :
full - counting the number of slots that are full.
empty - counting the number of slots that are empty.
The full and empty semaphores ensure that producer stops running when the buffer is full, consumer stops running when it is empty.
mutex - to make sure consumer and producer do no access the buffer at the same time.
mutex = 0 , no process can operate on semaphore ;
mutex = 1, process can perform Signal or Wait.
. Initially :
full = 0
empty = number of slot in the buffer.
mutex = 1 (can only take 1 or 0 - binary semaphore).
. Each process does a Wait before entering its critical region,
a Signal after leaving the critical region.
#include “prototypes.h”
#define N 100 /* number of slots in the buffer */
typedef int semaphore; /* semaphores are a special kind of int */
semaphore mutex = 1; /* controls access to critical region */
semaphore empty = N; /* counts empty buffer slots */
semaphore full = 0; /* counts full buffer slots */
void producer(void)
{
int data;
while (TRUE) { /* TRUE is the constant 1 */
data = produce_data(); /* generate data to put in buffer */
Wait(&empty); /* decrement empty count */
Wait(&mutex); /* enter critical region */
enter_data(data); /* put new data in buffer */
Signal(&mutex); /* leave critical region */
Signal(&full); /* increment count of full slots */
}
}
void consumer(void)
{
int data;
while (TRUE) { /* infinite loop */
Wait(&full); /* decrement full count */
Wait(&mutex); /* enter critical region */
data = remove_data(); /* take data from buffer */
Signal(&mutex); /* leave critical region */
Signal(&empty); /* increment count of empty slots */
consume_data(data); /* do something with the data */
}
}
(iii) Monitors
. monitor - a collection of procedures, variables and data structures in a package
. only one process can be active in a monitor at any instant
. compiler knows they are special monitor procedures (different from other procedure calls) and ensure only one process allows in the monitor, otherwise the calling process will be suspended until other process has left (mutual exclusion).
. Example of a monitor :
monitor example
integer i;
condition c;
procedure producer(x);
…
…
end;
procedure consumer(x);
…
…
end;
end monitor;
. A way for process to block when they cannot proceed - condition variables and operations WAIT and SIGNAL
When a monitor procedure finds that it cannot continue (such as for producer finds the buffer is full), it WAIT on the condition variable, full. The calling process will block itself, allowing another process (previously been blocked) to enter monitor
When a process (such as the consumer) wake up other sleeping process by doing a SIGNAL on the condition variable that other process is waiting on and must exited from the monitor immediately. SIGNAL must appear as the last statement (before exit) in a monitor.
The WAIT must come before the SIGNAL
Solution for the producer-consumer problem using monitor :
monitor ProducerConsumer
condition full, empty;
integer count, N;
function enter(data:integer);
begin
if count = N then wait(full);
enter_data(data);
count := count + 1;
if count = 1 then signal(empty)
end;
function remove(data:integer);
begin
if count = 0 then wait(empty);
data = remove_data;
count := count - 1;
if count = N - 1 then signal(full)
end;
count := 0;
end monitor;
procedure producer;
begin
while true do
begin
data = produce_data;
ProducerConsumer.enter(data)
end
end;
procedure consumer;
begin
while true do
begin
ProducerConsumer.remove;
consume_data(data)
end
end;
. monitors are a programming language concept and monitor procedures must be recognised by compiler to enforce mutual exclusion.
沒有留言:
張貼留言