GATE CSE 1999 | Question: 20-b

Question

Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations. 

Producer:      
Repeat 
    Produce an item;
    if count = 1 then sleep;
    place item in buffer.
    count = 1;
    Wakeup(Consumer);
Forever 

Consumer:
Repeat
    if count = 0 then sleep;
    Remove item from buffer;
    count = 0;
    Wakeup(Producer);
    Consume item;
Forever;

Show that in this solution it is possible that both the processes are sleeping at the same time. 

Answer 1

1. Run the Consumer Process, Test the condition inside "if" (It is given that the testing of count is atomic operation), and since the Count value is initially 0, condition becomes True. After Testing (But BEFORE "Sleep" executes in consumer process), Preempt the Consumer Process.  

2. Now Run Producer Process completely (All statements of Producer process). (Note that in Producer Process, 5th line of code, "Wakeup(Consumer);" will not cause anything because Consumer Process hasn't Slept yet (We had Preempted Consumer process before It could go to sleep). Now at the end of One pass of Producer process, Count value is now 1. So, Now if we again run Producer Process, "if" condition becomes true and Producer Process goes to sleep.

3. Now run the Preempted Consumer process, And It also Goes to Sleep. (Because it executes the Sleep code).

So, Now Both Processes are sleeping at the same time. 

Comments

best explanation

---

To note: if – then statement is not atomic.

---

I think this will work fine had the if-then were atomic too along with assignment.

Answer 2

Producer:      
Repeat 
    $P1$. Produce an item;
    $P2$. if count $= 1$ then sleep;
    $P3$. place item in buffer.
    $P4$. count $= 1$;
    $P5$. Wakeup(Consumer);
Forever

Consumer:
Repeat
    $C1$. if count $= 0$ then sleep;
    $C2$. Remove item from buffer;
    $C3$. count $= 0$;
   $C4$. Wakeup(Producer);
    $C5$. Consume item;
Forever;

Initially Count$=0$;

Producer starts first, and execute following steps:
$P1$
$P2$
$P3$

Producer preempts here.

Consumer executes the following step:
$C1$ and before it goes to sleep(waiting state) it got preempted.and went to ready state.

Producer resumes its execution
$P4$. set count $=1$
$P5$. wakeup(Consumer) but consumer is not actually blocked.
Producer preempts here.

Consumer Resumes its execution:
It completes second of half of the $C1$ and goes to sleep.

Producer resumes its execution, and executes
$P1$ 
$P2$ and Producer also goes to sleep.

Hence, Producer and Consumer both are sleeping.

Answer 3

• If any of producer and consumer was sleeping and got preempted .
• if  other one gave wakeup call to wake up the sleeping process .
• The the process giving wakeup call sleeps itself.  
• sleeping process was preempted so wake up call got wasted now after sleeping process was .again scheduled .
• it got back to sleeping state now both processes are in sleeping state.

This was the problem which Dijkstra found and semaphores were created to record the wakeup calls.

Answer 4

Best way to visualise Bounded Buffer problem

 

Comments

Say, Full = 0 and Empty = N [i.e. the buffer is empty and thus Producer should be able to produce]
Mutex = 1 [Initially]
Your code will block Producer at P(full), and Consumer will do --X, which should not be allowed as no item yet to consume.
Correction: Just swap the names {Producer and Consumer} and statements {X++ and X--}