A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤…
20132013
A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i] = g (a[i] )for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes \(X\) and \(Y\) such that \(X\) computes the array a and \(X\) 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); }
Attempted by 125 students.
Show answer & explanation
Correct answer: C
Key idea: implement a one-to-one handshake (rendezvous) so that for each index i, b[i]=g(a[i]) runs only after a[i]=f(i) has completed, regardless of which process runs first.
Use S to indicate Y's readiness and R to indicate X's completion for that index.
EntryY performs V(S) then P(R): it signals that Y is ready (V(S)) and then waits for X to signal that a[i] is ready (P(R)).
ExitX performs P(S) then V(R): it waits for Y's readiness (P(S)) and then signals that a[i] has been produced (V(R)).
Why this works (two example interleavings):
If X runs first for index i: X computes a[i], then ExitX executes P(S) and blocks waiting for Y; when Y runs its EntryY it does V(S) which unblocks X, then X does V(R) to let Y proceed with P(R) and compute b[i].
If Y runs first for index i: Y does V(S) and blocks on P(R); when X later does ExitX it performs P(S) (consuming that V(S)) and then V(R), which unblocks Y so it can compute b[i] using the a[i] X already produced.
Therefore the correct implementations are:
ExitX(R,S) { P(S); V(R); }
EntryY(R,S) { V(S); P(R); }
A video solution is available for this question — log in and enroll to watch it.