GATE CS 2015 Set 3 Q.20 (CS Q.10): Process Synchronization and Concurrency

Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes

/* Process X */
while (true) {
    varP = true;
    while (varQ == true) {
        /* Critical Section */
        varP = false;
    }
}

/* Process Y */
while (true) {
    varQ = true;
    while (varP == true) {
        /* Critical Section */
        varQ = false;
    }
}

Here, varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

The proposed solution prevents deadlock but fails to guarantee mutual exclusion

The proposed solution guarantees mutual exclusion but fails to prevent deadlock

The proposed solution guarantees mutual exclusion and prevents deadlock

The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Analyze the concurrency protocol for mutual exclusion and deadlock vulnerabilities by tracing interleavings.

Initially, varP = false and varQ = false.
Notice the internal structure of both processes:

Process X: sets varP = true, then executes while (varQ == true) { /* Critical Section */ varP = false; }
Process Y: sets varQ = true, then executes while (varP == true) { /* Critical Section */ varQ = false; }

Mutual Exclusion Check:
Consider the interleaving where both processes execute simultaneously:

Process X sets varP = true.
Process Y sets varQ = true.
Process X tests condition while (varQ == true). Since varQ is true, Process X enters the loop body and proceeds into the Critical Section.
Process Y tests condition while (varP == true). Since varP is true, Process Y enters the loop body and proceeds into the Critical Section.
Both Process X and Process Y are simultaneously inside the Critical Section!
Therefore, the protocol fails to guarantee mutual exclusion.

Deadlock Check:
Deadlock occurs if both processes are indefinitely waiting for each other to take an action, preventing either from making progress.

In this code, when both varP and varQ are true, neither process waits; instead, both enter the loop body and proceed.
Once inside, Process X sets varP = false and Process Y sets varQ = false, resetting the variables.
If only one process wants to enter (say X), with varQ = false, X tests varQ == true (false), skips the critical section, and loops back setting varP = true.
Therefore, deadlock cannot occur.

Thus, the proposed solution prevents deadlock but fails to guarantee mutual exclusion (Option A).

Final answer

Common trap

Assuming the while loop acts as a spin-lock waiting for the other variable to become false, whereas here the critical section is inside the while (condition == true) block, so having both variables true causes both to enter simultaneously.

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 20 of 65, printed as CS Q.10
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