Introduction

Picture four philosophers sitting around a table, each holding one chopstick and waiting for the one to their right. Nobody can eat, nobody will let go, and the table stays frozen forever. That story, invented by Edsger Dijkstra in 1965, is the classic image of a deadlock.

In a real operating system, the philosophers are processes and the chopsticks are resources — files, locks, memory pages, network sockets. A deadlock forms when a set of processes is stuck in a circular wait: process A holds resource 1 and waits for resource 2, process B holds resource 2 and waits for resource 1, and neither can ever proceed.

The four conditions that must all hold simultaneously for a deadlock to exist were identified by Coffman, Elphick, and Shoshani in 1971:

  1. Mutual exclusion — a resource can be held by at most one process at a time.
  2. Hold and wait — a process holding a resource can request more.
  3. No preemption — resources can only be released voluntarily.
  4. Circular wait — a cycle exists in the wait-for graph.

Remove any one condition and deadlock is impossible. But in practice the first three are often unavoidable, so the question becomes: can we detect the circular wait before it brings the system down?

Try It: Build a Deadlock

Below is a wait-for graph: nodes are processes, and a directed edge from A to B means "A is waiting for a resource held by B." A deadlock exists if and only if this graph contains a directed cycle.

Add edges between processes to build a wait-for graph, then press Detect Deadlock to run depth-first search and find any cycle.

<!-- Wait-for graph demo — nodes=processes, edges=waiting relationships -->
<div class="hint">Each node is a process. A directed edge P1 → P2 means P1 is waiting for a resource held by P2. A <b>deadlock</b> exists when there is a directed cycle — every process in the cycle waits forever.</div>
<div class="controls">
  <label>From: <select id="sel-from"></select></label>
  <span class="arrow">&#8594;</span>
  <label>To: <select id="sel-to"></select></label>
  <button id="btn-add" type="button">Add edge</button>
  <button id="btn-remove" type="button">Remove edge</button>
</div>
<div class="canvas-wrap">
  <canvas id="cvs" width="500" height="300"></canvas>
</div>
<div id="edge-list" class="edge-list"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-detect" type="button">Detect Deadlock</button>
  <button id="btn-preset" type="button">Load deadlock example</button>
  <button id="btn-reset" type="button" class="ghost">Clear all</button>
</div>

