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

Option 1 is correct. I am unable to understand the reason for it. Please explain.


Explanations for the truth-value of each assertion:

(1) is true because any process running P() after another process has already run P() will see y==1 and so be stuck in the do-loop. If context-switching is disabled inside P() [and we assume re-enabled on exit from P()], then the process stuck in the do-loop will be the ONLY running process, so no other process can release that one from the do-loop by calling V().

(2) is false because a context-switch may occur between the load of y and the store to x. Consider processes P1, P2, both calling P(). The following sequence is possible: (a) P1 loads y, which happens to be 0; (b) The context switches to P2; (c) P2 loads y -which is still 0-, then sets x to 1 and exits the loop (because for it y==0) and enters the critical section; (d) The context switches back to P1, which now sets x to 1 -but still sees its version of y as 0, so it exits the loop and enters the critical section. Verdict: Mutual-exclusion is NOT enforced!

(3) The implementation of V() is not wrong, given the implementation of P(). Execution of V() WILL set 'value' to 0, and by the atomicity property this must occur either entirely before or entirely after any test_and_set. If before, then test_and_set will set y to 0 immediately; if after, the same thing will happen on the next do-loop iteration.

(4) [because of 2 & 3].


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.