Suppose we want to synchronize two concurrent processes P and Q using binary…
2003
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.
Process P:
while (1) {
W:
print '0';
print '0';
X:
}
Process Q:
while (1) {
Y:
print '1';
print '1';
Z:
}Synchronization statements can be inserted only at points W, X, Y and Z.
Which of the following will always lead to an output starting with '001100110011' ?
- A.
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
- B.
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
- C.
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
- D.
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0
Attempted by 177 students.
Show answer & explanation
Correct answer: B
Answer: Use a semaphore-based handoff where P waits on S at the start of its cycle and signals T at the end, while Q waits on T at the start of its cycle and signals S at the end, initializing S = 1 and T = 0.
Why this works:
Start state: S = 1, T = 0. S allows P to begin; T blocks Q.
P executes: at W it performs wait(S) (succeeds), prints '0' and '0', then at X it performs signal(T).
Signal(T) at X makes T = 1, allowing Q to proceed at Y. Q then waits on T at Y (succeeds), prints '1' and '1', and at Z signals S.
Signal(S) at Z restores S = 1, allowing P to run its next cycle. This enforces repeated alternation of two zeros then two ones.
Therefore the synchronization that guarantees an output starting with 001100110011 is: P performs wait(S) at W and signal(T) at X; Q performs wait(T) at Y and signal(S) at Z; initialize S = 1 and T = 0.
Why the other arrangements fail (brief):
If semaphores are used only inside each process (no cross-process signal), the two processes are not coordinated and can interleave arbitrarily.
If both semaphores start at 1 even with cross-process wait/signal, Q might run first and produce ones before zeros, so the sequence may not start with 00.