The GATE Grind

GATE 2017 CS – Question 37

Operating System · Deadlock · 2 marks · Multiple choice

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:

  1. $x = 1$, $y = 2$
  2. $x = 2$, $y = 1$
  3. $x = 2$, $y = 2$
  4. $x = 1$, $y = 1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $x = 1$, $y = 1$

Explanation

With non-reentrant locks, a single thread that tries to acquire a lock it already holds will block forever waiting for itself. That is a deadlock with just one thread and one lock, so the minimum is $x = 1$ and $y = 1$.