GATE CS 2017 Set 1 Q.27 (CS Q.27): Deadlock Prevention, Avoidance and Detection

A multithreaded program $P$ executes with $x$ number of threads and uses $y$ number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock $l$ , then it cannot re-acquire lock $l$ without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of $x$ and the minimum value of $y$ together for which execution of $P$ can result in a deadlock are:

$x = 1, y = 2$

$x = 2, y = 1$

$x = 2, y = 2$

$x = 1, y = 1$

Official answer and solution

Official answer: D
From: Official GATE 2017 answer key

Solution

Examine self-deadlock conditions caused by non-reentrant locks.

A non-reentrant lock is defined such that if a thread currently holds lock $l$ , it cannot re-acquire lock $l$ without releasing it first. If it attempts to acquire $l$ again, it blocks until $l$ is released.

Consider a program with $x = 1$ (a single thread $T_1$ ) and $y = 1$ (a single non-reentrant lock $L_1$ ):

$T_1$ successfully acquires $L_1$ .
While still holding $L_1$ , $T_1$ executes another acquire(L_1) operation (e.g., in a nested function call or loop).
Because $L_1$ is non-reentrant and currently held, $T_1$ blocks waiting for $L_1$ to be released.
But $T_1$ is the only thread that holds $L_1$ and could release it. Because $T_1$ is blocked, $L_1$ will never be released.

This creates a permanent block (self-deadlock). Therefore, the minimum values of $x$ and $y$ that can result in a deadlock are $x = 1$ and $y = 1$ .

Final answer

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

Source

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