GATE CSE 2006 | Question: 61

Question

The atomic fetch-and-set $x, y$ instruction unconditionally sets the memory location $x$ to $1$ and fetches the old value of $x$ in $y$ without allowing any intervening access to the memory location $x$. Consider the following implementation of $P$ and $V$ functions on a binary semaphore $S$.

void P (binary_semaphore *s) { 
    unsigned y; 
    unsigned *x = &(s->value); 
    do { 
        fetch-and-set x, y; 
    } while (y); 
}

void V (binary_semaphore *s) { 
    S->value = 0; 
} 

Which one of the following is true? 

• A. The implementation may not work if context switching is disabled in $P$ 
• B. Instead of using fetch-and –set, a pair of normal load/store can be used 
• C. The implementation of $V$ is wrong
• D. The code does not implement a binary semaphore

Comments

How mutual exclusion is provided here. if another process implements v opreation first it will set the s value to 0 then if tries to execute the p operation it will enter into C.S even when there's another process inside it

---

well explained. I understood that why other options are wrong.

But I have one question from another perspective: How would Context switch have helped the processes?

What is the intention behind asking about the Context Switch here?

---

There are two right answers of this question

Of course A is right and so many others have already given reason for that.

Option D is also right because with this implementation of semaphore it satisfies the mutual exclusion but ,Bounded Wait will not be satisfied. Say P1 has successful DOWN and P2 and P3 are waiting in that order (P2 call DOWN before P3) , then when P1 will call UP, there is no guarantee that P2 will wake up before P3. thus if we use this semaphore implementation the solution will suffer from bounded wait and synchronization purpose will not achieve.

Answer 1

• A. :- This is correct because the implementation may not work if context switching is disabled in $P$ , then process which is currently blocked may never give control to the process which might eventually execute $V$. So Context switching is must !
   
• B. If we use normal load & Store instead of Fetch & Set there is good chance that more than one Process sees S.value as $0$ & then mutual exclusion wont be satisfied. So this option is wrong.
   
