GATE CS 2020 Q34 — Concurrency and Synchronization

This code implements a classic Barrier Synchronization mechanism. Let us analyze the execution step-by-step:

1. Initial State

• Semaphore $a = 1$ (used for mutual exclusion when updating the shared variable count).
• Semaphore $b = 0$ (used to block processes until all of them reach the barrier).
• count = 0.

2. Execution of the First $n-1$ Processes

When any of the first $n-1$ processes finish CODE SECTION P and enter the synchronization block:

1. They acquire the lock $a$ via wait(a).
2. They increment count. Since count < n, the condition if (count == n) is false, so they do not signal $b$.
3. They release the lock $a$ via signal(a).
4. They execute wait(b). Since $b = 0$, these $n-1$ processes get blocked here.

3. Arrival of the $n$-th Process

When the $n$-th process finishes CODE SECTION P and enters the synchronization block:

1. It acquires lock $a$, increments count to $n$.
2. Since count == n, it executes signal(b), which increments $b$ to $1$.
3. It releases lock $a$ via signal(a).
4. It executes wait(b) (which succeeds, decrementing $b$ back to $0$) and immediately executes signal(b) (incrementing $b$ back to $1$).
5. It then proceeds to CODE SECTION Q.

4. Cascading Wake-up

The signal(b) executed by the $n$-th process wakes up one of the blocked processes waiting at wait(b). That awakened process then executes signal(b), which wakes up the next process, and so on. This cascading effect ensures all $n$ processes are unblocked and can proceed to CODE SECTION Q.

Conclusion

No process can enter CODE SECTION Q until the $n$-th process has finished CODE SECTION P and signaled $b$. Thus, it ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

Therefore, Option A is the correct choice.