4.7k views

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 | 4.7k views
–1
do {
fetch-and-set x, y;
} while (y); 

isn't this a spinlock? By using a spinlock, processes need not be context switched. Once the spinlock fails the process will get into cs(by executing V()). So this implementaion will work even if context switch is disabled.  By definition of binary semaphore , semaphore's value must be either 0 or 1 but here semaphore's value ranges 0 to any value. Thus this is not BINARY semaphore even though it is a semphore. From the above arguments I find D as the answer. Kindly correct me if I am wrong.

0
Yes, i guess you're correct. Context switching is not needed if the processes are spin locked. However, the code is not implementing Binary semaphores and also the implementation of both P() and V() is incorrect.

Let's take a look at binary_semaphore S.

When S=1, all the processes are spinlocked.

When S=0, a process can execute in critical section.

Any process can attempt P() implementation and run their CS for S=0. Also, the successive calls to V() must be blocked to make it binary semaphore.
+1

What does the line "fetches the old value of x n y" mean?

0
I think 'n' here is a typo. It should be 'and'.
+7
I think the best way to answer this type of questions is to use option elimination technique.

d) wrong because a binary semaphore takes values of 0 & 1 only which is being done here too.

c) wrong because Implementation of 'V' is customized here according to the def. of Fetch-and-Set.

b) wrong because normal load_and_store is not atomic.

Thus answer a). Reason for a) to be correct because any semaphore implementation needs context switching to be ENABLED otherwise no other process cannot be brought in when one gets locked.
+2
at last i understood fetch-and-set fetches value of x and sets in y.
in question,"fetches the old value of x n y",is just a typo..she missed just a letter "i".
"n" in place of "in" made me think for half an hour
0
It is kind of TSL instruction. Someone correct me if I am wrong.

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

Yes, right .

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

s = 0 also possible..

+3
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?
+1
yes, it is modified semaphore implementation.

They modify that and add some constraints.
0
@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.
0

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
0
yes sir i got it..thnku
0
@ 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
0
@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)?
0

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

+1 vote

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 :

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;

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

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

-> fetch-and-set x,y;     <- this statement will set value of location stored in x to 1 i.e, s.value=1.  and older value of location stored in x will be stored in y i.e, y=0.

I think this is the main difficulty of the question. Now you can solve the question.

edited
–1 vote
Option a.
0

Arjun sir..
0
Why not the answer is B??
+2
Because normal Load/Store operation is not atomic
0
I to think that option can be B , Load and Store works same as the given Question code . Or can anyone plzz give the actual code of Load and Store
–1 vote

Option A