IAE Academy

GATE 2020 CS Q.34: solution and answer

GATE 2020 · CSQ.34 · 2 marks · MCQ

Each of a set of 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?

  1. (A)

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

  2. (B)

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

  3. (C)

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

  4. (D)

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

See the question in the paper
GATE 2020 CS question 34Tap to open full size

Answer and solution

ANSWER

The correct option is (A): no process executes CODE SECTION Q before every process has finished CODE SECTION P.

Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Semaphore a starts at 1, so it acts as a mutex. It protects only the update count=count+1 and the test count==n. CODE SECTION P sits before wait(a), outside that lock.

  2. Semaphore b starts at 0, so wait(b) blocks every process until some process executes signal(b).

  3. Each process increments count exactly once, under the lock. Only the -th process to arrive sees count==n, so only that process executes the first signal(b).

  4. Until the -th process arrives, b stays 0. Each of the first processes finishes P, releases a, and blocks at wait(b).

  5. After the -th process has finished P and signalled b, the value of b is 1. One blocked process wakes, executes signal(b) and so passes the token on. This repeats until all processes are released. Every process passes through wait(b); signal(b), so this is a one-use barrier (a turnstile).

  6. No process reaches CODE SECTION Q before b has been signalled. That signal happens only after the -th process has run its increment, which comes after that process has finished P, and every other process had finished P before it incremented. So no process enters Q before every process has finished P, and (A) holds.

  7. Check the others. (B) After the release, all processes can be in Q together, so there is no limit of two. (C) P is outside the mutex, so processes can run P concurrently. (D) All processes may be in P at the same time, since nothing limits entry to it.

KEY IDEA

A semaphore initialised to 0 that the last arriving process signals, and that each released process signals again, is a one-use barrier. The mutex only guards the arrival counter.

WATCH OUT FOR

Reading semaphore a as protecting CODE SECTION P. It guards only the counter update, and P runs before wait(a), so option (C) is false.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 7 Synchronisation questions, with notes

More Synchronisation questions