GATE CS 2012 Q.32 (CS Q.32): Process Synchronization and Concurrency

Fetch_And_Add(X, i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.

AcquireLock(L){
    while (Fetch_And_Add(L, 1))
        L = 1;
}

ReleaseLock(L){
    L = 0;
}

This implementation

fails as $L$ can overflow

fails as $L$ can take on a non-zero value when the lock is actually available

works correctly but may starve some processes

works correctly without starvation

Official answer and solution

Official answer: B
From: Official GATE 2012 answer key

Solution

Trace concurrent executions of AcquireLock and ReleaseLock to identify race conditions in the lock implementation.

Let $L$ be initialized to 0 (lock free).
Process $P_1$ executes AcquireLock(L):

Fetch_And_Add(L, 1) atomically reads 0 and writes 1.
Since the returned value is 0, the while condition is false. $P_1$ acquires the lock and enters critical section.

Process $P_2$ attempts to acquire the lock while $P_1$ is inside:

Fetch_And_Add(L, 1) reads 1 and writes 2.
Since returned value 1 is non-zero, $P_2$ enters the while loop body and prepares to execute L = 1;.

Before $P_2$ executes L = 1;, $P_1$ releases the lock:

$P_1$ calls ReleaseLock(L) which sets L = 0;.
The lock is now legitimately available.

Now, $P_2$ executes the statement L = 1; inside its while loop:

$L$ is set back to 1 even though NO process is currently in the critical section!

When any subsequent process (or $P_2$ in its next iteration) calls Fetch_And_Add(L, 1), it finds $L \ge 1$ and believes the lock is held, even though it is actually free.
Therefore, the implementation fails as $L$ can take on a non-zero value when the lock is actually available.

Final answer

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

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 32 of 65, printed as CS Q.32
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