GATE CSE 2013 | Question: 39

Question

A certain computation generates two arrays a and b such that $a[i] = f(i)$ for $0 \leq i < n$ and $b[i] = g(a[i])$ for $0 \leq i < n$. Suppose this computation is decomposed into two concurrent processes $X$ and $Y$ such that $X$ computes the array $a$ and $Y$ computes the array $b$. The processes employ two binary semaphores $R$ and $S$, both initialized to zero. The array $a$ is shared by the two processes. The structures of the processes are shown below.

Process X:

private i; 
for (i=0; i< n; i++) { 
 a[i] = f(i); 
 ExitX(R, S); 
} 

Process Y:

private i;
for (i=0; i< n; i++) { 
  EntryY(R, S); 
  b[i] = g(a[i]); 
}

Which one of the following represents the CORRECT implementations of ExitX and EntryY?

• A.

  ExitX(R, S) { 
   P(R); 
   V(S); 
  }
  EntryY(R, S) { 
   P(S); 
   V(R); 
  }
  

• B.

  ExitX(R, S) { 
   V(R); 
   V(S); 
  }
  EntryY(R, S) { 
   P(R); 
   P(S); 
  }
  

• C.

  ExitX(R, S) { 
   P(S); 
   V(R); 
  }
  EntryY(R, S) { 
   V(S); 
   P(R); 
  }
  

• D.

  ExitX(R, S) { 
   V(R); 
   P(S); 
  }
  EntryY(R, S) { 
   V(S); 
   P(R); 
  }
  

Comments

The problem here is that R and S are binary semaphores

So multiple signal operation without any wait operation in between is of No use

---

GATE CSE 2013 | Question: 39 by Sachin Sir

---

DIff between option c and option d is that in option when it gets s=1 and uses it for v(r) it comes back to p(s) first in option c which means it will make it s=0 and ensure that the array a is only one step ahead not more than one than that of array b

While, incase of option d we can see that v(r) is first which means that p(s) will be applied later so multiple v(r) can come continously due to that as s=1 will already be there which p(s) will pass and v(r) can happen again without calling the other process Y

Answer 1

• A. $X$ is waiting on $R$ and $Y$ is waiting on $X$. So, both cannot proceed.
   
• B. Process $X$ is doing Signal operation on $R$ and $S$ without any wait and hence multiple signal operations can happen on the binary semaphore so Process $Y$ won't be able to get exactly $n$ successful wait operations. i.e., Process $Y$ may not be able to complete all the iterations.
   
• C. Process $X$ does Wait(S) followed by Signal(R) while Process $Y$ does Signal(S) followed by Wait(R). So, this ensures that no two iterations of either $X$ or $Y$ can proceed without an iteration of the other being executed in between. i.e., this ensures that all $n$ iterations of $X$ and $Y$ succeeds and hence the .
   
• D. Process $X$ does Signal(R) followed by Wait(S) while Process $Y$ does Signal(S) followed by Wait(R). There is a problem here that $X$ can do two Signal(R) operation without a Wait(R) being done in between by $Y$. This happens in the following scenario:
  Process $Y$: Does Signal (S); Wait(R) fails; goes to sleep.
  Process $X$: Does Signal(R); Wait(S) succeeds; In next iteration Signal(R) again happens;

So, this can result in some Signal operations getting lost as the semaphore is a binary one and thus Process $Y$ may not be able to complete all the iterations. If we change the order of Signal(S) and Wait(R) in EntryY, then (D) option also can work. 

Comments

Option (a) and (c),  deadlock because they do P on semaphores that are initialized to 0 (clearly given in the question) with no prior V

So, according to me Option C is also not correct.

Please Clarify it Sir...

---

@Aditya Singh Chauhan deadlock not possible in option (C), P(S); in Entry code is just there to make sure that without running the Exit code can't run Process X again. 

---

How d may cause uncompletion of y :

Answer 2

Let us think of it in this way. To calculate value of $b[0]$, we need to already have value of $a[0]$ with us because $b[0] = g(a[0])$, Else some error will be thrown.

So there can only be 2 cases:

