-
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 Y computed 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
}
Process Y:
private i;
for (i=0; i
b[i] = g(a[i]);
}
Which one of the following represents the correct implementations of ExitX and EntryY?
-
- ExitX(R, S) {
P(R);
V(S);
}
EntryY(R, S) {
P(S);
V(R);
} - ExitX(R, S) {
V(R);
V(S);
}
EntryY(R, S) {
P(R);
P(S);
} - ExitX(R, S) {
P(S);
V(R);
}
EntryY(R, S) {
V(S);
P(R);
} - ExitX(R, S) {
V(R);
P(S);
}
EntryY(R, S) {
V(S);
P(R);
}
- ExitX(R, S) {
Correct Option: C
Option (a) Suppose process X executes Exit X then it will wait for R, and then process Y executes Entry Y then it will wait for S. Since, initially both binary semaphores are 0, no one will increment it and both process will be stuck up in a deadlock.
∴ Option (a) is incorrect.
Option (b) Here if process X executes for n times repeatedly it will set both semaphores to 1 (since only two values are possible) and after that process Y executes. First time it passes the Entry Y and make both semaphores to 0. And on second time it finds both semaphores to 0 and cannot pass the Entry Y barrier. Hence it will get stuck. So, option (b) is wrong. Option (c) Considering any sequence of operation of process X and process Y, first process X will wait for S which is increment by process Y and then process Y waits for R which is incremented by process X. There is no sequence of operation in which the value of R or S overlaps.
∴ Both processes execute one after another.
So, option (c) is correct.
Option (d) Suppose first process X executes it sets R = 1 and then waits for S. Now after that process Y executes. It first sets S = 1 and decrement R = 0. It comes again and then again sets S = 1 (i.e., it overlaps the value of S) and then again wait for R. Clearly hence one iteration of process X is lost due to overlapping of value of S, and after n – 1 iteration process X will be stuck.
So option (d) is wrong.
