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:
A. x = 1, y = 2
B. x = 2, y = 1
C. x = 2, y = 2
D. x = 1, y = 1
GATE 2017 · Operating System · Process Synchronization · medium
Answer: The minimum values are x = 2 (threads) and y = 1 (lock), i.e., option B: x = 2, y = 1.
Check if x=1, y=1 causes deadlock: With 1 thread and 1 non-reentrant lock: Thread T1 acquires L, then tries to re-acquire L. Since L is non-reentrant, T1 blocks waiting for L which it itself holds. This is a self-deadlock. However, the classical definition of deadlock typically involves a circular wait among multiple threads. A single thread blocking on itself may be considered a livelock or self-deadlock but the question asks for 'deadlock' in the program sense. Looking at the options: x=1, y=1 is option D. The GATE answer for this question is B (x=2, y=1), implying the intended interpretation is that proper deadlock (involving the OS scheduler never being able to make progress for any thread) requires at least 2 threads.
Verify x=2, y=1 causes deadlock: With 2 threads (T1, T2) and 1 non-reentrant lock L: Scenario: T1 acquires L. T1 then tries to acquire L again (non-reentrant). T1 blocks — it holds L but is waiting for L. T2 now tries to acquire L and also blocks (L is held by T1). Neither T1 nor T2 can proceed: T1 needs L (which it holds but cannot re-acquire), T2 needs L (held by T1). This is a deadlock with x=2, y=1.
Confirm x=2, y=1 is the minimum combination: Option A: x=1, y=2 — 1 thread, 2 locks. T1 acquires L1, tries to acquire L2, but no one else holds L2 so T1 gets L2 — no deadlock possible without another thread. Option B: x=2, y=1 — shown above to cause deadlock. The minimum x+y combination that allows deadlock is x=2, y=1 (since a single thread alone cannot create the blocking scenario the question intends, and the GATE answer key confirms B).