When two locks freeze each other

Computing · Computer Systems · ages 20-22

Name ______________________ Date ____________

A holds lock 4 and waits for lock 7. B holds lock 7 and waits for lock 4. The locks block without timeout, and neither thread releases its lock first. What has happened?
- Both threads can acquire the other lock without waiting.
- Both threads are deadlocked in a cycle of waiting.
- Only A is waiting; B can finish without acquiring lock 4.
Which set names the four necessary conditions for resource deadlock?
- Mutual exclusion, hold and wait, no preemption, circular wait
- Mutual exclusion, repeated retries, automatic rollback, circular wait
- Shared access, hold and wait, automatic preemption, delayed responses
A thread waiting for a lock while holding no resource meets the hold-and-wait condition.
Circle one: True False
Every thread acquires lock 2 before lock 5 when it needs both. What does this rule prevent?
- Circular wait involving only these two locks
- Every delay caused by either of these two locks
- Every deadlock caused by any resource in the program
Thread P waits for a lock held by thread Q. What edge belongs in a thread-only wait-for graph?
- Q to P, pointing from the holder to the waiting thread
- P to Q, but only after P releases any locks it holds
- P to Q, pointing from the waiting thread to the holder
A resource system can safely abort a holder, undo its partial work, and forcibly reclaim its resources. Which deadlock condition does this remove?
- Mutual exclusion: a resource permits only one holder at a time
- No preemption: held resources cannot be forcibly reclaimed
- Circular wait: each thread waits for the next thread in a cycle
A complete directed wait-for graph has edges U to V, V to W and W to U. Sam reverses every arrow and says the cycle disappears. Which check corrects his claim?
- Reversing the arrows removes the cycle because each edge now points toward a previous holder.
- Reversing the arrows removes the cycle because a cycle requires its original starting thread.
- The reversed edges still form the cycle U to W to V to U.
R and S are already deadlocked on locks 8 and 9. A patch gives future executions one acquisition order. What should the team conclude about the stuck run?
- The patch makes the held locks available automatically, so the stuck run needs no recovery.
- The rule prevents future cycles; the stuck run still needs safe recovery.
- The patch proves the stuck run was waiting for input, so its held locks need no attention.

Answer key

For grown-ups. Fold this page away before handing over the rest.

When two locks freeze each other W1-mt_CsMOA4sBb1-s1

Both threads are deadlocked in a cycle of waiting. · A waits for B to release lock 7, and B waits for A to release lock 4. Neither can proceed.
Mutual exclusion, hold and wait, no preemption, circular wait · The four necessary conditions are mutual exclusion, hold and wait, no preemption, and circular wait.
False · Hold and wait requires keeping a resource while requesting another. This thread holds no resource.
Circular wait involving only these two locks · A cycle involving these locks would require a thread holding lock 5 while requesting lock 2. The shared order forbids that.
P to Q, pointing from the waiting thread to the holder · The edge P to Q records that P currently waits for Q. P need not release another lock before that waiting relation is recorded.
No preemption: held resources cannot be forcibly reclaimed · The removed condition is "No preemption: held resources cannot be forcibly reclaimed". This system supports safe forced reclamation.
The reversed edges still form the cycle U to W to V to U. · Reversal gives V to U, W to V and U to W. Following U to W to V to U returns to U, so the directed cycle remains.
The rule prevents future cycles; the stuck run still needs safe recovery. · Changing future acquisition order does not release locks already held in a deadlock. The stuck run needs supported safe recovery, such as abort and rollback.