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

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.

Answer 2

Option A