3,424 views
11 votes
11 votes

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. 

4 Answers

Best answer
37 votes
37 votes

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. 

selected by
3 votes
3 votes


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.

0 votes
0 votes
  • 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.

edited by
0 votes
0 votes

Best way to visualise Bounded Buffer problem

 

Related questions

21 votes
21 votes
6 answers
1
29 votes
29 votes
4 answers
3
Kathleen asked Sep 23, 2014
13,187 views
Booth's coding in $8$ bits for the decimal number $-57$ is:$0-100+1000$$0-100+100-1$$0-1+100-10+1$$00-10+100-1$
35 votes
35 votes
4 answers
4
Keith Kr asked Sep 12, 2014
14,385 views
The minimum number of record movements required to merge five files A (with $10$ records), B (with $20$ records), C (with $15$ records), D (with $5$ records) and E (with ...