A multithreaded program \(P\) executes with \(x\) number of threads and uses…
2017
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\)
Attempted by 101 students.
Show answer & explanation
Correct answer: D
Answer: x = 1, y = 1
Explanation: Locks are non-reentrant, so a thread that already holds a lock and then tries to acquire the same lock again will block waiting for itself. This causes a self-deadlock.
Self-deadlock with one thread and one lock: A single thread can deadlock itself by acquiring lock L and then attempting to acquire L again without releasing it; because the lock is non-reentrant, the second acquire blocks forever.
Two threads and one lock: This causes contention but not deadlock. One thread holds the lock while the other blocks; when the lock is released the blocked thread proceeds, so no circular wait exists.
Two threads and two locks: This can produce a classic circular-wait deadlock (each thread holds one lock and waits for the other), but it is not the minimal configuration because a single thread and single non-reentrant lock already suffice.
Therefore the minimum values are x = 1 and y = 1.