Official PYQ · 2017Set 1 · Q27Concurrency and SynchronizationMCQ1 mark

GATE CS 2017 Set 1 Q27 — Concurrency and Synchronization

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:

View worked solution

Answer: D

To find the minimum number of threads ( $x$ ) and locks ( $y$ ) that can cause a deadlock, let us analyze the behavior of non-reentrant locks.

A lock is non-reentrant if a thread that already holds the lock cannot acquire it again without releasing it first. If it attempts to do so, it blocks indefinitely waiting for the lock to be released.

Consider the case where:

Number of threads, $x = 1$ (Thread $T_1$ )
Number of locks, $y = 1$ (Lock $L_1$ )

Let the thread $T_1$ execute the following sequence of operations:

acquire(L1) — $T_1$ successfully acquires the lock $L_1$ .
acquire(L1) — Since $L_1$ is non-reentrant and already held by $T_1$ , $T_1$ blocks waiting for $L_1$ to be released.

Since $T_1$ is blocked, it can never progress to release $L_1$ . This results in a self-deadlock.

Thus, the minimum number of threads and locks required to cause a deadlock is $x = 1$ and $y = 1$ .

Therefore, the correct option is D.

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

Published 10 Oct 2026

Report a correction

Browse this topic

More Concurrency and Synchronization questions

GATE CS 2017 Set 1 Q27 — Concurrency and Synchronization

Related questions