Deadlock and the Four Conditions · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

When two locks freeze each other

Computing · Computer Systems · ages 20-22
Name ______________________   Date ____________

  1. Thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1. What happened?

    • A race that fixes itself
    • A waiting cycle, so a deadlock
    • One slow lock and nothing more

  2. Which set lists all four things a deadlock needs?

    • One holder, hold and wait, no take-back, a cycle
    • Two threads, two locks, two cores, two crashes
    • A timeout, a retry, a slow disk, a big file

  3. A deadlock can happen even when one of the four conditions is missing.

    Circle one:   True   False

  4. Every thread now takes lock 1 before lock 2. What happens to the waiting cycle?

    • It cannot form
    • It forms twice as fast
    • It moves inside lock 2

  5. In a wait-for graph, which way should an arrow point?

    • From the lock to the thread that wants it
    • From each thread to itself
    • From the waiting thread to the lock holder

  6. Which change removes the no take-back condition?

    • Add a third lock to the program
    • Let the system reclaim a held lock and hand it back later
    • Make both threads sleep a little longer

  7. Sam draws arrows from each lock to the thread waiting for it, finds no loop, and says the program is safe. What is wrong?

    • Two threads can never deadlock
    • Cycles only matter with three or more locks
    • His arrows point the wrong way, so a real cycle stays hidden

  8. All functions take locks in the order 1, 2, 3 except one function that takes 3 then 1. What is the smallest fix?

    • Remove lock 2 from the whole program
    • Change that one function to take 1 before 3
    • Add a timeout to every lock
LightMySky · lightmysky.comW1-mt_CsMOA4sBb1-s1

Answer key

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

When two locks freeze each other W1-mt_CsMOA4sBb1-s1

  1. A waiting cycle, so a deadlock · Each waiter waits on the other, so the arrows form a cycle.
  2. One holder, hold and wait, no take-back, a cycle · All four must hold at once. Miss one and there is no deadlock.
  3. False · All four must hold at once. Remove one and the deadlock breaks.
  4. It cannot form · One shared order removes the cycle, so the deadlock is gone.
  5. From the waiting thread to the lock holder · Arrows run waiter to holder, so a loop means a cycle of waiting.
  6. Let the system reclaim a held lock and hand it back later · If a held lock can be taken back, waiting threads need never freeze.
  7. His arrows point the wrong way, so a real cycle stays hidden · Arrows must run waiter to holder. Drawn backwards, a real cycle disappears.
  8. Change that one function to take 1 before 3 · One rule-breaker can close the cycle, so fixing it restores the shared order.
Worksheet · LightMySky