/* Styles for the wait-for graph deadlock detector */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .6rem; font-size: .85rem; }
.controls label { display: flex; align-items: center; gap: .3rem; }
select { font-size: .85rem; padding: .2rem .4rem; border: 1px solid #cdd9e3; border-radius: 6px; background: #fff; }
.arrow { font-size: 1.2rem; color: #1d3557; }
.canvas-wrap { border: 1px solid #cdd9e3; border-radius: 10px; overflow: hidden; margin: .4rem 0; background: #f5f8fb; }
canvas { display: block; width: 100%; height: auto; }
.edge-list { font-size: .8rem; color: #555; min-height: 1.4em; margin: .2rem 0 .4rem; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d6fa0; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Deadlock detection via DFS cycle detection on the wait-for graph

// Process nodes in the wait-for graph
const NODES = ['P1','P2','P3','P4','P5'];
const NODE_COLORS = { normal: '#4a7bb7', cycle: '#e63946', checked: '#2e9e5b' };
// Canvas pixel positions for each node
const POS = { P1:[80,150], P2:[200,60], P3:[320,60], P4:[420,150], P5:[250,220] };

let edges = []; // Current directed edges (wait-for relationships)
let cycleNodes = new Set(); // Nodes that form a detected cycle
let cycleEdges = new Set(); // Edges that belong to the detected cycle
let detected = false;

const cvs = document.getElementById('cvs');
const ctx = cvs.getContext('2d');
const statusEl = document.getElementById('status');
const edgeListEl = document.getElementById('edge-list');
const selFrom = document.getElementById('sel-from');
const selTo = document.getElementById('sel-to');

// Populate the from/to dropdowns with process names
function populateSelects() {
  [selFrom, selTo].forEach(sel => {
    sel.innerHTML = '';
    NODES.forEach(n => { const o = document.createElement('option'); o.value = n; o.textContent = n; sel.appendChild(o); });
  });
  selTo.value = 'P2';
}
populateSelects();

function edgeKey(a, b) { return a + '->' + b; }

// Draw a directed arrow between two nodes
function drawArrow(x1, y1, x2, y2, color, highlight) {
  const dx = x2 - x1, dy = y2 - y1, len = Math.sqrt(dx*dx+dy*dy);
  if (len < 1) return;
  const ux = dx/len, uy = dy/len;
  const r = 22; // node radius in pixels
  const sx = x1 + ux*r, sy = y1 + uy*r;
  const ex = x2 - ux*r, ey = y2 - uy*r;
  ctx.save();
  ctx.strokeStyle = color;
  ctx.fillStyle = color;
  ctx.lineWidth = highlight ? 2.6 : 1.6;
  ctx.beginPath(); ctx.moveTo(sx, sy); ctx.lineTo(ex, ey); ctx.stroke();
  // Arrowhead triangle
  const headLen = 10, angle = Math.atan2(ey - sy, ex - sx);
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - headLen*Math.cos(angle-0.42), ey - headLen*Math.sin(angle-0.42));
  ctx.lineTo(ex - headLen*Math.cos(angle+0.42), ey - headLen*Math.sin(angle+0.42));
  ctx.closePath(); ctx.fill();
  ctx.restore();
}

// Redraw the entire canvas
function draw() {
  const W = cvs.width, H = cvs.height;
  ctx.clearRect(0, 0, W, H);

  // Draw all wait-for edges
  for (const e of edges) {
    const [x1,y1] = POS[e.from], [x2,y2] = POS[e.to];
    const key = edgeKey(e.from, e.to);
    const isCycle = cycleEdges.has(key);
    drawArrow(x1, y1, x2, y2, isCycle ? '#e63946' : '#6b8faf', isCycle);
  }

  // Draw all process nodes
  for (const n of NODES) {
    const [x, y] = POS[n];
    let color = NODE_COLORS.normal;
    if (cycleNodes.has(n)) color = NODE_COLORS.cycle;
    else if (detected) color = NODE_COLORS.checked;
    ctx.save();
    ctx.beginPath(); ctx.arc(x, y, 22, 0, 2*Math.PI);
    ctx.fillStyle = color; ctx.fill();
    ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();
    ctx.fillStyle = '#fff'; ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(n, x, y);
    ctx.restore();
  }
}

function updateEdgeList() {
  edgeListEl.textContent = edges.length
    ? i18nFmt('Edges: %list%', { list: edges.map(e => e.from+'→'+e.to).join(', ') })
    : 'No edges yet.';
}

// DFS-based cycle detection — runs in O(V+E) time
function detectCycle() {
  // Build adjacency list from the current edge set
  const adj = {};
  for (const n of NODES) adj[n] = [];
  for (const e of edges) adj[e.from].push(e.to);

  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = {}; NODES.forEach(n => color[n] = WHITE);
  const parent = {};
  let cycleStart = null, cycleEnd = null;

  function dfs(u) {
    color[u] = GRAY;
    for (const v of adj[u]) {
      if (color[v] === GRAY) { cycleStart = v; cycleEnd = u; return true; }
      if (color[v] === WHITE) { parent[v] = u; if (dfs(v)) return true; }
    }
    color[u] = BLACK; return false;
  }

  for (const n of NODES) { if (color[n] === WHITE && dfs(n)) break; }

  cycleNodes = new Set(); cycleEdges = new Set();
  if (cycleStart !== null) {
    // Walk parent pointers back to reconstruct the cycle path
    let cur = cycleEnd;
    while (cur !== cycleStart) { cycleNodes.add(cur); cur = parent[cur]; }
    cycleNodes.add(cycleStart);
    // Mark the directed edges that form the cycle
    cur = cycleEnd;
    while (cur !== cycleStart) {
      const p = parent[cur]; cycleEdges.add(edgeKey(p, cur)); cur = p;
    }
    cycleEdges.add(edgeKey(cycleEnd, cycleStart));
  }
  return cycleStart !== null;
}

document.getElementById('btn-add').addEventListener('click', () => {
  const f = selFrom.value, t = selTo.value;
  if (f === t) { setStatus('A process cannot wait for itself.', 'info'); return; }
  if (edges.some(e => e.from===f && e.to===t)) { setStatus('That edge already exists.', 'info'); return; }
  edges.push({ from: f, to: t });
  detected = false; cycleNodes = new Set(); cycleEdges = new Set();
  updateEdgeList(); draw(); setStatus('Edge added.', 'info');
});

document.getElementById('btn-remove').addEventListener('click', () => {
  const f = selFrom.value, t = selTo.value;
  const before = edges.length;
  edges = edges.filter(e => !(e.from===f && e.to===t));
  detected = false; cycleNodes = new Set(); cycleEdges = new Set();
  updateEdgeList(); draw();
  setStatus(edges.length < before ? 'Edge removed.' : 'No such edge exists.', 'info');
});

document.getElementById('btn-detect').addEventListener('click', () => {
  if (edges.length === 0) { setStatus('Add at least one edge first.', 'info'); return; }
  detected = true;
  const found = detectCycle();
  draw();
  if (found) {
    const cyc = [...cycleNodes].join(' → ');
    setStatus(i18nFmt('Deadlock detected! Cycle: %cycle%', { cycle: cyc }), 'bad');
  } else {
    setStatus('No deadlock — the wait-for graph is acyclic.', 'ok');
  }
});

document.getElementById('btn-preset').addEventListener('click', () => {
  // Classic 3-process deadlock P1->P2->P3->P1 with P4->P5 innocent
  edges = [
    { from: 'P1', to: 'P2' },
    { from: 'P2', to: 'P3' },
    { from: 'P3', to: 'P1' },
    { from: 'P4', to: 'P5' }
  ];
  detected = false; cycleNodes = new Set(); cycleEdges = new Set();
  updateEdgeList(); draw(); setStatus('Example loaded. Click Detect Deadlock to find the cycle.', 'info');
});

document.getElementById('btn-reset').addEventListener('click', () => {
  edges = []; detected = false; cycleNodes = new Set(); cycleEdges = new Set();
  updateEdgeList(); draw(); setStatus('', '');
});

function setStatus(t, cls) { statusEl.textContent = t; statusEl.className = 'status ' + cls; }

updateEdgeList(); draw(); setStatus('Add edges to build a wait-for graph, then click Detect Deadlock.', 'info');
Result
Console

Notice that detection is instant regardless of graph size: DFS visits every node and edge exactly once, running in O(V+E)O(V + E) time. The hard part is not detecting a deadlock — it is preventing one in the first place, which requires predicting the future.

The Real Complexity

Deadlock detection is a solved problem — and an elegantly cheap one.

  • Wait-for graph: model each process as a node; add a directed edge from P to Q whenever P waits for a resource Q holds. A deadlock exists if and only if this graph has a directed cycle.
  • Cycle detection via DFS runs in O(V+E)O(V + E) time, where VV is the number of processes and EE is the number of wait edges. Every modern OS deadlock detector is essentially this algorithm.
  • Resource-allocation graph: when resources can have multiple instances (e.g., three identical printers), the graph gets two kinds of nodes and the cycle rule alone is insufficient — you need a more careful reduction procedure, still polynomial.

Deadlock prevention and avoidance are where the real difficulty lives:

  • Prevention imposes a global ordering on all resource types and forces every process to request resources in that order, breaking the circular-wait condition. It is correct but can over-restrict concurrency.
  • Dijkstra's Banker's Algorithm (1965) maintains a "safe state" invariant: before granting any request, it simulates whether the resulting allocation can still finish all processes. If yes, grant; if not, make the process wait. This runs in O(n2⋅m)O(n^2 \cdot m) time for nn processes and mm resource types — still polynomial, but requires knowing the maximum claim of each process in advance, which many real programs cannot provide.
  • Deadlock recovery — killing a process or preempting a resource — is the brute-force fallback when detection fires.

The lesson is subtle: the question "is there a deadlock right now?" is easy (linear time). The question "will there ever be a deadlock, given what processes might request?" is far harder — it touches undecidability for fully general programs, which is why operating systems settle for heuristics and detection rather than perfect prevention. See also halting problem for why predicting program behavior in general is impossible.

Where It Matters

The circular-wait problem appears anywhere shared resources and concurrent access meet:

  • Database engines: every major RDBMS (PostgreSQL, MySQL, Oracle) runs a deadlock detector on its lock graph. When a cycle appears among transactions, one is chosen as the victim and rolled back, freeing the others to proceed. Without this, a simple pair of conflicting transactions would freeze the database forever.
  • Operating system kernels: the OS manages file locks, semaphores, and I/O devices. Linux's lock validator (lockdep) instruments every kernel lock acquisition to catch circular-wait patterns in development before they reach production.
  • Distributed systems: in a cluster, a process on machine A may wait for a resource held by a process on machine B, which in turn waits for machine C, which waits for A. Detecting this requires collecting wait-for edges from all nodes — a classic distributed algorithm problem.
  • Programming language runtimes: Go's runtime detects "all goroutines are asleep" deadlocks and panics immediately. Java's ThreadMXBean lets you query for deadlocked threads at runtime.
  • Concurrent data structures: lock-free and wait-free algorithms (used in high-performance caches and queues) eliminate deadlocks by design — at the cost of much more complex code.

Understanding deadlock detection also illuminates graph coloring and scheduling problems: whenever resources must be allocated without conflict, you are navigating the same terrain.

Conclusion

Deadlock detection is one of computer science's success stories: a frightening scenario — a system frozen forever — reduces to a single depth-first search on a graph. The algorithm is O(V+E)O(V + E), runs continuously in the background of every major database and OS, and reliably finds the culprit in milliseconds.

The deeper lesson is about the gap between detection and prevention. Catching a deadlock after it forms is easy. Guaranteeing one will never form requires knowing what resources every process will ever need — information that, for general programs, is as unknowable as the halting problem. So real systems settle for the practical middle ground: detect fast, recover cheaply, and use heuristics like the Banker's Algorithm when you can afford the bookkeeping.

Dijkstra's dining philosophers taught us that even simple rules — hold what you have, wait for the rest — can produce a collective impasse from which no individual can escape alone. The wait-for graph makes that impasse visible, and a DFS makes it decidable in an instant.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/deadlock-detection/Content licensed under CC BY-NC 4.0.