edited by
27,347 views
104 votes
104 votes

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? 

  1. The implementation may not work if context switching is disabled in $P$ 
  2. Instead of using fetch-and –set, a pair of normal load/store can be used 
  3. The implementation of $V$ is wrong
  4. The code does not implement a binary semaphore
edited by

6 Answers

Best answer
106 votes
106 votes
  1. Answer :- 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 !
     
  2. 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.
     
  3.  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.
     
  4. 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
     
edited by
50 votes
50 votes

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.

 

edited by
12 votes
12 votes

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.

edited by
0 votes
0 votes
Option a.
Answer:

Related questions