Deadlock and Prevention Strategies

Problem What is a deadlock, and how can it be prevented?

Be ready to discuss

• The definition: two or more processes or threads each hold a resource and wait on one held by another, forming a cycle in which none can ever proceed.
• The four Coffman conditions that must all hold simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait.
• Prevention by breaking circular wait: impose a global total ordering on resources and require every thread to acquire locks in that order.
• Prevention by breaking hold-and-wait: acquire all needed resources atomically up front, or use try-lock with timeout and randomised backoff, releasing everything on failure.
• Prevention by allowing preemption: force a victim to release its resources and roll back, which is exactly what a database deadlock victim does.
• Deadlock avoidance vs prevention: the Banker's algorithm computes safe states dynamically, but needs advance knowledge of maximum resource demand.
• Detection and recovery: build a wait-for graph, look for cycles, and abort a victim - the pragmatic choice when deadlocks are rare and prevention is too costly.
• Related-but-distinct failure modes worth naming: livelock and starvation.