1. $Process X$ is selected first, this is good. It will calculate the value of $a[0]$ and then after this if $process Y$ executes, it will already have the corresponding value of $a[0]$ to calculate value of $b[0]$. If this case happens always, we do not need any semaphores.
2. $Process Y$ is selected first. This is bad because now $Process Y$ will try to calculate value of $b[0]$ but value of $a[0]$ is not calculated yet. Now look at option $C$. Before calculating the value of $b[0]$, $Process Y$ needs to pass $EntryY$ first. Inititally $S=0, R=0$. To pass $EntryY$, it will first execute $V(S)$, simple up operation on $S$, now $S=1,R=0$. Now it tries to execute next line, $P(R)$. It will be blocked because $R=0$ and will have to wait for $R$ to be $1$, i.e. until up operation is performed on $R$. Now while it is waiting, $Process X$ executes and it finds value of $a[0]$. (now we can find value of $b[0]$ because $b[0] = g(a[0])$). Now it will go inside the $exitX$ and executes $P(S)$ so now $S=0,R=0$. It goes to the next line which is V(R). This is what we have been waiting for and now $S=0,R=1$. Now $process Y$ resumes and calculates $b[0]$. This can be generalized to $i, 0 < i < n$.

And hence we can safely calculate the arrays $a$ and $b$.

Comments

When process Y resumes, will it again execute EntryY or resume from P(R) ?

---

from P(R)
in binary semaphore if process is suspended then it needs to wakeup that process from another.
if it wakeup then it will start from next instruction.
 

Answer 3

Approach that must be followed while solving this kind of problem :

1. Identify producer and consumer and which semaphore is acting as wake up signal for consumer.

2. Here there must be strict alteration as elements of B  is dependent on A and semaphores are binary. If there would have been counting semaphore then no need of strict alteration as count will be maintained by counting semaphore.

3. Producing element in a[] up(sem 1(signal for consumer)) then block it till b does not calculate f(a[i]) so down(sem 2 ) here producer will be blocked. Now b will consume signal generated by a(sem 1) and calculate element of b(fa[i]) hence down (sem 1) now as a[i] and b[i] is done to calculate next element of a up (sem 2) so that producer can get unblocked and produce next element.

 

c matches this process.

Comments

hello Tushar, since GO doesn't allow sending messages, could we connect on LinkedIn?

---

Here i variable also share so have this concept to solve this problem

 

---

simulating in brain taking 10 minutes to solve

Answer 4

Option D is incorrect because If we consider n=2 than Process  X will compute a[0] and a[1] both but Process Y will not able to compute b[1] because P(R) signal. Below Image is showing such a case that Y will not able to execute exactly n times.

Comments

at step 9 r should be 2 ??am i wrong..

 

---

binary semaphore can't take any values other than 0 or 1. If we decrement 0 then also 0, if we increment 1 then also 1.@Harshit_Pant

Answer 5

//A
private i; 
for (i=0; i< n; i++) { 
    a[i] = f(i); 
    ExitX(R, S); 
} 

//B
private i;
for (i=0; i< n; i++) { 
    EntryY(R, S); 
    b[i] = g(a[i]); 
}


A and B are supposed to execute such that A[0]->B[0]->A[1]->B[1] and so on

Consider Option A :

ExitX(R, S) { 
 P(R); 
 V(S); 
}
EntryY(R, S) { 
 P(S); 
 V(R); 
}

A	B
a[0] = f(0)
Busy waiting //R==0
	Busy waiting //S==0

This creates a deadlock hence A not possible.

Option B:

ExitX(R, S) { 
 V(R); 
 V(S); 
}
EntryY(R, S) { 
 P(R); 
 P(S); 
}

A	B
a[0] = f(0)
R=1
S=1
a[1] = f(1)
R=1
S=1
a[2] = f(2)

This will starve B and lead to incorrect results.

 

Option D :

ExitX(R, S) { 
 V(R); 
 P(S); 
}
EntryY(R, S) { 
 V(S); 
 P(R); 
}

A	B
a[0] = f(0)
R=1
S=0 // Busy Waiting
	S=1
S=0
a[1] = f(1)
R=1

This leads to incorrect solution again.
A,B,D eliminated, C can be proven to work in the same way.

Comments

best explanation. Thanks

Answer 6

https://youtu.be/ka7e9gMIoPg