search
Log In
17 votes
1.9k 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.

in Operating System
edited by
1.9k 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
1

The question is incomplete. Please do complete it...

https://www.geeksforgeeks.org/gate-gate-cs-1999-question-68/

6 Answers

14 votes
 
Best answer

 

  1. TSET $R1$, flag
  2. CMP $R1, \#0$
  3. JNZ Step$1$
  4. $[CS]$
  5. Store $M[Flag], \#0

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

0

iarnav The testing part is "if count=0"(or "if count=1") not "if count then sleep".  

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


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

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.

1

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

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

0 votes

Solution:-

0 votes

I think this is solution...please comment if something is wrong

Related questions

3 votes
2 answers
1
979 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 = ... Producer); Consume item; Forever; Show that in this solution it is possible that both the processes are sleeping at the same time.
asked Feb 28, 2018 in Operating System jothee 979 views
23 votes
4 answers
2
6.1k 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 6.1k views
25 votes
5 answers
3
5.1k 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 5.1k views
34 votes
3 answers
4
6.5k 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 6.5k views
...