Official PYQ · 2009Q33Concurrency and SynchronizationMCQ1 mark

GATE CS 2009 Q33 — Concurrency and Synchronization

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

void enter_CS(X)
{
    while(test-and-set(X));
}

void leave_CS(X)
{
    X = 0;
}

In the above solution, $X$ is a memory location associated with the $CS$ and is initialized to $0$ . Now consider the following statements:

Which of the above statements are TRUE?

View worked solution

Answer: A

The test-and-set(X) instruction is an atomic hardware instruction that performs the following operations atomically:


temp = X;
X = 1;
return temp;

Initially, $X = 0$ . Let us evaluate each statement:

Statement I: The solution is deadlock-free. (TRUE)
If multiple processes attempt to enter the critical section simultaneously when $X = 0$ , exactly one process will successfully execute test-and-set(X), receive a return value of $0$ , and exit the while loop to enter the critical section. The other processes will spin in the loop. Since progress is guaranteed and there is no circular dependency preventing all processes from proceeding, the solution is deadlock-free.
Statement II: The solution is starvation-free. (FALSE)
There is no mechanism to guarantee bounded waiting. A process waiting in the while loop might repeatedly lose the race to other processes that exit and re-enter the critical section. Thus, a process can starve indefinitely.
Statement III: The processes enter CS in FIFO order. (FALSE)
The selection of the next process to enter the critical section is arbitrary and depends purely on CPU scheduling and which process executes the atomic test-and-set instruction first when $X$ becomes $0$ . No FIFO queue is maintained.
Statement IV: More than one process can enter CS at the same time. (FALSE)
Since test-and-set is atomic, only one process can read $X = 0$ and set it to $1$ . Any subsequent process will read $X = 1$ and remain blocked in the while loop. Thus, mutual exclusion is strictly preserved.

Therefore, only statement (I) is TRUE.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions