edited by
28,086 views
114 votes
114 votes

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?

  1. ExitX(R, S) { 
     P(R); 
     V(S); 
    }
    EntryY(R, S) { 
     P(S); 
     V(R); 
    }
    
  2. ExitX(R, S) { 
     V(R); 
     V(S); 
    }
    EntryY(R, S) { 
     P(R); 
     P(S); 
    }
    
  3. ExitX(R, S) { 
     P(S); 
     V(R); 
    }
    EntryY(R, S) { 
     V(S); 
     P(R); 
    }
    
  4. ExitX(R, S) { 
     V(R); 
     P(S); 
    }
    EntryY(R, S) { 
     V(S); 
     P(R); 
    }
    
edited by

6 Answers

Best answer
154 votes
154 votes
  1. $X$ is waiting on $R$ and $Y$ is waiting on $X$. So, both cannot proceed.
     
  2. 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.
     
  3. 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 answer.
     
  4. 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. 

edited by
20 votes
20 votes

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.

14 votes
14 votes

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

11 votes
11 votes

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.

Answer:

Related questions