GATE CS 2016 Set 2 Q.58 (CS Q.48): Process Synchronization and Concurrency

Consider the following two-process synchronization solution.

Process 0
--------
Entry: loop while (turn == 1);
(critical section)
Exit: turn = 1;

Process 1
---------
Entry: loop while (turn == 0);
(critical section)
Exit: turn = 0;

The shared variable turn is initialized to zero. Which one of the following is TRUE?

This is a correct two-process synchronization solution.

This solution violates mutual exclusion requirement.

This solution violates progress requirement.

This solution violates bounded wait requirement.

Official answer and solution

Official answer: C
From: Official GATE 2016 answer key

Solution

Analyze mutual exclusion, progress, and bounded waiting in the strict alternation synchronization protocol.

Examine Mutual Exclusion:
Process 0 can enter the critical section only when turn == 0. Process 1 can enter only when turn == 1. Since turn is a single variable that cannot simultaneously be 0 and 1, both processes cannot be inside the critical section concurrently. Thus, mutual exclusion is satisfied.

Examine Progress:
The progress requirement states that if no process is in its critical section and some processes wish to enter, only those processes that are not executing in their remainder section can participate in deciding which will enter next, and this selection cannot be postponed indefinitely.

Consider the following scenario:

Initially turn == 0. Process 0 enters the critical section, executes, and upon exit sets turn = 1.
Now turn == 1. Process 0 immediately wishes to re-enter its critical section, but Process 1 is currently busy in its remainder section and does not wish to enter.
Process 0 executes loop while (turn == 1); and is blocked waiting for Process 1 to change turn back to 0, even though no process is in the critical section.
Because a process in its remainder section blocks an interested process from entering the critical section, the progress requirement is VIOLATED.

Therefore, this solution violates the progress requirement.

Final answer

Common trap

Assuming strict alternation satisfies progress because processes take turns smoothly under symmetric workload.

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 58 of 65, printed as CS Q.48
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