The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1k 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 in Operating System by Veteran (59.5k points)
edited by | 1k views
0
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.
0
why did you removed part b

4 Answers

+9 votes
Best answer

(A)

  1. TSET $R1$, flag
  2. CMP $R1, \#0$
  3. JNZ Step$1$
  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 Boss (39.8k points)
edited by
0
count value neither increment , nor getting decremented . That is the main problem here.and assignment not changing
0
How can this problem be rectified?
+1
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
0

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

0

Correct implementation of critical section includes:

  • Mutual Exclusion
  • Progress
  • Bounded Waiting

Although, Mutual Exclusion and Progress is guaranteed in above solution but there is no bounded waiting.

0

Ayush Upadhyaya @srestha if testing the count is an atomic operation then how come - in consumer's if condition, how preemption is happening?

 

if count =0 ||preemption||  then sleep;

+1

what do u mean by atomic operation?

here is part b of the question

https://gateoverflow.in/205817/gate1999-20-b

0

https://gateoverflow.in/205817/gate1999-20-b

This link made sense, Ma'am! Thank you! :)

+13 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 (625 points)
edited by
0
can't understand the logic.... plz help
0
@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?
0

shraddha priya 

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.

+4

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.

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?

0
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?
0
@ Hemant Parihar, Don't you feel L2 will always be false?
0
@churchill khangar Yes you are correct. I correct it now check it :) .
+1

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 :)

0
how does producer went into sleep? can you explain it a bit?
0

@Anshul Shankar because when Producer runs again and it has made count ==1 in previous execution. 

So, Producer runs line P1 okay

then in line P2 if (count=1) then sleep; and yes count = 1 

Hence if (1==1) is True and producer goes to sleep!

+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 Boss (31.4k points)
0
In part b in the question, it is said that, "
Also assume that the testing of count and assignment to count are atomic operations". Can you please explain, what does this statement means?    Thank you.......
0
+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)

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

38,079 questions
45,572 answers
132,067 comments
49,042 users