GATE CS 2020 Q.44 (CS Q.34): Process Synchronization and Concurrency

Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

CODE SECTION P

wait(a);
count = count + 1;
if (count == n)
    signal(b);
signal(a);

wait(b);
signal(b);

CODE SECTION Q

What does the code achieve?

It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

It ensures that at most two processes are in CODE SECTION Q at any time.

It ensures that all processes execute CODE SECTION P mutually exclusively.

It ensures that at most $n - 1$ processes are in CODE SECTION P at any time.

Official answer and solution

Official answer: A
From: Official GATE 2020 answer key

Solution

Trace semaphore operations to recognize the reusable barrier synchronization pattern.

Initial state:

Semaphore $a = 1$ (provides mutual exclusion for updating count).
Semaphore $b = 0$ (blocks processes until all $n$ arrive).
Shared variable count = 0.

Execution trace:

As each of the first $n - 1$ processes finishes CODE SECTION P, it enters the critical section protected by $a$ , increments count, checks if (count == n) (which is false), releases $a$ , and executes wait(b).
Since $b = 0$ , all first $n - 1$ processes block at wait(b).
When the $n$ -th process finishes CODE SECTION P, it enters the critical section, increments count to $n$ , satisfies if (count == n), and executes signal(b), making $b = 1$ .
It then releases $a$ , executes wait(b) (decrementing $b$ back to 0), immediately executes signal(b) (incrementing $b$ back to 1 for the next waiting process), and enters CODE SECTION Q.
This turnstile allows each waiting process to unblock one after another and proceed to CODE SECTION Q.

Conclusion:

No process can pass wait(b) and execute CODE SECTION Q until the $n$ -th process executes signal(b), which happens only after all $n$ processes have finished CODE SECTION P.
Hence, the code guarantees that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 44 of 65, printed as CS Q.34
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source