The Producer Consumer Problem - RT
The Producer Consumer Problem - RT
The Producer Consumer Problem - RT
General Situation: One or more producers are generating data and placing these in a buffer A single consumer is taking items out of the buffer one at time Only one producer or consumer may access the buffer at any one time The Problem: Ensure that the Producer cant add data into full buffer and consumer cant remove data from empty buffer Assume an infinite buffer b with a linear array of elements
Producer/Consumer Problem
Producer :
Consumer :
Incorrect Solution
Instead of indices in and out, we can simply keep track of the number of items in the buffer, using the integer variable n = in out; The semaphore s is used to enforce mutual exclusion and is initialized to 1; The semaphore delay is used to block the consumer if buffer is empty, and is initialized to 0.
Incorrect Solution
The concurrent execution of producer and consumer processes continues in their while(true) loops.
Thus, the first semWaitB(delay) in consumer process executes only when consumer executes for the first time . This decrements delay if it was one, i.e., if producer has placed the first item in the buffer. Then the consumer executes.
OR, it blocks the consumer if delay was zero, i.e., if consumer tries to access the buffer at the very beginning, before producer adds an item to the buffer
Purti R. Savardekar, Operating Systems, BE ETC, Sem VII, 2013.
Incorrect Solution
if(n==1)semSignalB(delay) is used to either increment the value of delay or unblock the consumer.
If producer is the first to access the buffer at the very beginning, it increments delay to 1 so that when consumer consumes for the first time, semWait(delay) decrements delay to 0 and continues its while(true). Then onwards, delay never becomes 1. Thus, if(n==0)semWaitB (delay) only blocks consumer if buffer is empty, and if(n==1)semSignalB(delay) only unblocks the consumer if buffer has one item in it.
Purti R. Savardekar, Operating Systems, BE ETC, Sem VII, 2013.
Consider a scenario where the order of execution is : Produce, Consume, Produce, Consume, Consume And, in line 10, the producer takes over before consumer is blocked, adds an element to the buffer, thus n=1, and in line 12, instead of unblocking the consumer, it increments the value of delay to 1! In line 14, the consumer gets a chance to continue its execution, and starts where it had left off. But now, if(n==0)semWaitB(delay) cannot be executed since n0. The consumer consumes the last added item (n=0), and then semWait finds delay = 1!!(instead of 0) Thus, delay is decremented to 0!!(instead of blocking the consumer since n=0)
Since the consumer is not blocked it tries to consume from an empty buffer!! <= Flaw It would not do simply to move the conditional statement inside the critical section of the consumer because this could lead to deadlock (e.g., after line 8) blocking the consumer would not allow semSignal(s) to execute, the Purti R. Savardekar, Operating Systems, blocking the producer!
BE ETC, Sem VII, 2013.
Correct Solution
A Solution to the Infinite Buffer Producer / Consumer Problem Using General or Counting Semaphores
A somewhat cleaner solution can be obtained if general semaphores or counting semaphores are used The variable n is semaphore. now a
The semaphore includes a new integer component, s.flag, a form of busy waiting. But since semWait and semSignal are relatively short, the amount of busy Purti R. Savardekar, Operating Systems, waiting is minor. BE ETC, Sem VII, 2013.