Skip to main content

Deadlock and Lock-Free Reasoning Lab

Retrieval Prompts​

  1. State the four Coffman conditions for deadlock.
  2. State which Coffman condition each of these fixes breaks: global lock ordering; trylock + backoff; transactional rollback; bounded resource pool.
  3. Define lock-free progress versus wait-free progress.
  4. Describe the ABA problem in one paragraph.
  5. State what memory_order_acquire pairs with and what that pairing guarantees.

Compare and Distinguish​

Separate these pairs:

  • deadlock versus livelock versus starvation
  • prevention versus detection versus avoidance
  • memory_order_relaxed versus memory_order_seq_cst
  • a Treiber lock-free stack versus a mutex-protected stack (safety, progress, memory reclamation)
  • reader-preferring, writer-preferring, and FIFO fair rwlocks

Common Mistake Check​

Diagnose each. Name the concurrency failure class:

  1. Two threads each call transfer(a, b, 100) and transfer(b, a, 50) respectively. The program hangs. (What failed? What fix?)
  2. A lock-free queue works under load but leaks memory visibly over hours. (What failed?)
  3. A rwlock implementation passes correctness tests but on a 16-core server a writer waits 40 seconds to acquire while readers continuously enter. (What failed?)
  4. A CAS loop on a shared counter gets the correct sum under 2 threads but loses updates under 64 threads. (What could cause this?)
  5. A sync.RWMutex protected cache in Go gives correct results but CPU profiling shows huge time in runtime.semacquire. (What failed?)

Mini Application​

Do all three:

  1. Coffman analysis. For the deadlock-prone dining-philosophers implementation, draw the waits-for graph at the moment of deadlock. Identify the cycle. Apply the resource-ordering fix, redraw the graph, and confirm no cycle is possible.
  2. Readers-writers fairness trace. For a reader-preferring rwlock, construct a write operation that waits arbitrarily long because new readers keep arriving. Convert to writer-preferring and show the symmetric starvation. Design a FIFO scheme and argue bounded waiting.
  3. ABA walkthrough. Construct a 4-thread schedule on the Treiber stack that exhibits ABA. Show the stack state at each step. Then describe how a tagged-pointer CAS (or hazard pointers, epoch-based reclamation) blocks the schedule.

Evidence Check​

This page is complete only if you can:

  • produce each trace or graph without looking at the concept page
  • name each Coffman condition a given fix breaks
  • produce a valid ABA schedule and a mitigation that blocks it
  • state the fairness contract of at least one real rwlock in production use (std::shared_mutex, sync.RWMutex, Java ReentrantReadWriteLock)