GATE CS 2016 Set 2 Q48 — Concurrency and Synchronization

To evaluate the given two-process synchronization solution, let us analyze the three requirements of process synchronization: Mutual Exclusion, Progress, and Bounded Waiting.

The shared variable turn is initialized to 0.

1. Mutual Exclusion

• For Process 0 to enter its Critical Section (CS), the condition turn == 1 must be false, which means turn must be 0.
• For Process 1 to enter its CS, the condition turn == 0 must be false, which means turn must be 1.
• Since the variable turn can hold only one value (either 0 or 1) at any given instant, both processes can never be in the critical section simultaneously. Thus, Mutual Exclusion is satisfied.

2. Progress

The progress requirement states that if no process is in its CS and some processes want to enter, then only those processes that are not executing in their remainder section can participate in deciding which process will enter next, and this decision cannot be postponed indefinitely.

• Initially, turn = 0. Process 0 enters the CS, executes, and upon exit, sets turn = 1.
• Now, suppose Process 0 wants to enter the CS again, but Process 1 is busy in its remainder section and has no interest in entering the CS.
• Since turn is currently 1, Process 0 is blocked at its entry condition: loop while (turn == 1).
• Process 0 is prevented from entering the CS by Process 1, which is not even interested in entering. Thus, Progress is violated.

3. Bounded Waiting

• Because of strict alternation (Process 0 $\rightarrow$ Process 1 $\rightarrow$ Process 0), once a process exits, it hands over the turn to the other process. A process cannot enter the CS twice consecutively if the other process is waiting. Thus, the waiting time is bounded to at most one turn, so Bounded Waiting is satisfied.

Since the solution violates the progress requirement, Option C is the correct statement.