The Gateway to Computer Science Excellence
+2 votes
432 views

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. 

in Operating System by Veteran (105k points) | 432 views

2 Answers

+9 votes
Best answer

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. 

by Boss (26.5k points)
selected by
0

I think this can be solved using binary semaphores

Consider we have two binary semaphores S and T initialized to 1 and 0 respectively.

Since the maximum value of count is 1, it is clear that buffer is of size 1. So when the producer produces an item, it has to be consumed by the consumer before the producer can produce the next item.

Producer
repeat
P(S);
produce item and place it in buffer
V(T);

Consumer
P(T);
Consume item from buffer
V(S);

 

 

0
Can we preempt the process without completion of statement ';'    as per solution

 
@arjunsuresh  sir
 

 

Plz clear my doubt I wasted a lot time behind this
0
Anyone, please explain

how the consumer part is getting preempted?
0 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.

by Boss (43.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,597 answers
195,837 comments
102,134 users