Operating Systems Module 6 – Deadlocks
Deadlock: conditions and resource graphs
What a deadlock is, the four Coffman conditions it needs, how resource-allocation and wait-for graphs expose one, and how livelock and starvation differ.
What you will learn
- State the four Coffman conditions and show that a deadlock needs all four
- Draw resource-allocation and wait-for graphs and find the cycle in them
- Decide whether a cycle means deadlock when a resource has several instances
- Distinguish deadlock, livelock and starvation
- Recognise the deadlocks that hide in lock order, callbacks and full thread pools
Before you start
What you’ll learn · Before you start
What you will learn
- State the four Coffman conditions and show that a deadlock needs all four
- Draw resource-allocation and wait-for graphs and find the cycle in them
- Decide whether a cycle means deadlock when a resource has several instances
- Distinguish deadlock, livelock and starvation
- Recognise the deadlocks that hide in lock order, callbacks and full thread pools
Before you start
On this page
Two threads move money between accounts 17 and 42 at the same moment: one locks account 17 and then 42, the other locks 42 and then 17. In the run below each took its first lock and then waited a full second for the other’s before giving up, and without that deadline both would still be waiting. That is a deadlock: A state in which every thread of a group waits for something that only another thread of the same group can do, such as releasing a lock, so none of them can ever go on.: every thread of a group waits for something that only another thread of the same group can do.
Deadlocks follow rules. Four conditions hold whenever one exists, a graph of who holds what and who waits for what shows it as a cycle, and a few code patterns produce nearly all of them. By the end of this page you can take any snapshot of threads and locks, name the threads that can never finish, and say which condition to break.
Two locks taken in opposite orders deadlock
two_locks.c runs the two transfers twice. In the first run a small meeting point makes each thread take its first lock before either thread asks for its second, the unlucky timing that a busy server reaches sooner or later. Each thread then asks for its second lock with pthread_mutex_trylock, which returns at once when the lock is taken, every millisecond for one second. In the second run both threads lock account 17 first:
// Two threads move money between accounts 17 and 42. When they take the two
// locks in opposite orders they deadlock; when both take lock 17 first, never.
#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>
static pthread_mutex_t locks[2] = {PTHREAD_MUTEX_INITIALIZER,
PTHREAD_MUTEX_INITIALIZER};
static const int account[2] = {17, 42};
static atomic_int holding, tried; // threads past each meeting point
typedef struct {
const char *name;
int first, second; // indexes into locks
bool meet; // wait until both threads hold their first lock
bool done;
} transfer;
static void meet(atomic_int *count) {
atomic_fetch_add(count, 1);
while (atomic_load(count) < 2)
sched_yield();
}
// Tries the lock every millisecond for a second instead of waiting for ever.
static bool lock_within_a_second(pthread_mutex_t *m) {
for (int i = 0; i < 1000; i++) {
if (pthread_mutex_trylock(m) == 0)
return true;
nanosleep(&(struct timespec){.tv_nsec = 1000000}, NULL);
}
return false;
}
static void *run(void *arg) {
transfer *t = arg;
pthread_mutex_lock(&locks[t->first]);
if (t->meet)
meet(&holding);
t->done = lock_within_a_second(&locks[t->second]);
if (t->meet)
meet(&tried); // neither lets go before both have tried
if (t->done)
pthread_mutex_unlock(&locks[t->second]);
pthread_mutex_unlock(&locks[t->first]);
return NULL;
}
static void race(const char *title, transfer pair[2]) {
pthread_t threads[2];
for (int i = 0; i < 2; i++)
pthread_create(&threads[i], NULL, run, &pair[i]);
for (int i = 0; i < 2; i++)
pthread_join(threads[i], NULL);
puts(title);
for (int i = 0; i < 2; i++) {
const transfer *t = &pair[i];
if (t->done)
printf(" %s locked %d, then %d: transfer done\n", t->name,
account[t->first], account[t->second]);
else
printf(" %s locked %d, then waited 1 s for %d: gave up\n", t->name,
account[t->first], account[t->second]);
}
}
int main(void) {
race("opposite orders, both first locks taken before either second one:",
(transfer[2]){{"A", 0, 1, true, false}, {"B", 1, 0, true, false}});
race("one order, lock 17 first in both threads:",
(transfer[2]){{"A", 0, 1, false, false}, {"B", 0, 1, false, false}});
return 0;
}Output
opposite orders, both first locks taken before either second one: A locked 17, then waited 1 s for 42: gave up B locked 42, then waited 1 s for 17: gave up one order, lock 17 first in both threads: A locked 17, then 42: transfer done B locked 17, then 42: transfer done
Recorded with Apple clang version 21.0.0 (clang-2100.3.34.2) on macOS 26 arm64. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined two_locks.c -o two_locks && ./two_locks
In the first run both threads gave up. For a whole second each held one lock and waited for the other, and neither could go on, because each was waiting for a lock that only the other could release and neither releases a lock while it waits. Taking both locks in one order made the same transfers finish. A plain pthread_mutex_lock has no deadline at all: it would have waited for ever. POSIX offers pthread_mutex_timedlock and pthread_mutex_clocklock, which wait until a deadline and then return ETIMEDOUT.
Dijkstra called this state a deadly embrace. Step through the first run, drawn the way the rest of this lesson draws every snapshot, with an arrow for each lock a thread holds and a dashed arrow for each lock it wants:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- Two transfers start. Thread A moves money from account 17 to account 42, and thread B moves money the other way. Each transfer needs both accounts' locks, and each thread locks the account it takes money from first.
- A locks account 17. A takes the lock of account 17. In a resource-allocation graph, an arrow from a resource to a thread is an assignment edge, which says that the thread holds it.
- B locks account 42. At the same moment B takes the lock of account 42. Both first locks are now taken, which is the interleaving the program forces before either thread asks for its second lock.
- A asks for lock 42. A needs the lock of account 42 too. An arrow from a thread to a resource is a request edge, which says that the thread waits for it. A sleeps until lock 42 is free and keeps lock 17 meanwhile.
- B asks for lock 17. B needs the lock of account 17, which A holds. The four arrows now form a loop, A to lock 42 to B to lock 17 and back to A.
- A cycle, so nobody moves. Follow any arrow and you come back to where you started. Each thread waits for a lock that only the other thread can release, and neither releases while it waits, so both would wait for ever.
- Both give up after a second. In two_locks.c each thread tries its second lock for one second, then gives up and releases its first lock, which ends the wait by dropping the transfer. A plain lock call has no such deadline.
Four arrows were enough: each thread held one lock and wanted the other’s, and following the arrows led back to the start. The next sections turn that loop into a rule you can check.
A deadlock needs all four Coffman conditions
In 1971 Coffman, Elphick and Shoshani described four conditions that hold whenever a deadlock exists, now called the Coffman conditions: The four conditions that hold whenever a deadlock exists: mutual exclusion, hold and wait, no preemption and circular wait. Removing any one of them prevents deadlock.. All four are visible in the first run of two_locks.c:
| Condition | In the first run of two_locks.c | Without it |
|---|---|---|
| mutual exclusion: The guarantee that at most one thread is inside a given critical section at any moment. More in “Race conditions and the critical-section problem” | A mutex has one owner at a time, so lock 17 cannot serve A and B together | A resource that every thread may use at once makes nobody wait for it |
| hold and wait: A condition for deadlock: a thread keeps the resources it already holds while it waits for another one. | A keeps lock 17 while it waits for lock 42 | A thread that waits while holding nothing blocks no other thread |
| No preemption | Nothing can take lock 17 away from A, and only a mutex’s owner may release it | The system could take one lock back from a waiting thread and let the other finish |
| circular wait: A condition for deadlock: a closed chain of threads in which each one waits for a resource that the next one holds. | A waits for B, and B waits for A | Some waiting thread waits for a thread that is not waiting, which finishes and lets the chain move |
The last column is the proof that a deadlock needs all four. Take away mutual exclusion and nobody waits; take away hold and wait and a waiting thread is no obstacle to anyone; allow preemption and the system can break the wait by force. Take away circular wait and every chain of waiting threads ends at a thread that is not waiting: that thread runs to its end and releases what it holds, then the thread behind it can go on, and so on down the chain.
The first three conditions describe how resources are handed out, and ordinary locks meet all three. Circular wait describes the state that the threads reach, which is why the second run worked: when every thread takes the two locks in the same order, no thread can hold the later lock while waiting for the earlier one, so no cycle can form. When each resource has one instance, the four conditions are also enough: a circular wait among such locks is a deadlock.
Key idea
A deadlock needs mutual exclusion, hold and wait, no preemption and a circular wait at the same time. Take away any one of them and the waiting can always end.
Checkpoint
Check: Deadlock from two locks taken in opposite orders · The four Coffman conditions
A resource-allocation graph shows who holds and who waits
The picture in the first section is a resource-allocation graph: A graph of threads and resources in which an arrow from a thread to a resource is a request and an arrow from a resource to a thread means that the thread holds it., the graph model that Holt described in 1972. Each thread is a circle and each resource a box with one dot per instance. An arrow from a thread to a resource is a request, the thread waits for it; an arrow from a resource to a thread means the thread holds it. When every resource has a single instance, each request points through the resource at exactly one holder, and the resources can be left out: an arrow from thread A to thread B then says that A waits for a lock B holds. That smaller drawing is the wait-for graph: A graph with an arrow from each waiting thread to the thread that holds what it waits for. When every resource has one instance, a cycle in it is a deadlock., and its cycles are the cycles of the resource-allocation graph.
A server snapshot with five threads and four locks:
| Thread | Holds | Waits for | So it waits for |
|---|---|---|---|
| A | log | cache | B |
| B | cache | index | C |
| C | index | log | A |
| D | nothing | stats | E |
| E | stats | nothing | nobody |
A cycle is easy to see among five threads and hard to see among five hundred, so a program looks for it the other way round: it finishes every thread that can finish. A thread that waits for nobody can run to its end and release its locks, and then every thread that waited only for it can run too. Whatever never finishes is deadlocked.
The figure runs that idea on the server as Kahn’s topological sort. Each arrow points from a thread to the thread waiting for it, so read it as “finishes before”. The label “in 1” means the thread still waits for one other thread, and a thread with no arrow left pointing in is ready to finish:
- being compared or looked at
- being moved or written
- in its final place
- the key, pivot or target
- visited or ruled out
Pseudo-code
-
indeg(v) ← the number of edges into v -
queue ← every node with indeg 0 -
while the queue is not empty: -
u ← dequeue; append u to the order -
for each edge u → v: indeg(v) ← indeg(v) − 1; if it is 0: enqueue v -
if the order misses a node: the graph has a cycle
Order the tasks so that every arrow points forwards. "in k" is a node's in-degree: how many arrows still point into it. Nodes with nothing left pointing in are ready: E.
When it finishes: No order: the graph has a cycle.
Try your own input
E waits for nobody, so it finishes and releases the stats lock, and then D can take it and finish. A, B and C each wait for the next one, so none of them ever becomes ready, and the run ends with the three of them on a cycle: they are the deadlocked threads. The program below does the same for four snapshots, in 14 languages. It reads each one as its wait-for graph, the last column of the table, and once nothing more can finish it follows the waits from the first stuck thread until a thread repeats, and prints that cycle:
Python 3.14 · main.py
# Each thread and the thread it waits for (None: nobody).
SERVER = [("A", "B"), ("B", "C"), ("C", "A"), ("D", "E"), ("E", None)]
SNAPSHOTS = [
("opposite orders", [("A", "B"), ("B", "A")]),
("same order", [("A", None), ("B", "A")]),
("server", SERVER),
("server and F", SERVER + [("F", "A")]),
]
def analyse(waits: dict[str, str | None]) -> None:
# A thread that waits for nobody can finish and release its locks.
ready = [t for t, holder in waits.items() if holder is None]
finished: list[str] = []
while ready:
done = ready.pop(0)
finished.append(done)
ready += [t for t, holder in waits.items() if holder == done]
stuck = [t for t in waits if t not in finished]
print(" can finish:", ", ".join(finished) or "none")
if not stuck:
print(" deadlocked: none")
return
# Every stuck thread waits for another stuck thread, so following them must loop.
path = [stuck[0]]
while waits[path[-1]] not in path:
path.append(waits[path[-1]])
loop = path[path.index(waits[path[-1]]) :]
print(f" deadlocked: {', '.join(stuck)} (cycle {' -> '.join(loop + loop[:1])})")
for title, threads in SNAPSHOTS:
print(title)
analyse(dict(threads))In Python: dict(threads) keeps the snapshot's order, so the threads that can finish are found in the order the table lists them, and waits[path[-1]] reads who the last thread on the path waits for.
Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
// Each thread and the thread it waits for (null: nobody).
const SERVER = { A: "B", B: "C", C: "A", D: "E", E: null };
const SNAPSHOTS = {
"opposite orders": { A: "B", B: "A" },
"same order": { A: null, B: "A" },
server: SERVER,
"server and F": { ...SERVER, F: "A" },
};
function analyse(waits) {
// A thread that waits for nobody can finish and release its locks.
const ready = [...waits.keys()].filter((t) => waits.get(t) === null);
const finished = [];
while (ready.length > 0) {
const done = ready.shift();
finished.push(done);
ready.push(...[...waits.keys()].filter((t) => waits.get(t) === done));
}
const stuck = [...waits.keys()].filter((t) => !finished.includes(t));
console.log(` can finish: ${finished.join(", ") || "none"}`);
if (stuck.length === 0) {
console.log(" deadlocked: none");
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
const path = [stuck[0]];
const next = () => waits.get(path[path.length - 1]);
while (!path.includes(next())) path.push(next());
const loop = path.slice(path.indexOf(next()));
console.log(` deadlocked: ${stuck.join(", ")} (cycle ${[...loop, loop[0]].join(" -> ")})`);
}
for (const [title, threads] of Object.entries(SNAPSHOTS)) {
console.log(title);
analyse(new Map(Object.entries(threads)));
}In JavaScript: Object.entries turns each snapshot into a Map in the order its keys were written; a thread name like "A" is not an integer key, so that order is kept.
Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs
Java 25 LTS · Main.java
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Main {
static void analyse(Map<String, String> waits) {
// A thread that waits for nobody can finish and release its locks.
List<String> ready = new ArrayList<>();
waits.forEach(
(t, holder) -> {
if (holder == null) ready.add(t);
});
List<String> finished = new ArrayList<>();
while (!ready.isEmpty()) {
String done = ready.remove(0);
finished.add(done);
waits.forEach(
(t, holder) -> {
if (done.equals(holder)) ready.add(t);
});
}
List<String> stuck = new ArrayList<>(waits.keySet());
stuck.removeAll(finished);
System.out.println(
" can finish: " + (finished.isEmpty() ? "none" : String.join(", ", finished)));
if (stuck.isEmpty()) {
System.out.println(" deadlocked: none");
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
List<String> path = new ArrayList<>(List.of(stuck.get(0)));
while (!path.contains(waits.get(path.get(path.size() - 1)))) {
path.add(waits.get(path.get(path.size() - 1)));
}
String start = waits.get(path.get(path.size() - 1));
List<String> loop = new ArrayList<>(path.subList(path.indexOf(start), path.size()));
loop.add(start);
System.out.println(
" deadlocked: " + String.join(", ", stuck) + " (cycle " + String.join(" -> ", loop) + ")");
}
/** Each thread and the thread it waits for (null: nobody). */
static Map<String, String> threads(String... pairs) {
Map<String, String> waits = new LinkedHashMap<>();
for (int i = 0; i < pairs.length; i += 2) waits.put(pairs[i], pairs[i + 1]);
return waits;
}
public static void main(String[] args) {
String[] server = {"A", "B", "B", "C", "C", "A", "D", "E", "E", null};
Map<String, Map<String, String>> snapshots = new LinkedHashMap<>();
snapshots.put("opposite orders", threads("A", "B", "B", "A"));
snapshots.put("same order", threads("A", null, "B", "A"));
snapshots.put("server", threads(server));
Map<String, String> withF = threads(server);
withF.put("F", "A");
snapshots.put("server and F", withF);
snapshots.forEach(
(title, waits) -> {
System.out.println(title);
analyse(waits);
});
}
}In Java: A LinkedHashMap keeps the insertion order that the output depends on, and done.equals(holder) is called on done because holder is null for a thread that waits for nobody.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
#include <algorithm>
#include <optional>
#include <print>
#include <string>
#include <utility>
#include <vector>
// Each thread and the thread it waits for (std::nullopt: nobody).
using Threads = std::vector<std::pair<char, std::optional<char>>>;
std::string join(const std::string &names, const char *sep) {
std::string out;
for (const char t : names)
out += (out.empty() ? "" : sep) + std::string(1, t);
return out;
}
void analyse(const Threads &threads) {
// A thread that waits for nobody can finish and release its locks.
std::string ready, finished, stuck;
for (const auto &[t, holder] : threads)
if (!holder)
ready += t;
while (!ready.empty()) {
const char done = ready.front();
ready.erase(0, 1);
finished += done;
for (const auto &[t, holder] : threads)
if (holder == done)
ready += t;
}
for (const auto &[t, holder] : threads)
if (!finished.contains(t))
stuck += t;
std::println(" can finish: {}",
finished.empty() ? "none" : join(finished, ", "));
if (stuck.empty()) {
std::println(" deadlocked: none");
return;
}
// Every stuck thread waits for another stuck thread, so following them must
// loop.
auto holder_of = [&](char t) {
return std::ranges::find(threads, t, &Threads::value_type::first)
->second.value();
};
std::string path(1, stuck.front());
while (!path.contains(holder_of(path.back())))
path += holder_of(path.back());
std::string loop = path.substr(path.find(holder_of(path.back())));
loop += loop.front();
std::println(" deadlocked: {} (cycle {})", join(stuck, ", "),
join(loop, " -> "));
}
int main() {
const Threads server = {
{'A', 'B'}, {'B', 'C'}, {'C', 'A'}, {'D', 'E'}, {'E', std::nullopt}};
Threads with_f = server;
with_f.push_back({'F', 'A'});
const std::vector<std::pair<std::string, Threads>> snapshots = {
{"opposite orders", {{'A', 'B'}, {'B', 'A'}}},
{"same order", {{'A', std::nullopt}, {'B', 'A'}}},
{"server", server},
{"server and F", with_f}};
for (const auto &[title, threads] : snapshots) {
std::println("{}", title);
analyse(threads);
}
}In C++: Thread names are single chars, so a std::string holds each list of threads and contains() and find() search it; std::optional<char> marks a thread that waits for nobody.
Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main
C# 14 · .NET 10 · app.cs
// Each thread and the thread it waits for (null: nobody).
(string Thread, string? Holder)[] server =
[("A", "B"), ("B", "C"), ("C", "A"), ("D", "E"), ("E", null)];
(string Title, (string Thread, string? Holder)[] Threads)[] snapshots =
[
("opposite orders", [("A", "B"), ("B", "A")]),
("same order", [("A", null), ("B", "A")]),
("server", server),
("server and F", [.. server, ("F", "A")]),
];
foreach (var (title, threads) in snapshots)
{
Console.WriteLine(title);
Analyse(threads);
}
static void Analyse((string Thread, string? Holder)[] threads)
{
// A thread that waits for nobody can finish and release its locks.
var ready = new Queue<string>(threads.Where(t => t.Holder is null).Select(t => t.Thread));
var finished = new List<string>();
while (ready.TryDequeue(out var done))
{
finished.Add(done);
foreach (var t in threads.Where(t => t.Holder == done))
{
ready.Enqueue(t.Thread);
}
}
var stuck = threads.Select(t => t.Thread).Except(finished).ToList();
var canFinish = finished.Count == 0 ? "none" : string.Join(", ", finished);
Console.WriteLine($" can finish: {canFinish}");
if (stuck.Count == 0)
{
Console.WriteLine(" deadlocked: none");
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
var waits = threads.ToDictionary(t => t.Thread, t => t.Holder ?? t.Thread);
var path = new List<string> { stuck[0] };
while (!path.Contains(waits[path[^1]]))
{
path.Add(waits[path[^1]]);
}
var loop = path.Skip(path.IndexOf(waits[path[^1]])).ToList();
loop.Add(loop[0]);
var cycle = string.Join(" -> ", loop);
Console.WriteLine($" deadlocked: {string.Join(", ", stuck)} (cycle {cycle})");
}In C#: The snapshot is an array of named tuples, Except keeps the stuck threads in the snapshot's order, and the dictionary maps a thread that waits for nobody to itself.
Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs
C23 · main.c
#include <stddef.h>
#include <stdio.h>
#include <string.h>
// Each thread and the thread it waits for (a space: nobody).
typedef struct {
const char *title;
const char *threads, *holders;
} snapshot;
static void print_names(const char *names, size_t n, const char *sep) {
for (size_t i = 0; i < n; i++)
printf("%s%c", i > 0 ? sep : "", names[i]);
}
static void analyse(const char *threads, const char *holders) {
const size_t n = strlen(threads);
char ready[8] = "", finished[8] = "", stuck[8] = "", path[9] = "";
size_t head = 0, tail = 0, n_finished = 0, n_stuck = 0, n_path = 0;
// A thread that waits for nobody can finish and release its locks.
for (size_t i = 0; i < n; i++)
if (holders[i] == ' ')
ready[tail++] = threads[i];
while (head < tail) {
const char done = ready[head++];
finished[n_finished++] = done;
for (size_t i = 0; i < n; i++)
if (holders[i] == done)
ready[tail++] = threads[i];
}
for (size_t i = 0; i < n; i++)
if (memchr(finished, threads[i], n_finished) == NULL)
stuck[n_stuck++] = threads[i];
printf(" can finish: %s", n_finished == 0 ? "none" : "");
print_names(finished, n_finished, ", ");
if (n_stuck == 0) {
printf("\n deadlocked: none\n");
return;
}
// Every stuck thread waits for another stuck thread, so following them must
// loop.
path[n_path++] = stuck[0];
char next = holders[strchr(threads, stuck[0]) - threads];
while (memchr(path, next, n_path) == NULL) {
path[n_path++] = next;
next = holders[strchr(threads, next) - threads];
}
const size_t start = (size_t)((char *)memchr(path, next, n_path) - path);
path[n_path++] = next;
printf("\n deadlocked: ");
print_names(stuck, n_stuck, ", ");
printf(" (cycle ");
print_names(path + start, n_path - start, " -> ");
printf(")\n");
}
int main(void) {
static const snapshot snapshots[] = {{"opposite orders", "AB", "BA"},
{"same order", "AB", " A"},
{"server", "ABCDE", "BCAE "},
{"server and F", "ABCDEF", "BCAE A"}};
for (size_t i = 0; i < sizeof snapshots / sizeof snapshots[0]; i++) {
printf("%s\n", snapshots[i].title);
analyse(snapshots[i].threads, snapshots[i].holders);
}
return 0;
}In C: Each snapshot is two strings, the threads and, at the same position, the thread each one waits for, with a space for nobody; memchr and strchr do the searching.
Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main
PHP 8.5 · main.php
<?php
declare(strict_types=1);
/**
* Each thread and the thread it waits for (null: nobody).
*
* @param array<string, ?string> $waits
*/
function analyse(array $waits): void
{
// A thread that waits for nobody can finish and release its locks.
$ready = array_keys($waits, null, true);
$finished = [];
while ($ready !== []) {
$done = array_shift($ready);
$finished[] = $done;
array_push($ready, ...array_keys($waits, $done, true));
}
$stuck = array_values(array_diff(array_keys($waits), $finished));
echo ' can finish: ', $finished === [] ? 'none' : implode(', ', $finished), "\n";
if ($stuck === []) {
echo " deadlocked: none\n";
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
$path = [$stuck[0]];
while (!in_array($waits[end($path)], $path, true)) {
$path[] = $waits[end($path)];
}
$loop = array_slice($path, (int) array_search($waits[end($path)], $path, true));
$loop[] = $loop[0];
echo ' deadlocked: ', implode(', ', $stuck), ' (cycle ', implode(' -> ', $loop), ")\n";
}
$server = ['A' => 'B', 'B' => 'C', 'C' => 'A', 'D' => 'E', 'E' => null];
$snapshots = [
'opposite orders' => ['A' => 'B', 'B' => 'A'],
'same order' => ['A' => null, 'B' => 'A'],
'server' => $server,
'server and F' => $server + ['F' => 'A'],
];
foreach ($snapshots as $title => $waits) {
echo $title, "\n";
analyse($waits);
}In PHP: array_keys($waits, null, true) finds the threads whose holder is exactly null, and the + operator appends F to a copy of the server snapshot.
Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php
Rust 1.99 · main.rs
/// Each thread and the thread it waits for (None: nobody).
type Threads<'a> = [(&'a str, Option<&'a str>)];
fn analyse(threads: &Threads) {
// A thread that waits for nobody can finish and release its locks.
let mut ready: Vec<&str> = threads
.iter()
.filter(|(_, h)| h.is_none())
.map(|(t, _)| *t)
.collect();
let mut finished = Vec::new();
while !ready.is_empty() {
let done = ready.remove(0);
finished.push(done);
ready.extend(
threads
.iter()
.filter(|(_, h)| *h == Some(done))
.map(|(t, _)| *t),
);
}
let stuck: Vec<&str> = threads
.iter()
.map(|(t, _)| *t)
.filter(|t| !finished.contains(t))
.collect();
let can = if finished.is_empty() {
"none".to_string()
} else {
finished.join(", ")
};
println!(" can finish: {can}");
let Some(&first) = stuck.first() else {
println!(" deadlocked: none");
return;
};
// Every stuck thread waits for another stuck thread, so following them must loop.
let holder = |t: &str| {
threads
.iter()
.find(|(name, _)| *name == t)
.and_then(|(_, h)| *h)
};
let mut path = vec![first];
let mut next = holder(first).unwrap_or(first);
while !path.contains(&next) {
path.push(next);
next = holder(next).unwrap_or(next);
}
let mut cycle = path.split_off(path.iter().position(|&t| t == next).unwrap_or(0));
cycle.push(next);
println!(
" deadlocked: {} (cycle {})",
stuck.join(", "),
cycle.join(" -> ")
);
}
fn main() {
let server = [
("A", Some("B")),
("B", Some("C")),
("C", Some("A")),
("D", Some("E")),
("E", None),
];
let mut with_f = server.to_vec();
with_f.push(("F", Some("A")));
let snapshots = [
("opposite orders", vec![("A", Some("B")), ("B", Some("A"))]),
("same order", vec![("A", None), ("B", Some("A"))]),
("server", server.to_vec()),
("server and F", with_f),
];
for (title, threads) in &snapshots {
println!("{title}");
analyse(threads);
}
}In Rust: Option<&str> marks a thread that waits for nobody, and split_off cuts the path at the thread where the cycle starts, so only the cycle is left in the second half.
Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main
TypeScript 6.0 · main.ts
// Each thread and the thread it waits for (null: nobody).
type Threads = Record<string, string | null>;
const SERVER: Threads = { A: "B", B: "C", C: "A", D: "E", E: null };
const SNAPSHOTS: Record<string, Threads> = {
"opposite orders": { A: "B", B: "A" },
"same order": { A: null, B: "A" },
server: SERVER,
"server and F": { ...SERVER, F: "A" },
};
function analyse(waits: Map<string, string | null>): void {
// A thread that waits for nobody can finish and release its locks.
const ready = [...waits.keys()].filter((t) => waits.get(t) === null);
const finished: string[] = [];
for (let done = ready.shift(); done !== undefined; done = ready.shift()) {
finished.push(done);
ready.push(...[...waits.keys()].filter((t) => waits.get(t) === done));
}
const stuck = [...waits.keys()].filter((t) => !finished.includes(t));
console.log(` can finish: ${finished.join(", ") || "none"}`);
if (stuck.length === 0) {
console.log(" deadlocked: none");
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
const path = [stuck[0]];
const next = (): string => waits.get(path[path.length - 1]) ?? "";
while (!path.includes(next())) path.push(next());
const loop = path.slice(path.indexOf(next()));
console.log(` deadlocked: ${stuck.join(", ")} (cycle ${[...loop, loop[0]].join(" -> ")})`);
}
for (const [title, threads] of Object.entries(SNAPSHOTS)) {
console.log(title);
analyse(new Map(Object.entries(threads)));
}In TypeScript: A Record type describes each snapshot, and next() falls back to an empty string so that path stays a string[] under strict mode.
Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts
Go 1.27 · main.go
package main
import (
"fmt"
"slices"
"strings"
)
// Each thread and the thread it waits for ("": nobody).
type waiting struct{ thread, holder string }
func analyse(threads []waiting) {
// A thread that waits for nobody can finish and release its locks.
var ready, finished, stuck []string
for _, w := range threads {
if w.holder == "" {
ready = append(ready, w.thread)
}
}
for len(ready) > 0 {
done := ready[0]
ready = ready[1:]
finished = append(finished, done)
for _, w := range threads {
if w.holder == done {
ready = append(ready, w.thread)
}
}
}
holders := map[string]string{}
for _, w := range threads {
holders[w.thread] = w.holder
if !slices.Contains(finished, w.thread) {
stuck = append(stuck, w.thread)
}
}
if len(finished) == 0 {
finished = []string{"none"}
}
fmt.Println(" can finish:", strings.Join(finished, ", "))
if len(stuck) == 0 {
fmt.Println(" deadlocked: none")
return
}
// Every stuck thread waits for another stuck thread, so following them must loop.
path := []string{stuck[0]}
for !slices.Contains(path, holders[path[len(path)-1]]) {
path = append(path, holders[path[len(path)-1]])
}
loop := slices.Clone(path[slices.Index(path, holders[path[len(path)-1]]):])
loop = append(loop, loop[0])
fmt.Printf(" deadlocked: %s (cycle %s)\n",
strings.Join(stuck, ", "), strings.Join(loop, " -> "))
}
func main() {
server := []waiting{{"A", "B"}, {"B", "C"}, {"C", "A"}, {"D", "E"}, {"E", ""}}
snapshots := []struct {
title string
threads []waiting
}{
{"opposite orders", []waiting{{"A", "B"}, {"B", "A"}}},
{"same order", []waiting{{"A", ""}, {"B", "A"}}},
{"server", server},
{"server and F", append(slices.Clone(server), waiting{"F", "A"})},
}
for _, s := range snapshots {
fmt.Println(s.title)
analyse(s.threads)
}
}In Go: Go's maps have no order, so each snapshot is a slice of structs; an empty string marks a thread that waits for nobody.
Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
// Each thread and the thread it waits for (nil: nobody).
typealias Threads = [(thread: String, holder: String?)]
func analyse(_ threads: Threads) {
// A thread that waits for nobody can finish and release its locks.
var ready = threads.filter { $0.holder == nil }.map(\.thread)
var finished: [String] = []
while !ready.isEmpty {
let done = ready.removeFirst()
finished.append(done)
ready += threads.filter { $0.holder == done }.map(\.thread)
}
let stuck = threads.map(\.thread).filter { !finished.contains($0) }
print(" can finish: \(finished.isEmpty ? "none" : finished.joined(separator: ", "))")
guard let first = stuck.first else {
print(" deadlocked: none")
return
}
// Every stuck thread waits for another stuck thread, so following them must loop.
func holder(of thread: String) -> String {
threads.first { $0.thread == thread }?.holder ?? thread
}
var path = [first]
while !path.contains(holder(of: path[path.count - 1])) {
path.append(holder(of: path[path.count - 1]))
}
let start = holder(of: path[path.count - 1])
let loop = path[(path.firstIndex(of: start) ?? 0)...] + [start]
print(" deadlocked: \(stuck.joined(separator: ", ")) (cycle \(loop.joined(separator: " -> ")))")
}
let server: Threads = [("A", "B"), ("B", "C"), ("C", "A"), ("D", "E"), ("E", nil)]
let snapshots: [(title: String, threads: Threads)] = [
("opposite orders", [("A", "B"), ("B", "A")]),
("same order", [("A", nil), ("B", "A")]),
("server", server),
("server and F", server + [("F", "A")]),
]
for snapshot in snapshots {
print(snapshot.title)
analyse(snapshot.threads)
}In Swift: A snapshot is an array of labelled tuples, and holder(of:) is a nested function that searches it, falling back to the thread itself instead of force-unwrapping.
Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main
Ruby 4.0 · main.rb
# frozen_string_literal: true
# A thread that waits for nobody can finish and release its locks.
def finish_order(waits)
ready = waits.select { |_, holder| holder.nil? }.keys
finished = []
until ready.empty?
done = ready.shift
finished << done
ready.concat(waits.select { |_, holder| holder == done }.keys)
end
finished
end
# Every stuck thread waits for another stuck thread, so following them must loop.
def cycle_from(first, waits)
path = [first]
path << waits[path.last] until path.include?(waits[path.last])
loop = path.drop(path.index(waits[path.last]))
loop << loop.first
end
def analyse(waits)
finished = finish_order(waits)
stuck = waits.keys - finished
puts " can finish: #{finished.empty? ? 'none' : finished.join(', ')}"
return puts(' deadlocked: none') if stuck.empty?
puts " deadlocked: #{stuck.join(', ')} (cycle #{cycle_from(stuck.first, waits).join(' -> ')})"
end
# Each thread and the thread it waits for (nil: nobody).
server = { 'A' => 'B', 'B' => 'C', 'C' => 'A', 'D' => 'E', 'E' => nil }
{
'opposite orders' => { 'A' => 'B', 'B' => 'A' },
'same order' => { 'A' => nil, 'B' => 'A' },
'server' => server,
'server and F' => server.merge('F' => 'A')
}.each do |title, waits|
puts title
analyse(waits)
endIn Ruby: RuboCop keeps a method to ten lines, so the finishing and the cycle are separate methods; waits.keys - finished keeps the snapshot's order.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
fun analyse(waits: Map<String, String?>) {
// A thread that waits for nobody can finish and release its locks.
val ready = ArrayDeque(waits.filterValues { it == null }.keys)
val finished = mutableListOf<String>()
while (ready.isNotEmpty()) {
val done = ready.removeFirst()
finished += done
ready.addAll(waits.filterValues { it == done }.keys)
}
val stuck = waits.keys - finished.toSet()
println(" can finish: ${if (finished.isEmpty()) "none" else finished.joinToString(", ")}")
if (stuck.isEmpty()) {
println(" deadlocked: none")
return
}
// Every stuck thread waits for another stuck thread, so following them must loop.
val path = mutableListOf(stuck.first())
var next = waits.getValue(path.last()) ?: path.last()
while (next !in path) {
path += next
next = waits.getValue(next) ?: next
}
val loop = path.drop(path.indexOf(next))
val cycle = (loop + loop.first()).joinToString(" -> ")
println(" deadlocked: ${stuck.joinToString(", ")} (cycle $cycle)")
}
fun main() {
// Each thread and the thread it waits for (null: nobody).
val server = linkedMapOf("A" to "B", "B" to "C", "C" to "A", "D" to "E", "E" to null)
val snapshots =
listOf(
"opposite orders" to mapOf("A" to "B", "B" to "A"),
"same order" to mapOf("A" to null, "B" to "A"),
"server" to server,
"server and F" to server + ("F" to "A"),
)
for ((title, waits) in snapshots) {
println(title)
analyse(waits)
}
}In Kotlin: filterValues keeps the map's insertion order, and getValue(next) ?: next keeps the walk free of null without an assertion, since a stuck thread always waits for another one.
Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
Dart 3.13 · main.dart
// Each thread and the thread it waits for (null: nobody).
void analyse(Map<String, String?> waits) {
// A thread that waits for nobody can finish and release its locks.
final ready = [
for (final MapEntry(:key, :value) in waits.entries)
if (value == null) key,
];
final finished = <String>[];
while (ready.isNotEmpty) {
final done = ready.removeAt(0);
finished.add(done);
ready.addAll([
for (final MapEntry(:key, :value) in waits.entries)
if (value == done) key,
]);
}
final stuck = [
for (final t in waits.keys)
if (!finished.contains(t)) t,
];
print(' can finish: ${finished.isEmpty ? 'none' : finished.join(', ')}');
if (stuck.isEmpty) {
print(' deadlocked: none');
return;
}
// Every stuck thread waits for another stuck thread, so following them must loop.
final path = [stuck.first];
var next = waits[path.last] ?? path.last;
while (!path.contains(next)) {
path.add(next);
next = waits[next] ?? next;
}
final loop = [...path.sublist(path.indexOf(next)), next];
print(' deadlocked: ${stuck.join(', ')} (cycle ${loop.join(' -> ')})');
}
void main() {
final server = {'A': 'B', 'B': 'C', 'C': 'A', 'D': 'E', 'E': null};
final snapshots = {
'opposite orders': {'A': 'B', 'B': 'A'},
'same order': {'A': null, 'B': 'A'},
'server': server,
'server and F': {...server, 'F': 'A'},
};
snapshots.forEach((title, waits) {
print(title);
analyse(waits);
});
}In Dart: Map literals keep their insertion order, and MapEntry patterns in the collection-for pick each thread with its holder.
Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart
What every language printed
opposite orders can finish: none deadlocked: A, B (cycle A -> B -> A) same order can finish: A, B deadlocked: none server can finish: E, D deadlocked: A, B, C (cycle A -> B -> C -> A) server and F can finish: E, D deadlocked: A, B, C, F (cycle A -> B -> C -> A)
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 13 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 153 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 4 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 9 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 21 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 723 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 200 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 15 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
The server’s answer matches the figure: E and D finish, and A, B and C are deadlocked around A -> B -> C -> A. In the last snapshot F is not on the cycle, but it waits for the log lock that A holds, so F never finishes either. A thread that waits for a deadlocked thread is part of the deadlock, which is why the program lists every thread that cannot finish before it names the cycle at the heart of them.
Checkpoint
Check: Resource-allocation and wait-for graphs
With several instances, a cycle is not yet a deadlock
So far every lock had one instance. Then a cycle is a deadlock: each resource on the cycle is held by a thread on the cycle, and that thread is waiting. A pool of identical resources, such as database connections, worker threads or buffers, breaks that argument. A thread that wants a connection can take any free one, including one that a thread outside the cycle gives back. Step through such a snapshot, a pool of two connections and one file lock:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- A cycle through the pool. A holds one of the pool's two connections and wants the file lock. B holds the file lock and wants a connection. The arrows A to file lock to B to pool and back to A form a cycle.
- C holds the other connection. The pool's second connection belongs to C, which waits for nothing because it is running a query. A thread outside the cycle holds an instance that the cycle needs, so the cycle does not settle the question yet.
- C finishes. C finishes its query and returns its connection, so the pool has one free. C waited for nobody, so it was always going to finish.
- B gets a connection. B's request can now be met. B holds the file lock and a connection, waits for nothing and runs to its end.
- B finishes. B releases the connection and the file lock. The file lock is free, and so is one connection.
- A takes the file lock. A takes the file lock and finishes as well. Every thread finished, so this snapshot was never a deadlock, although its graph held a cycle.
The cycle was real, and still nothing was stuck: C held the instance that the cycle needed, and C waited for nobody. Holt’s analysis gives the rule. With one instance per resource, a cycle in the graph is a deadlock. With several instances, a deadlock still needs a cycle, but a cycle is not enough to prove one. To decide, finish whatever can finish, counting the free instances of each resource as threads return them, and see who is left. The last lesson of this module turns that procedure into the detection algorithm, with counts in tables instead of arrows.
Checkpoint
Check: Cycles when a resource has several instances
Livelock and starvation stop progress without a cycle
Threads can fail to make progress without being deadlocked. In a livelock: Threads that keep running and reacting to each other, for example by releasing and retrying in step, while none of them makes progress. they keep running and keep reacting to one another, a case Oracle’s Java tutorial describes beside deadlock, and none of them gets anywhere. In starvation one thread waits while the others keep getting the resource: a lock that always goes to the thread that asks again first, a stream of readers that never leaves a gap for a writer, or a thread whose priority is always lower than someone else’s.
Suppose the two transfers are rewritten to avoid the deadlock politely: a thread that cannot get its second lock at once releases its first and tries again. Step through what happens when both threads keep the same pace:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- A takes lock 17. Each thread now asks for its second lock with a try-lock, which answers at once instead of waiting. A starts by locking account 17.
- B takes lock 42. At the same moment B locks account 42, exactly as in the deadlocked run.
- A tries 42. A tries lock 42 and hears that it is taken. Instead of waiting with lock 17 in hand, A is polite and lets go of 17 to try again.
- B tries 17. B tries lock 17 at the same moment, hears that it is taken, and decides the same thing.
- Both let go. A releases lock 17 and B releases lock 42. Nobody holds anything and nobody is blocked.
- Both start again. B has released 42 too, and after the same short pause both threads start over, A with lock 17 and B with lock 42.
- The same moves for ever. The pair is back where it began. With the same timing the round repeats without end. That is a livelock, both threads running and changing state while no transfer ever finishes.
Neither thread was ever blocked for long, and still no transfer finished. Real timing often breaks such a pattern after a few rounds, but nothing guarantees it, and the usual cure is to make the pauses unequal, for example random. The three failures look alike from outside, a request that never completes, and differ inside:
| What differs | Deadlock | Livelock | Starvation |
|---|---|---|---|
| The threads | are blocked | keep running | one waits, others run |
| Progress | none in the group | none in the group | every thread but the starved one |
| A cycle in the wait-for graph | always | none that lasts | none |
| What ends it | breaking one Coffman condition | breaking the symmetry | a fair order, such as a queue |
Checkpoint
Check: Deadlock, livelock and starvation
Deadlocks hide in lock order, callbacks and full pools
In real programs the two locks are rarely taken side by side in one function, where anyone reading the code would see them. Three patterns hide the cycle well:
| Where it hides | How the cycle forms |
|---|---|
| Lock order across modules | Module X holds its own lock while it calls module Y, which takes Y’s lock; another path holds Y’s lock and calls back into X |
| A callback under a lock | A method holds its object’s lock while it calls a method of another object that locks that object; two threads doing it in opposite directions deadlock, like the two bowing friends of Oracle’s Java tutorial |
| A full thread pool: A fixed set of threads, started once, that take tasks from a shared queue and run them one after another, so that tasks need no thread of their own. More in “Thread pools, event loops and async I/O” | Every worker of a fixed pool runs a task that waits for another task still in the queue, which needs a free worker; Python’s documentation shows it with a pool of one worker |
None of these is visible in a single function. That is why tools record the order in which locks are taken across a whole program: the Linux kernel’s lockdep validator reports two lock classes taken in both orders, even when no run has deadlocked yet. The pool case holds no lock at all. Its resource is the pool’s workers, and its cycle runs through the task queue: each running task waits for a queued task, and every queued task waits for a worker.
Checkpoint
Check: Where deadlocks hide in real code
Practise: name the deadlocked threads
Write the reduction yourself. The function receives a snapshot like the program’s, each thread with the locks it holds and the lock it wants, and returns the threads that can never finish. The sample tests run in your browser and include a thread that waits behind a cycle, two separate cycles and a thread that waits for a lock it already holds:
Exercise · Medium · Python
Name the threads that can never finish
A snapshot lists every thread as a tuple (name, held, wants): the thread's name, the list of locks it holds, and the lock it waits for, or None when it waits for nothing. Every lock has one instance, and a thread that wants a lock nobody holds simply takes it.
Write deadlocked(threads), which returns the sorted list of the names of the threads that can never finish. A thread that waits for nobody can finish and release its locks; a thread can finish once every lock it waits for has been released. A thread that waits for a deadlocked thread never finishes either, and an empty list means that every thread can finish.
Starter code · deadlocked.py
def deadlocked(threads):
"""Returns the sorted names of the threads that can never finish.
threads is a list of (name, held, wants): the thread's name, the locks it holds and
the lock it waits for, or None. Every lock has one instance.
"""
# Replace this line with your code.
return []The sample tests · test_deadlocked.py
from deadlocked import deadlocked
SERVER = [
("A", ["log"], "cache"),
("B", ["cache"], "index"),
("C", ["index"], "log"),
("D", [], "stats"),
("E", ["stats"], None),
]
def test_opposite_orders():
"""two threads that each hold the lock the other wants"""
assert deadlocked([("A", ["17"], "42"), ("B", ["42"], "17")]) == ["A", "B"]
def test_same_order():
"""a thread that waits behind a running thread is not deadlocked"""
assert deadlocked([("A", ["17", "42"], None), ("B", [], "17")]) == []
def test_server():
"""a cycle of three while two other threads finish"""
assert deadlocked(SERVER) == ["A", "B", "C"]
def test_thread_behind_the_cycle():
"""a thread that waits for a deadlocked thread never finishes either"""
assert deadlocked(SERVER + [("F", [], "log")]) == ["A", "B", "C", "F"]
def test_two_separate_cycles():
"""two cycles at once, beside a thread that waits for nothing"""
threads = [
("A", ["1"], "2"),
("B", ["2"], "1"),
("C", ["3"], "4"),
("D", ["4"], "3"),
("E", [], None),
]
assert deadlocked(threads) == ["A", "B", "C", "D"]
def test_lock_nobody_holds():
"""a thread that wants a lock nobody holds takes it, and the chain behind it finishes"""
assert deadlocked([("A", ["1"], "2"), ("B", [], "1")]) == []
def test_waiting_for_itself():
"""a thread that waits for a lock it already holds deadlocks on its own"""
assert deadlocked([("A", ["1"], "1"), ("B", [], None)]) == ["A"]A hint
Start from the threads that wait for nobody: they want None, or a lock that no thread holds. Each one that finishes lets the threads that were waiting for it go next. The threads you never reach are the deadlocked ones.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Then test the whole lesson. The questions open on whichever of its six ideas you have answered worst, and each right answer brings a harder one:
Practice that adapts to you
Practise this lesson
16 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
The warm-up comes with its full answer:
-
Fresher to mid · Warm-up
What four conditions hold whenever there is a deadlock, and what does each of them mean?
Mutual exclusion: a resource can be used by one thread at a time, so the others must wait for it. Hold and wait: a thread keeps what it already holds while it waits for more. No preemption: nothing takes a resource away from the thread that holds it; it is released only when that thread decides to. Circular wait: there is a closed chain of threads in which each waits for a resource held by the next. Coffman, Elphick and Shoshani described the four in 1971, and every deadlock satisfies all of them at once, so breaking any one prevents deadlock. The first three describe how resources are handed out and hold for ordinary locks; circular wait describes the state the threads reach, which is why a global lock order, which makes a cycle impossible, is the usual cure.
Two harder questions start from this lesson: a service that hangs about once a week, and a thread pool that stops with no lock held. Pick a first move for each; every answer explains what it catches and what it misses:
Checkpoint
Your first decision
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Mid to senior
A service hangs about once a week at peak load, and a thread dump taken during a hang shows 40 blocked threads. How do you decide whether this is a deadlock rather than slow I/O or starvation, and how do you find the threads and locks involved?
-
Mid to senior
A service runs requests on a fixed pool of 8 worker threads, and each request submits two sub-tasks to the same pool and waits for both. Under load the service stops completely, yet no thread holds a lock. Explain what happened and how you would fix it.
Key takeaways
- A deadlock is a group of threads in which each waits for something that only another member can do; two locks taken in opposite orders are enough to make one.
- Four Coffman conditions hold in every deadlock, circular wait among them, and a design that rules out any one of the four lets every wait end.
- A resource-allocation graph draws requests and holdings as arrows; with one instance per resource it shrinks to a wait-for graph, and finishing every thread that can finish leaves exactly the deadlocked threads.
- With one instance per resource a cycle is a deadlock; with several instances a cycle is only a warning, settled by finishing what can finish and counting free instances.
- Livelocked threads keep running without progress, and a starved thread waits while others progress; neither shows a lasting cycle.
- Most deadlocks in real code come from lock order across modules, callbacks made under a lock and tasks that wait for other tasks of the same full pool.
Terms in this lesson
- circular wait
- A condition for deadlock: a closed chain of threads in which each one waits for a resource that the next one holds.
- Coffman conditions
- The four conditions that hold whenever a deadlock exists: mutual exclusion, hold and wait, no preemption and circular wait. Removing any one of them prevents deadlock.
- deadlock
- A state in which every thread of a group waits for something that only another thread of the same group can do, such as releasing a lock, so none of them can ever go on.
- hold and wait
- A condition for deadlock: a thread keeps the resources it already holds while it waits for another one.
- livelock
- Threads that keep running and reacting to each other, for example by releasing and retrying in step, while none of them makes progress.
- resource-allocation graph
- A graph of threads and resources in which an arrow from a thread to a resource is a request and an arrow from a resource to a thread means that the thread holds it.
- wait-for graph
- A graph with an arrow from each waiting thread to the thread that holds what it waits for. When every resource has one instance, a cycle in it is a deadlock.
References
- System Deadlocks (E. G. Coffman, M. Elphick and A. Shoshani), ACM Computing Surveys 3(2) (ACM)
- Some Deadlock Properties of Computer Systems (R. C. Holt), ACM Computing Surveys 4(3) (ACM)
- Cooperating sequential processes (E. W. Dijkstra, EWD 123): The problem of the deadly embrace (E. W. Dijkstra Archive, University of Texas at Austin)
- pthread_mutex_lock, pthread_mutex_trylock, pthread_mutex_unlock (POSIX.1-2024) (The Open Group (The Open Group Base Specifications Issue 8))
- pthread_mutex_clocklock, pthread_mutex_timedlock (POSIX.1-2024) (The Open Group (The Open Group Base Specifications Issue 8))
- The Java Tutorials: Deadlock (Oracle)
- The Java Tutorials: Starvation and Livelock (Oracle)
- concurrent.futures: ThreadPoolExecutor (Python Software Foundation)
- Runtime locking correctness validator (lockdep) (The Linux Kernel Organization)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Report a problem with this lesson
Kept only in this browser. Your Learn progress