+13 votes
803 views

(a) 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.

(b) 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.

asked
edited | 803 views
option B shows the disadvantages of using sleep() and wait() calls as wakeups can't be saved for the future use. And thus we go for the semaphores.

## 4 Answers

+7 votes
Best answer

(A)
1. TSET R1, flag
2. CMP R1, #0
3. JNZ Step1
4. [CS]
5.Store M[Flag], #0

(B)
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.

answered by Veteran (43.6k points)
edited
count value neither increment , nor getting decremented . That is the main problem here.and assignment not changing
How can this problem be rectified?
Other sequence of deadlock :

C1:- checks if count==0,it is true, then preempt(remember sleep is still pending)

Producer comes,completes one iteration ( wakeup called by producer is lost as consumer is not sleeping as of now)

Produces comes again,P1 and p2 and goto sleep

Consumer resumes execution => goto sleep

afte p2 has also gone to sleeping state ... then can't it be possible that another consumer say p2 comes and wakes p2 from the sleeping state??

+12 votes

Q-2)

for consumer part

if (count==0)

consumer understands that buffer is full,But before consumer going  to sleep It got preempted and went to the Ready Queue

when producer produce an item and make Count=1,it will think consumer is blocked and try to wake up the consumer.

But actually Consumer is not Blocked it is in ready queue

After Some time Consumer come and Go to sleep[as before preemption it had seen that buffer is empty]

producer think that he has woken up consumer  and consumer is busy in consuming its produced item and consumer is waitinng for producer wakeup call

After sometime when buffer is full,producer went to sleep  thinking that when buffer is empty consumer will wake him up .And consumer is still waiting for producer wakeup call

So now Both are sleeping nd deadlock happens.

After some

answered by Junior (693 points)
edited by
can't understand the logic.... plz help
@bikram sir, In the above ans,
"for consumer part

if (count==0)

consumer understands that buffer is full,But before consumer going  to sleep It got preempted and went to the Ready Queue"

Can we preempt a process after checking the if condition and not executing the then part? If so, how? Aren't they a single line of code, so how can preemption occur in between?

when buffer is empty consumer reads count value =0  at that moment scheduler stops consumer temporarily and start producer process . [ in a full buffer you can not add anything more so you have to stop ]

So that means consumer is pre empted and taken to the ready queue.

Part A.
The flag is initialized to 0.

Flag == 0 means you are free to go into CS.
Flag == 1 means someone is in CS.

Entry Section

L1: Test register, Flag
L2: If (register != 0)
L3         goto L1

CS

Exit Section

Flag == 0.

in consumer section if count==0 then it means there is nothing to be consumed(consumer  understand buffer is empty) so it will go to sleep

but in selected answer explanation

if (count==0)

consumer understands that buffer is full

is that wrong explanation ?

correct me if i am wrong?

can i do like , producer produce item and then preempt (before making count =1), and now consumer try to consume item but as count =0 , he will go to sleep , and producer come back and excute the remaining part(noe count=1) , and again try to produce other item it will go to sleep as count =1 , so both will be in sleeping state .. it this correct?
@ Hemant Parihar, Don't you feel L2 will always be false?
@churchill khangar Yes you are correct. I correct it now check it :) .

Actually in B) code is working like this

-------------------------------------------------------------------------------

At first producer and consumer both are active state

Now, initially count =0

So, Say consumer active this part of code

if count = 0

And stop now

And producer starts and executes this part

place item in buffer.
count = 1;
Wakeup(Consumer);

Now producer goes to sleep

Consumer active now execute next part of it's code

 then sleep;
Remove item from buffer;
count = 0;
Wakeup(Producer);
Consume item;

So, at first it get instruction for sleep and it also goes to sleep

Both are in sleep mode now :)

how does producer went into sleep? can you explain it a bit?
+3 votes
part b) Initially when buffer is empty consumer reads count value =0  at that instant scheduler stops consumer temporarily and start producer process..Producer after inserting item finds count=1 and goes to sleep...Wakeup call of producer is lost and consumer finds count value =0 and go to sleep...so both are sleeping at same time
answered by Veteran (34.3k points)
+2 votes

Q1. ENTRY SECTION (Assuming flag is set to 0 initially before any process entered critical section)

while(register!=0)
Test(register, flag);

EXIT SECTION

f=0;

answered by Active (2.1k points)

+16 votes
1 answer
1
+27 votes
2 answers
2
+17 votes
2 answers
3