• Deadlock Model and Coffman Conditions
• Prevention (break the conditions)
• Avoidance (Banker’s algorithm)
• Detection and Recovery
• Engineering Practices
• Exercises

• Deadlock: set of processes/threads where each waits for an event only another in the set can cause.
• Coffman conditions: mutual exclusion, hold-and-wait, no preemption, circular wait.
• Resource-Allocation Graph (RAG): processes (circles), resources (squares); cycle implies deadlock if 1 instance per resource.

• Mutual exclusion: use lock-free or RCU where possible for read-mostly paths.
• Hold-and-wait: acquire-all-at-once (two-phase locking) or release before requesting new; can harm concurrency.
• No preemption: allow preemption of resources (e.g., roll back transactions, revoke CPU), tricky for mutexes.
• Circular wait: impose a global lock ordering; acquire locks in increasing order of rank.

// Enforce global lock ordering with numeric ranks
async function acquireOrdered(mutexes) {
  const sorted = [...mutexes].sort((a,b)=>a.rank-b.rank);
  const unlocks = [];
  for (const m of sorted) { unlocks.push(await m.lock()); }
  return () => { while(unlocks.length) unlocks.pop()(); };
}

Requires knowing each process’s maximum resource needs; system only grants requests that keep the state safe.

// Sketch of Banker's safety check
function isSafeState(avail, max, alloc) {
  const n = max.length, m = avail.length;
  const need = Array.from({length:n}, (_,i)=>max[i].map((x,j)=>x-(alloc[i][j]||0)));
  const work = avail.slice();
  const finish = Array(n).fill(false);
  let progress = true;
  while (progress) {
    progress = false;
    for (let i=0;i work[j]) { can = false; break; }
      if (can) { for (let j=0;jf);
}

• Safe state: there exists some completion order without deadlock.
• Limitations: needs advance maxima; conservative; overhead significant.

• Detection: wait-for-graph cycles; periodically or on suspicion (timeouts).
• Recovery: kill/rollback a victim; preempt resources; checkpoint/restart for long-running jobs.
• Distributed: probe-based algorithms (Chandy–Misra–Haas); beware false detections due to asynchrony.

• Define and lint a global lock order; centralize lock rank assignments.
• Prefer fine-grained locks with clear ownership; minimize lock hold time.
• Use timeouts and deadlock detectors in debug builds; dump wait-for graphs on alert.
• Design APIs to avoid calling out while holding locks; split into acquire/use/release phases.

1. Implement a wait-for graph builder and cycle detector for a simulated system; test on random workloads.
2. Simulate Banker’s algorithm; generate random max/alloc/request matrices and evaluate admission decisions.
3. Instrument your codebase to log lock acquisitions/releases with ranks and verify ordering with a checker.