Stuck forever
Thread 1 holds lock *a* and waits for *b*; thread 2 holds *b* and waits for *a*. Neither can move — a deadlock. Draw who waits for whom as a graph: a deadlock is a cycle. The classic cure is a global lock order: if everyone takes *a* before *b*, no cycle can form.
Cycle detection
function findCycle(edges) {
const graph = {};
for (const [from, to] of edges) (graph[from] ??= []).push(to);
const state = {};
const path = [];
function visit(node) {
state[node] = "visiting";
path.push(node);
for (const next of graph[node] ?? []) {
if (state[next] === "visiting") return path.slice(path.indexOf(next)); // back edge: a cycle
if (!state[next]) {
const cycle = visit(next);
if (cycle) return cycle;
}
}
path.pop();
state[node] = "done";
return null;
}
for (const node of Object.keys(graph)) {
if (!state[node]) {
const cycle = visit(node);
if (cycle) return cycle;
}
}
return null;
}
function canDeadlock(threads) {
const edges = [];
for (const locks of Object.values(threads)) {
for (let i = 0; i + 1 < locks.length; i++) edges.push([locks[i], locks[i + 1]]); // holds i, wants i + 1
}
return findCycle(edges) !== null;
}