search
Log In
2 votes
763 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 763 views

2 Answers

13 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. 


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?
1 vote


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.

Related questions

17 votes
5 answers
1
1.7k views
A certain processor provides a 'test and set' instruction that is used as follows: TSET register, flag This instruction atomically copies flag to register and sets flag to $1$. Give pseudo-code for implementing the entry and exit code to a critical region using this instruction.
asked Sep 24, 2014 in Operating System Kathleen 1.7k views
22 votes
4 answers
2
5.4k 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$
asked Sep 23, 2014 in Digital Logic Kathleen 5.4k views
24 votes
5 answers
3
4.5k 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 $25$ records) is: $165$ $90$ $75$ $65$
asked Sep 12, 2014 in Algorithms Keith Kr 4.5k views
32 votes
3 answers
4
5.7k views
A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $2^{16}$ bytes each. The virtual address space is divided into $8$ non-overlapping equal size segments. The ... are available in page table entry for storing the aging information for the page? Assume that the page size is $512$ bytes.
asked Sep 24, 2014 in Operating System Kathleen 5.7k views
...