• C.  Here we are setting $S \rightarrow $ value to $0$, which is correct. (As in fetch & Set we wait if value of $S \rightarrow $ value is $1$. So implementation is correct. This option is wrong.
   
• D. I don't see why this code does not implement binary semaphore, only one Process can be in critical section here at a time. So this is binary semaphore & Option (D) is wrong
   

Comments

@Akash How can you answer without the value of y. Fetch and Set instruction sets x=1 but what about y?

@Arjun Suresh : Please help on this ?

---

Basic doubt- P succeeds only when the semaphore value is 1.
V does not change the semaphore value when it is 1?
Is it necessary ?
If some sempahore performed P on value 0 and reverse for signal - will it still be a valid semaphore ?

 As in this ques If s= 1 the P continues in while loop ..... as y is set to 1 so it is waiting even when semaphore value is 1 which as per the definition should have succeeded .................similarly if S= 0 then it succeeds ie condition in while loop is false ...........so as per me ans will be ( d) - but every where I'm seeing ans as (A)

My basic question is just about whether we can be flexible regarding values of binary semaphore ?

---

This question is about the definition of the semaphore. If we take 'initial' value s=1, then the semaphore should allow only one process to execute and the rest processes should wait. If we take 'initial' value s=0, then it means that some other process is executing the critical section and so the current process should wait. We see that if s=0, then the process will have to wait, until V() set the value to s=1, where the semaphore is available. One process out of many (if many waiting) will execute the fetch-and-set instruction and will come out of the while loop. Also, the process, which has finished executing the critical section should call V() set the value to s=1, otherwise no progress will hold. Again, this will be in implementation, here the definition is given only.

---

well explained bro

---

how you are saying that load and store can be used for preparing wait() and signal() instructions in order to conclude that they cannot be used at all. In fact I don't find anything in the books about load and store instructions. What I found by quick googling is that they simply load and store register with either a constant or address. (Plus that these instructions have some variants) However nothing talks about them in the context of Operating Systems concurrency control.

---

@Aspirant There is no need to look at what those instructions does. Only this that matters is load (reading value), and store (storing value) are two separate operations. This should be clear when we read about fetch-and-set instruction, because here read and set happens together -- in between read and write, there can be no other read.

---

P(s) is used to decrease value and  V(s) is used to increase key.So why option D is wrong ???

---

I think the implementation of V is wrong as V is supposed to make the value of S 1 and not 0, so C could also be an answer ?

@arjun sir, @Habibkhan

---

Well according to fetch and set , 

S = 0 , to release the lock and 

S = 1, to acquire the lock 

that's why its named Fetch and Set.

---

@indrajeet, the vaue of S always remain either 0 or 1 , its the def. of binary semaphore

 

this question can be better understood if we use slection by elimination

---

If context switching is disabled then can there be two active processes at the same time?

---

@rakesh

generally it is not possible

---

@Wanted then the explanation of the selected answer is not correct since it assumes that there will be two active processes at a time and one is waiting for the other.

---

@rakesh

i also want to say that until a process is not completed it is not possible to interrupt that , save its state and load other due to disabling of context switching.

---

I think the correct option is d.

@Arjun sir, plaese take a look at my explanation provided at the bottom section.

---

If the value of Binary Semaphore S=0 then no one should ever be allowed to enter CS. But if here if S=0  initially i.e S->Value=0

void P (binary_semaphore *s)

{

unsigned y;

unsigned *x = &(s->value);

do {

fetch-and-set x, y;    // now x=1 and y=0;

} while (y); //as y=0 so we will come out of while loop and proced to execute CS Hence it is not implementing Binary Semaphore correctly

}

---

@akb1115

But how you say S = 0 always ?

S = 1 also possible here .

the value of S always remain either 0 or 1 in this code snippet as no S value is given so option D can be wrong.

---

Sir when we do

 unsigned *x = &(s->value); // it means x is holding the address of S->Value

 After that, if we do "fetch-and-set x, y"   then the old value of X i.e address of S->value is copied to Y or the  S->value pointed by X is copied to Y 

---

@akb1115

S can be 0 or 1 ..both so it is also possible that option D can be false ..it is implementation dependent .

---

does context switching means here pre emption?

---

Yes, @subhanshu , here context switch means pre-emption of a process.

But there is a difference between context switch and preemption, theoratically.

Pre-emption means there must be context switch but context switch does not  mean there is preemption always.

Context Switch is the consequence of preemption but reverse is not true.

---

@Bikram Sir, Suppose we have two processes P1 and P2 .

Now suppose p1 execute first and set the value of S as 1 and enter into CS, after that p2 came and execute the statement "fetch and set" and set the value of S as 1 again and set the value of local y as 1, then this y will be check into WHILE LOOP, (results true )continously and by the statement "CONTEXT SWITCH IS DISABLED" the process p2will continously executing "fetch and set", bcz of while is true due to which no other process get the access of S and on the other side process p1 also unable to do its work in CS becz CPU is busy in p2.

ryt Sir??

---

@ Shubhanshu 

Yes, right .

It is one way implementation.. where s =1 .

s = 0 also possible..

you should read all above comments.

---

Thanks @Bikram Sir,
this implementation seems slightly reverse of actual semaphore as In actual semaphore on P operation value of S is decrease by one but here it is incresed by one moreover the value after V operation is incresed by one when it is zero but here it is directly set to zero.
ryt?

---

yes, it is modified semaphore implementation.

They modify that and add some constraints.

---

@Bikram sir

sir in V we increment the semaphore...then why it is setting s value to 0.

pls suggest me some source to make good understanding of this topic...coz i m really confused.

---

@ shefali1

First of all before asking any question please read all comments.

It is modified semaphore implementation.

In actual semaphore,  on P operation ( down) value of S is decrease by one ....... but here it is increased by one moreover the value after V operation ( up)  is increased by one when it is zero ..... but here it is directly set to zero.

see this line:

S->value = 0;  // the value of s is equal to 0 

---

yes sir i got it..thnku

---

@ Bikram sir but for one of the cases where s=0 its failing to be the implementation of binary semapohore instead i think this is the implementation of TSL with lock value is 's' when s=1 then all the processes that read this value will remain in infinite loop and when its made 0 by the process the finishes the CS and does an up operation then one of the process which then executes the critical section i think option d should also be considered .. as its not perfectly correct

---

@Bikram sir I am not getting the point let's assume a process A has executed P() with S=1 then went to infinite loop ie busy waiting.....now some other process B executed V and made S=0 ,now how does this Ensure that A will come out of busy waiting or its blocked state(it is executing while loop  continuously)?

---

@Akash, If the context switch is enabled also and the case is that after fetch-and-set instruction previous process is being blocked then is it possible that the new process will enter into critical section?

or, an unambiguous question-> Does it provide progress? 

If it would have been the case that the prev process is being blocked before the fetch-and-set instruction then enabling context switching would have helped considerably.

Correct me if I am wrong.

---

Hi Sir,
Correct me if I'm wrong..suppose there are n processes and 1 of them is in CS right now.Suppose all n-1 processes now try their luck one after the other and stay blocked(like in round robin manner).So there will be a moment when value of x will overflow in TSL and will become 0(since type of x is unsigned) and then next process will execute TSL and will return 0 and makes y=0; makes x =1. So suppose that process is Pn while P1 is still in CS...won't this lead to incorrect implementation of binary semaphore??

---

If context switch is disabled, then how p1 gets preempted when it is in  CS? It Only gets preempted after making s->value =0

then p2 can again read y=0 and writes x=1 and again  preemits only after full execution ( making s->value =0

---

In a binary semaphore there is a waiting queue associated with each semaphore.
how is that implemented?

---

Answer to my question:

there are 2 approaches for semaphore:
classical approach with busy waiting
new approach with sleep() and wake up().
here in the question they are using the classical approach.

---

Can someone tell me why LOAD STORE operations are not atomic here??

---

This is a type of implementation of Test and Set Lock variable in which the lock variable is loaded and it’s value is changed to 1 in a single line of code and the initial value of the lock variable is stored in another variable(here y). This was an advancement from the basic Lock Variable Synchronization mechanism.

Now, coming on to the question.

Option B : Wrong. As the reason is already stated above, a pair of normal load/store isn’t a better option.

Option C : Wrong. Because, V() will set the Binary Semaphore to 0( this means critical section is vacant and can be occupied)

Option D : Obviously Wrong. Reason being, the option C is wrong that means if C was correct then D had to be correct, but since it is a MCQ type question. Hence, implementation is appropriate.

Therefore, Option (A) is the correct option.

---

I think the justification of option B is not accurate because operation wait and signal are completely atomic, so there are no chances of executing wait() by two processes simultaneously.

correct justification should be "even if wait() uses normal load/store, the implementation may not work if preemption is not allowed”

am i right?

---

@Arjun sir,

When P1 is in busy waiting and context switch occurs then another process P2 will signal semaphore value(i.e 0).

My doubt is P1 is in while loop then how  value will be stored in x (after signal  by V) will get updated to 0 after context switch to P1 ?

 

---

@Arjun Sir,let say semaphore=0 initially. what if process P1 executes x=s->value and then preempts to P2 which reads x again as 0. Now both process can enter critical section simultaneously. How this obeying Mutual Exclusion?

---

No you are missing something (Maybe you have assumed Critical Section as Do-while Loop which is not). ME will be satisfied. Lets say P1 has x1 which reads s.value=0 and it prempts and P2 has x2 which also reads same s.vaue=0. Now if P2 decide to execute do while loop see what happens x2 will update s.value to 1 and store y=0 and while(y==0) i.e false will enter CS now if P1 comes x1 will update s.value=1 and store y=1 and while(y==1) i.e true it will do looping and not enter CS. Therefore ME is satisfied.

---

So, if I am not mistaken, there are two implementations of \(P\) and \(V\) operations on a semaphore (according to the book of Galvin):-

1. A spinlock/busy waiting implementation,
2. Another that (possibly) blocks the process, and put the process PCB on a queue

\((1)\) bothers only with mutual-exclusion, whereas \((2)\) enforces a FIFO ordering on the blocked processes, so it bothers with both mutual exclusion and bounded waiting.

Given any arbitrary scenario, which of the above implementations should one assume by default? 

Answer 2

CASE 1 : If initial value of s=0

then the fetch & set operation will make it 1 & one process will enter into critical section. Now if any other process will try to enter in to CS it will stuck into while loop as y=1.

When the process leave the CS, it will make the value of S to 0 which will give chance to other process to execute CS. Here, the thing to be noted is P() incrementing the value of semaphore & V() decrementing the value of semaphore variable. so this is reverse implementation of P & V. but they are working fine. so Option C & D is wrong.

CASE 2 : If initial value of S= 1

then every process will stuck into while loop & no process will be able to execute CS, so here we require some other process to come & execute v() which require context switching. If context switching is disabled then any process try to enter in CS will stuck into loop. so option A is correct.

Option B : If load & store is used & taking preemption into consideration(these are not atomic operation so preemption may occur) mutual exclusion can be dissatisfied.

 

Answer 3

It is kind of TSL instruction. Someone correct me if I am wrong.

The key point of this question is "The atomic fetch-and-set x,y instruction sets the memory location x to 1 and the old value of x into y". It means following (understand the code snippet first) 

CODE SNIPPET:

void P (binary_semaphore *s) {
    unsigned y;
    unsigned *x = &(s->value);
    do {
        fetch-and-set x, y;
    } while (y);
}

void V (binary_semaphore *s) {
    S->value = 0;
} 

UNDERSTAND HERE IN FOLLOWING STEPS:

1. Suppose s.value==0 initially. and &(s->value)==100. 

2. unsigned *x=&(s->value) will assign 100 to x.

3.  fetch-and-set x,y;     <- this statement will set value of location stored in x to 1 i.e, s.value=1. (REMEMBER BINARY SEMAPHORE'S STRUCTURE CONSISTS VALUE AND QUEUE FIELD ) and older value of location stored in x will be stored in y i.e, y=0.

I think this is one of the main difficulties of the question for many. Now you can solve the question.

Comments

Thank you sir.Its help now to solve this question complete story is behind this.

Answer 4

Say, old value of x is 0 and not 1, bcz if old value of x=1 then why ques says that fetches old value of x and set x=1.
So, suppose x=0 initially.

Code for P:
----------------------------------------
Line 1: void P (binary_semaphore *s) {
Line 2: unsigned y;
Line 3: unsigned *x = &(s->value);
Line 4: do {
Line 5: fetch-and-set x, y;
Line 6: } while (y);
Line 7: }

Code for V:
----------------------------------------
Line 8: void V (binary_semaphore *s) {
Line 9: S->value = 0;
Line 10: }

So, since given that Context switching disabled in function P, so lines from 1 to 7 will execute without any pre-emption.

So, suppose a process P1 came, execute lines 1 to 5, now at line 5 it set x=1 and fetch y=0(bcz old value of x=0), and now it execute line 6 (while(0))--->false. 
Suppose this process is inside Critical section. 

Now suppose process P2 came, and it fetches value of y=1(bcz when process p1 execute fetch-and-set it sets x=1). So, now process P2 stuck in while loop-> while(1)-----> busy waiting.

Now, suppose P1 process execute its V code and make S.value=0.
Now, control came back to process P2. So now P2 execute line 5.
Now, key thing to note here is that->

fetches the old value of x in y without allowing any intervening access to the memory location x.
bcz, x contains memory location which contains S->value, and since memory access not allowed hence x contains old value which was 1 (when P2 first time executed fetch-and-set and set x=1)
so, it means even there is no one in Crirical section, still P2 is in busy waiting.

So, context switching is must in P.