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 ensure that the output string never contains a substring of the form 01^n0 or 10^n1 where n is odd?
- 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 and T initially 1
- C.
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
- D.
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1
Attempted by 92 students.
Show answer & explanation
Correct answer: C
Correct synchronization (single semaphore protecting both processes):
Use a single binary semaphore S initialized to 1, with a wait(P) on S before each process's two prints and a signal(V) after the two prints: P(S) at W, V(S) at X, P(S) at Y, V(S) at Z.
This enforces mutual exclusion around each pair of prints, so every time a process prints it outputs an atomic block "00" or "11".
The global output is therefore a concatenation of two-character homogeneous blocks (for example, ..., "00", "11", "00", ...).
Any substring consisting of a 0, followed by some number of 1s, followed by a 0 must contain an even number of 1s because ones appear only in blocks of two; hence an odd number of 1s between zeros is impossible. The same argument applies when swapping 0 and 1.
Therefore the synchronization described as 'P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1' prevents substrings of the form 0 1^n 0 or 1 0^n 1 with n odd.
Why the other arrangements fail:
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1: Using separate semaphores for the two processes does not prevent them from executing their printing regions concurrently, allowing interleavings that can create odd-length runs of the opposite symbol between equal symbols.
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1: Cross signaling with both semaphores initially available does not ensure serialization; both processes may proceed and interleave their prints, producing forbidden patterns.
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1: Signaling before printing and waiting after does not serialize the critical printing sections, so interleavings remain possible and the required property is not guaranteed.
A video solution is available for this question — log in and enroll to watch it.