In the previous lesson we left a debt. The five philosophers deadlocked, we dodged the problem with three tricks that worked, and we did not explain why they worked or what they had in common. This lesson pays that debt and closes the module.

Deadlock is the most feared pathology of concurrency, not because of its frequency but because of how it behaves. It produces no corrupt data and no wrong results: it produces silence. The processes are still alive, they consume no CPU, they write nothing to the log, they return no errors; they simply stop making progress, and from the outside everything looks normal until somebody wonders why meteo-api has not responded for twenty minutes. It is also a failure that shows up under load and not in the tests, because it needs a specific interleaving that only occurs with real traffic.

We are going to build one from scratch so that you see it hang, formalize it with Coffman's four conditions, model it with graphs, and then go through the four strategies that exist: preventing it, avoiding it, detecting it and recovering, or deliberately ignoring it — which is, surprisingly, what Linux does. We will finish with the most practical part of the whole lesson: how a real deadlock is diagnosed on a production server, with tools you will actually use.

1. Definition and a minimal reproducible example
2. Coffman's four conditions
3. The resource allocation graph and cycle detection
4. Strategy 1: prevention
5. Strategy 2: avoidance and the banker's algorithm
6. Strategy 3: detection and recovery
7. Strategy 4: the ostrich, and why Linux adopts it
8. Deadlock, starvation and livelock
9. Diagnosing a real deadlock
10. The solved case of meteo-api and the aggregator
11. Engineering rules that avoid it
12. Closing module 3

A set of processes is in deadlock when each one of them waits for an event that only another process in the same set can produce. Since they are all waiting and none makes progress, the event never happens and the wait is permanent.

The key word is permanent: it is not a long wait, it is a wait it is impossible to get out of without outside intervention. If you wait two hours but eventually make progress, that is a performance problem; if the state of the system guarantees you will never make progress, that is a deadlock.

The minimal example is two mutexes taken in the opposite order. It really does hang, and it is worth running:

Running it, it prints two or three rounds from each thread and stops forever, consuming no CPU and giving no error message at all.

The trace of the fatal moment, after the usleep:

Each one holds what the other needs, and neither will release its own because it is blocked. It is a waiting cycle of length 2.

Two important observations before moving on. The usleep(10) only makes the failure deterministic: without it, the program also hangs, but it may take minutes or hours, because it needs the scheduler to preempt a thread right between the two acquisitions — it is the non-determinism of 03-01: the window is always there, and with enough iterations it eventually happens. And the code is correct when each function is looked at on its own: both take two locks, do their work and release them in the opposite order, just as the manual says. The bug is in neither of the two functions, it is in the relationship between them, which is why no code review that looks at one function in isolation will catch it.

In 1971, Edward Coffman formulated the four necessary conditions for a deadlock to be possible. Their practical value is enormous: since all of them are necessary at once, it is enough to guarantee that one does not hold for deadlock to be impossible. The entire prevention strategy comes from here.

1. Mutual exclusion. At least one resource must be non-shareable: if a process holds it, another cannot hold it at the same time. Without it there is no possible conflict, because if ten processes can use the resource at once nobody waits for anybody. It is why the shared reads of an rwlock cannot be part of a deadlock, but the writes can.

2. Hold and wait. A process that already holds at least one resource requests another and waits without releasing what it holds.

It is the condition that makes the blocking spread: if on requesting a new resource you released everything you held, your wait would block nobody. In the example, the aggregator waits for the file while holding the cache, and that is what traps meteo-api.

3. No preemption. A resource can only be released voluntarily by the process that holds it; the system cannot take it away. A mutex satisfies this condition by design: there is no call that rips a mutex away from a thread, and rightly so, because the state it protected would be left half-modified. The CPU, by contrast, is preemptible — the scheduler takes it away every few milliseconds — and that is why there is never a deadlock over the CPU; and physical memory is preemptible too, thanks to swapping (module 2).

4. Circular wait. There is a set of processes {P₀, P₁, ..., Pₙ} such that P₀ waits for a resource held by P₁, P₁ waits for one held by P₂, ..., and Pₙ waits for one held by P₀. It is the most visible condition and the one that gives the mental image of the problem. Watch out for the logical detail: circular wait implies hold and wait, but not the other way round — there can be many processes holding and waiting without any cycle closing, and then there is no deadlock.

Summarized, with what it costs to break each one:

This table is the map of the prevention strategy, and it already anticipates the conclusion: in practice, the fourth one is almost always the one broken.

The formal model that lets you reason about this is the resource allocation graph, a directed graph with two kinds of node — processes and resources — and two kinds of edge: the assignment edge R → P, meaning that resource R is assigned to process P, and the request edge P → R, meaning that P is waiting for resource R. Our example looks like this:

The cycle aggregator → file_lock → meteo-api → cache_lock → aggregator leaps off the page. And here is the theorem that makes the model useful:

If every resource has a single instance, a cycle in the graph is a necessary and sufficient condition for deadlock. If some resource has several instances, the cycle is necessary but not sufficient.

The distinction matters. A mutex is a single-instance resource: either you hold it or you do not. A semaphore initialized to 5 — five database connections — has five instances, and there a cycle is not enough: one of them may be held by a process outside the cycle, which will release it and unjam everyone. For those cases a more elaborate detection algorithm is needed, which we will see in section 6.

Looking for cycles in a directed graph is a solved problem: a depth-first traversal detects them in O(V + E), and a system with 1,000 processes and 5,000 resources is analyzed in milliseconds. The difficulty is not the algorithm, but building the graph: you have to know, in a frozen instant, who holds what and who is waiting for what. In the kernel that is easy; from outside, not so much.

Preventing means designing the system so that one of the four conditions never holds. It is a structural guarantee: if the condition cannot occur, deadlock is impossible by construction, with nothing to check at run time.

Breaking mutual exclusion would mean making the resources shareable, and that is impossible for most: a mutex exists precisely in order to exclude. Where it does apply is with virtualizable resources — module 2's print spooling: instead of competing for the printer, the processes write into a queue of files and a daemon manages it. In Meteora, the cache could be made "shareable" with the double buffer we proposed in the previous lesson, where readers never block.

Breaking hold and wait, in two variants. Requesting everything at once up front: the process declares all the resources it will need and only starts when it has them all.

Note the pthread_mutex_trylock, which tries to acquire without blocking and returns an error if it cannot: by releasing a when it fails, the process never holds while waiting. The random wait before retrying is essential, because without it two threads can fall into lockstep and retry at the same time forever, ending up in the livelock of section 8.

Releasing everything before requesting. If you need a new resource, you release those you hold and request them all again: correct but costly, and the state they protected is exposed in between. The cost of this route is low utilization — you reserve resources you may not use for another ten minutes — and possible starvation — whoever needs many resources may never get them all at once. It is used in real time and in databases with static scheduling, not in general code.

Breaking the absence of preemption. If a process requests a resource and cannot get it, everything it held is taken away and it retries later. In user space it is implemented with timeouts:

pthread_mutex_timedlock turns an infinite wait into a bounded one, transforming a permanent deadlock into a recoverable temporary failure. The cost is that you have to be able to undo the work done up to that point, which requires transactional critical sections; and in its aggressive form it can produce livelock.

Breaking circular wait: the global order. This is the winning technique, the one you will always use: impose a total order on the resources and require every process to acquire them in increasing order.

Why it works, proved: suppose there is a cycle P₀ → P₁ → ... → Pₙ → P₀. Each edge means that Pᵢ holds a resource of order k and waits for one of order m > k. Going round the cycle, the orders increase strictly at every step, and on returning to the starting point we would have k > k. Contradiction: the cycle is impossible.

When the resources have no natural order, their memory address is used:

It is the pattern used by bank transfers between two accounts, and it solves the problem in general: whichever two locks you pass it, it will always take them in the same absolute order. Cost in performance: zero. Cost in discipline: the hierarchy has to be documented and respected throughout the code, including code somebody else writes two years from now. That is why serious kernels document their lock hierarchy and have automatic validators, as we will see.

Avoidance is more ambitious than prevention: it does not restrict how you request, but decides on each request whether to grant it, depending on whether the resulting state is still safe. It requires each process to declare its maximum need for each resource in advance.

A safe state is one in which there is a safe sequence: an ordering of the processes ⟨P₁, P₂, ..., Pₙ⟩ such that each Pᵢ's outstanding needs can be met with the free resources plus those that will be released by all the Pⱼ with j < i. If such a sequence exists, the system can finish them all, one after another, without blocking. The relationship between the three kinds of state is hierarchical: safe implies there is not and will not be a deadlock; unsafe means there may be one, not that there is; and deadlocked is a subset of the unsafe ones. Avoidance is conservative: it rejects every request that leads to an unsafe state, even though that state might not have caused any problem.

Dijkstra named it by analogy with a banker granting credit: he never commits so much money that he could not satisfy all his clients' credit lines.

The scenario. meteo-01 has three kinds of resource — A: 10 database connections; B: 5 buffers of 1 MB in /dev/shm; C: 7 reserved descriptors — and five processes. The current state is given by the Allocated matrix (what each process holds now) and the Maximum matrix (what it declared it might come to need):

Available = Total − Allocated = (10, 5, 7) − (7, 2, 5) = (3, 3, 2)

Question 1: is this state safe? We go through the list looking for who can complete with what is available; when one finishes, it returns everything it had allocated:

At step 1, P₀ did not fit because it needs 7 units of A and there are only 3. The state is SAFE, with the sequence ⟨P₁, P₃, P₄, P₂, P₀⟩; there are others that work, and finding one is enough.

Question 2: P₁ (aggregator) requests (1, 0, 2). Is it granted?

Three checks in a chain. Is Request ≤ Need? (1,0,2) ≤ (1,2,2), yes, it is not asking for more than it declared. Is Request ≤ Available? (1,0,2) ≤ (3,3,2), yes, the resources are there. Would the resulting state be safe? We have to simulate it: Available = (3,3,2) − (1,0,2) = (2, 3, 0); P₁'s Allocated = (3,0,2); P₁'s Need = (0, 2, 0). We look for a safe sequence in that hypothetical state:

The sequence ⟨P₁, P₃, P₄, P₀, P₂⟩ exists: the resulting state is safe and the request is granted.

Question 3: in the original state, what happens if P₀ (ingestor) requests (0, 3, 0)? It asks within its maximum and the resources are there ((0,3,0) ≤ (3,3,2)), but on simulating the grant, Available would be left at (3, 0, 2): resource B is exhausted completely. Only P₂ could make progress — it needs (6,0,0), which does not fit: 6 > 3 — so in fact nobody fits, because everyone else needs at least 1 unit of B and there is none left. No safe sequence exists: unsafe state, request DENIED, even though at that instant there were enough resources to satisfy it.

That case illustrates the essence of the algorithm: denying a request that could be satisfied, because leading the system into an unsafe state is a risk that is not worth taking.

The algorithm is correct and elegant, but in practice almost nobody applies it, for four cumulative reasons:

That last row is devastating: a pthread_mutex_lock costs 20 nanoseconds; running the banker before each one would cost milliseconds. It would be five orders of magnitude slower.

Where it is used: mission-critical embedded systems with a fixed, known set of tasks — avionics, industrial control — where the number of processes and resources is frozen at design time and certification demands formal guarantees. For everything else, the banker is an extremely valuable conceptual tool — the notion of a safe state structures your thinking — and a technique that does not get implemented.

If preventing is expensive and avoiding is impractical, the third route is to let it happen, detect it and get out of the jam.

Detection is done with the wait-for graph, a simplification of the allocation graph in which the resource nodes are removed and Pᵢ → Pⱼ is connected directly when Pᵢ waits for a resource held by Pⱼ:

There is a deadlock if and only if the wait-for graph has a cycle — for single-instance resources. Detection is a depth-first traversal, O(V + E). For resources with several instances you have to use a variant of the banker's algorithm that, instead of the declared maximum need, uses the actual outstanding request.

How often should it be run? It is a genuine trade-off:

A heuristic used in real systems is the third: if CPU usage is low but there are many processes in a non-runnable state, that is suspicious. Linux does something similar with the hung task detector we will see in section 9.

Recovery has two routes, and neither is pleasant. The first is terminating processes: either all those in the cycle (fast and brutal) or one at a time, reevaluating (slow but less destructive). Choosing the victim is done with weighted criteria:

The second route is rollback: returning a process to an earlier checkpoint and retrying. It is what databases do — when PostgreSQL detects a deadlock, it aborts the youngest transaction and returns error 40P01 to the client, who can retry it. It is the ideal recovery because no committed work is lost, but it requires all the work to be transactional, which a C program with mutexes does not have. The danger in both routes is starvation: if the algorithm always picks the same victim, that process will never finish, so the criteria have to include how many times it has already been sacrificed.

The fourth strategy is to do nothing: ignore the problem and trust that it is rare enough that the cost of dealing with it is not worth paying. It is known as the ostrich algorithm, from the image of burying your head in the sand.

It sounds like negligence, but it is a conscious engineering decision and it is the one Linux, Windows, macOS and practically every general-purpose operating system takes for user-space resources. The reasons, in order of weight:

1. The cost of the alternatives is disproportionate. Preventing with a global order requires coordinating all the code in the system, including third-party code. Avoiding with the banker is five orders of magnitude slower for every lock. Detecting requires maintaining an up-to-date graph of who waits for what, with its own synchronization. All that for a failure that, with decent programming, does not happen — and its real frequency is low, because deadlocks are programming errors, not random system events.

2. The system cannot know what is a deadlock and what is not. This is the decisive argument and the least obvious one. A process blocked in read() on an empty FIFO is indistinguishable, from the kernel's point of view, from a deadlocked one: both wait for an event that may never come, and the kernel does not know whether the writer is going to show up. Telling "legitimate waiting" from "deadlock" requires understanding the program's intent, and the system cannot do that.

3. Restarting is acceptable in most contexts. If a service hangs, systemd restarts it (module 7) and the system carries on. The cost of an occasional restart is far lower than that of instrumenting the whole system.

That said, the ostrich is not universal, and it is worth seeing who does act:

The kernel row deserves a note, because it is the best example of the right approach: lockdep is a validator enabled with CONFIG_PROVE_LOCKING which, during execution, learns the order in which locks are taken and warns the first time anybody reverses it, even if the deadlock never actually occurs. It is the ThreadSanitizer of locking: it detects the cause, not the symptom. Its cost is high — 20-30 % of performance — which is why it is only used in development kernels, but it has prevented thousands of hangs in production.

Three pathologies that are constantly confused. It is worth distinguishing them precisely, because the diagnosis and the solution are different.

Deadlock is this lesson's example: two threads in S, 0 % CPU, forever. Starvation is a process ready to run that the scheduler never picks, or that asks for a resource always granted to others — the writer in v1 of readers-writers, with 3 writes in 30 seconds; the key difference from deadlock is that there is no cycle, so the starving process could make progress at any moment if it got lucky, and it is solved with aging (raising the priority of whoever has been waiting a long time) or fair queues.

In a livelock, by contrast, the processes do execute instructions but their state does not progress. The image is two people in a corridor who step aside to the same side simultaneously, over and over:

If the two threads run this at the same time and at the same speed, they can alternate indefinitely: A takes a, B takes b, A fails on b and releases a, B fails on a and releases b, and round again. Both cores at 100 %, zero progress. It is worse than a deadlock in one sense: at least a deadlock consumes no resources and is easy to see in top.

The solution is random backoff, the same idea Ethernet uses to resolve collisions:

It is enough for the retries not to be simultaneous for one of the two to win. Adding exponential growth (wait *= 2 on each failure, with a cap) makes it robust under high contention too.

This is the part you will use in your job. It is three in the morning, meteo-api is not responding, and you have to work out what is going on. The steps, in order.

Step 1: confirm that it is stopped and not working.

0.0 % CPU on every thread and state S: it is not computing, it is waiting. If you saw 100 % and state R, it would be an infinite loop or a livelock, not a deadlock. This first distinction saves a lot of time.

Step 2: see what each thread is waiting on, with cat /proc/2841/task/*/wchan. If the answer is futex_wait_queue_me in all of them, the signature is unmistakable: they are asleep waiting on a futex, that is, a mutex, a semaphore or a condition variable (03-04). If you saw pipe_write it would be a full pipe; sk_wait_data, a socket with no data; io_schedule, pending disk I/O. WCHAN narrows down the kind of wait before you look at a single line of code.

Step 3: get each thread's stack. Here gdb is irreplaceable:

Thread 3 is blocked on mutex 0x5581e4a2c0c0 from api.c:212; thread 2, on 0x5581e4a2c100 from aggregator.c:88. Two threads blocked on two different mutexes: the exact pattern of a deadlock. To confirm it you have to find out who holds each mutex, and the internal structure of pthread_mutex_t stores the owner's TID:

The cycle is closed and proved: thread 2844 waits for a mutex held by 2843, and 2843 waits for one held by 2844. Deadlock confirmed, with file names and line numbers.

Step 4: the kernel's hung task detector. For processes in state D (uninterruptible wait, typically I/O), Linux has a watchdog that warns on its own:

A kernel thread (khungtaskd) walks the tasks in state D every 120 seconds and warns about those that have been there too long. Important: it only watches state D, not S, so it does not detect deadlocks on user-space mutexes — those leave the threads in S. It is useful for blocking in the kernel: a dead NFS mount, a disk that is not responding, a kernel lock used badly.

Step 5: /proc/<pid>/stack shows a thread's kernel stack (futex_wait_queue_me → futex_wait → do_futex → __x64_sys_futex → do_syscall_64), confirming from the kernel side what gdb sees from the user side: the thread came in through the futex call and is in the wait queue. It requires CONFIG_STACKTRACE and root privileges.

A summary of the toolbox:

With the tools above, Meteora's complete incident. Symptom: at 03:14, monitoring warns that meteo-api is returning timeouts. The service is alive, it has not restarted, and there has been nothing new in /var/log/meteora/meteo-api.log since 03:12:47.

Diagnosis (the five steps above, in three minutes): 0 % CPU and state S on every thread → futex_wait_queue_me in every wchan → gdb reveals two threads blocked on different mutexes → the __owners of those mutexes close the cycle. Deadlock confirmed between aggregator.c:88 and api.c:212.

Root cause, on looking at the code:

Opposite orders: the aggregator does cache → file; api_read_history does file → cache. It is the minimal example of this lesson, written by two different people in two different files, each perfectly reasonable on its own.

Why it appeared on that particular night. Three factors had to coincide: agg_hourly_cycle() runs once an hour and only then does the window exist; api_read_history() is only called when a client asks for data more than 24 hours old, some 40 times a day; and the window between the two acquisitions lasts about 200 µs, the time compute_averages_from_cache takes.

Probability per hour ≈ (40/86400 calls/s) × 200 µs × 3600 s ≈ 0.00033: once every 3,000 hours, about four months. That number explains why the code passed every test, had been in production for months and failed one September night. A deadlock with a vanishing probability is a certainty in the medium term, exactly like the race conditions of 03-01.

Immediate fix (at 03:20): systemctl restart meteo-api, which restores the service in two seconds but fixes nothing. Definitive fix: establish a global lock order, document it, and correct the order in api.c:

An additional defense: a debug-mode wrapper that checks the hierarchy at run time, in the style of lockdep:

This wrapper detects the violation the first time it happens, even if the deadlock never occurs. It is the same philosophy as ThreadSanitizer and lockdep: look for the cause, do not wait for the symptom. Compiled only in the tests, the cost in production is zero.

None of these rules is theoretical: they all come from real incidents.

1. Define and document a lock hierarchy. It is rule number one, and the one that would have prevented the incident. A header file with the levels and a comment on each lock stating its own. If all the code acquires in increasing order, circular wait is mathematically impossible.

2. When there is no natural order, order by memory address. The pattern if (a < b) lock(a), lock(b); else lock(b), lock(a); works for any pair and requires no prior convention.

3. Use timeouts in long-lived code. pthread_mutex_timedlock with 5 or 10 seconds turns a permanent hang into a logged error you can recover from. Always log the failure: an expired timeout is a warning that you have a design problem, not a solution.

4. Keep critical sections short and with a single lock whenever you can. If you never hold two locks at once, there is never a cycle. Often it is enough to reorganize: read with the lock, release, compute, take it again to write.

5. Never call somebody else's code while holding a lock. It is the most forgotten rule and one of the most dangerous. If inside your critical section you invoke a callback, a plugin, an event handler or a third-party library, you have no idea which locks that code will take. It may take yours (self-deadlock), it may take another in the opposite order (deadlock), it may do a second's worth of I/O. Prepare the data, release the lock, and call afterwards.

6. Do not do I/O or allocate memory inside a critical section. A write() to disk can take milliseconds and a malloc() may take the allocator's own internal lock: both multiply the danger window a thousandfold. And be careful with PTHREAD_MUTEX_RECURSIVE, which allows the same mutex to be taken several times: it avoids self-deadlocks, but it usually gives away that you are not clear about who owns what.

7. Run the tests with detectors enabled. ThreadSanitizer (-fsanitize=thread) also detects inconsistent lock orders, not just races. In the kernel, lockdep. In your code, a wrapper like the one in the previous section. Looking for the cause always beats waiting for the symptom.

8. Prefer higher-level primitives. A channel, a message queue or an actor model eliminates the whole class of problems: if you take no locks, no cycle is possible. Most application code can be written without a single explicit mutex.

Assuming that "it works in the tests" means there is no deadlock. Meteora's case had a probability of 0.00033 per hour and survived months in production before showing itself. Tests do not find deadlocks; lock-order analyses do.

Reviewing functions in isolation. Each of the two functions in the incident was impeccable on its own. The bug was in the relationship between them, and only a review that looks at every place those two locks are taken catches it.

Confusing deadlock with starvation or livelock. If the CPU is at 100 %, it is not a deadlock: it is livelock or a loop. If a component makes progress but very slowly, it is starvation. top -H tells them apart in five seconds and saves hours of searching in the wrong direction.

Adding a recursive lock to "fix" a self-deadlock. The self-deadlock is the symptom that you do not know which locks you hold on reaching that function; RECURSIVE hides it and leaves the design problem untouched.

Setting timeouts and not logging the failures, or calling a callback while holding a lock. A timedlock that expires silently turns a visible hang into an invisible degradation: always log, with the name of the lock. And calling somebody else's code inside a critical section is the fastest route to a deadlock between your code and a library you do not control.

Tip: draw the graph when in doubt. Faced with two or three locks and several flows, drawing the allocation graph on paper takes two minutes and reveals the cycle immediately. It is the most cost-effective reasoning tool in this lesson.

Tip: if you often need two locks, consider whether they should be one. Two locks that are almost always taken together probably protect the same invariant. Merging them removes the problem at the root and often simplifies the code.

Write the two-thread program with two mutexes in the opposite order and run it until it hangs. Diagnose it following the five steps of section 9: top -H, wchan, gdb with the stacks, and identifying the owner of each mutex. Document what you see at each step. Then fix it with the memory-address order and verify that it no longer hangs over 10 million iterations. Finally, remove the usleeps from the broken version and measure how long it takes to hang without them, repeating the measurement five times.

A system has 3 resource types with (12, 8, 6) total units and four processes:

Compute the Need matrix and the Available vector. Determine whether the state is safe and, if it is, give a safe sequence. Then evaluate two requests separately, always from the original state: P₂ asks for (1, 1, 0) and P₀ asks for (3, 2, 1). Justify each decision with the complete matrices.

For each situation, identify whether it is deadlock, starvation, livelock or none of the three, say what you would see in top -H and wchan, and propose a solution.

• (a) Two meteo-api threads at 0 % CPU in state S; one waits for mutex A held by the other, and vice versa.
• (b) The aggregator has been unable to write to the cache for 40 seconds because the 4 workers read non-stop with an rwlock.
• (c) Two threads at 100 % CPU in state R; both take a lock, see that the other one is busy, release theirs and retry immediately.
• (d) The ingestor has been blocked for 5 minutes in read() on /run/meteora/readings.fifo because nobody is writing.
• (e) A thread calls pthread_mutex_lock twice in a row on the same non-recursive mutex.

Solution 1

Step-by-step diagnosis of the hung program (PID 9412):

The first step rules out livelock and an infinite loop (0 % CPU and state S mean stopped, not working); the second narrows the wait down to a futex, that is, to a mutex, semaphore or condition variable; the third gives the file and line of each block; and the fourth closes the cycle: 9413 holds the cache and waits for the file, held by 9414; 9414 holds the file and waits for the cache, held by 9413. Deadlock confirmed between deadlock.c:18 and deadlock.c:31.

Fix with the address order:

With 10,000,000 iterations and no usleep, none of the 20 runs hung (0.71 s on average). The two threads always take the lower-addressed mutex first, so circular wait cannot form.

Without the usleeps, in the broken version, the iterations it survived before hanging in five runs were 47,219 (0.08 s), 3,106,884 (4.91 s), 812 (0.002 s), 18,443,201 (31.2 s) and 291,556 (0.47 s).

Four orders of magnitude of difference between the fastest and the slowest, without changing a single line. That is the nature of the problem: the window between the two acquisitions lasts a few nanoseconds and the deadlock requires the scheduler to preempt right there. With enough iterations it always happens, but when is unpredictable. In production, with critical sections of microseconds and operations that happen a few dozen times a day, that "always" translates into months.

Solution 2

Need = Maximum − Allocated:

Available = (12, 8, 6) − (8, 6, 4) = (4, 2, 2)

Is the state safe?

The state is SAFE, with the sequence ⟨P₁, P₀, P₃, P₂⟩. (At step 1, P₃ would fit too — (3,2,2) against (4,2,2) — so there are more valid sequences.)

Request A: P₂ asks for (1, 1, 0). It passes the first two checks — (1,1,0) ≤ Need (6,4,2) and ≤ Available (4,2,2) — so we simulate: Available = (3,1,2), P₂'s Allocated = (3,2,2), P₂'s Need = (5,3,2).

Safe sequence ⟨P₁, P₀, P₃, P₂⟩. GRANTED.

Request B: P₀ asks for (3, 2, 1). It also passes the first two — (3,2,1) ≤ Need (4,3,2) and ≤ Available (4,2,2) — but on simulating, Available is left at (1, 0, 1) and P₀'s Need at (1,1,1). Now nobody fits: P₀ needs 1 of B and there are 0; P₁ needs 2 of A and 1 of B, and there are 1 and 0; P₂ and P₃ are much further away. No process can complete, no safe sequence exists, the resulting state is unsafe and THE REQUEST IS DENIED.

Compare the two: in A there were (3,1,2) left, enough for P₁ to finish and release its resources, starting the chain. In B resource B is exhausted completely, leaving all four processes unable to reach their maximum. That is exactly the scenario the banker exists to prevent: not a current deadlock, but the possibility of one if everybody asked for their maximum.

Solution 3

Comments on the cases that are most often confused:

(b) versus (a). The difference is that in starvation the system as a whole does make progress: the readers complete millions of operations. Only one component is stopped, and it could make progress at any moment if there were a gap. There is no cycle, and that is why gdb would show the aggregator waiting for a lock whose owner changes constantly, instead of being fixed. That is the distinguishing sign: if you look twice a second apart and the __owner is different, it is starvation, not deadlock.

(c) is the easiest to identify and the easiest to confuse from a distance. State R and 100 % CPU give it away immediately: a deadlock never consumes CPU. If the service is not responding but the cores are maxed out, do not look for a lock cycle; look for a retry loop or an infinite loop.

(d) is the reason the operating system cannot detect deadlocks automatically. From the kernel's point of view, this case is indistinguishable from (a): a process in S waiting for an event that may never come. The difference only exists in the program's intent — should anybody ever write to that FIFO? — and the kernel does not have that information. It is argument 3 of the ostrich section, in concrete form.

(e) produces the same clinical picture as (a) but with a single thread involved, and in gdb it is obvious straight away: the mutex's __owner is the TID of the very thread that is waiting. It is a cycle of length 1.

A deadlock is a set of processes in which each one waits for an event that only another in the set can produce, and the wait is permanent. We have built one in twenty lines — two mutexes taken in the opposite order — and we have seen that each function was correct on its own: the bug lives in the relationship between them, which is why no isolated code review finds it.

Coffman's four conditions — mutual exclusion, hold and wait, no preemption and circular wait — are all necessary at once, and that is their value: breaking one is enough. The first is almost always unbreakable, the second costs concurrency and starvation, the third requires being able to undo work, and the fourth is broken with a global acquisition order at zero cost. The resource allocation graph gives the formal model: with single-instance resources, a cycle is a necessary and sufficient condition.

Of the four strategies, prevention through a global order is the one you will always use, and its proof takes two lines: if the orders increase strictly along a cycle, closing it would give k > k. Avoidance with the banker's algorithm, which we have worked through with complete matrices, formalizes the valuable idea of a safe state, but it requires knowing the maximum needs in advance and costs O(n²m) per request — five orders of magnitude more than the lock it protects — so it is only used in critical embedded systems. Detection and recovery with a wait-for graph is the databases' route, since they can abort transactions without losing consistency, with the whole problem of choosing the victim without causing starvation. And the ostrich strategy is the one Linux, Windows and macOS adopt for user space, for a reason that goes beyond cost: the system cannot tell a legitimate wait from a deadlock, because that would require knowing the program's intent. The kernel, by contrast, does protect itself, with lockdep verifying the lock order.

We have separated deadlock from its two cousins: starvation, where the system makes progress but one component does not, with no cycle and potentially resolvable; and livelock, where the processes run at 100 % CPU without progressing, which is cured with random backoff. top -H tells them apart in five seconds: 0 % and S is deadlock; 100 % and R is livelock.

And the most useful part: the diagnostic procedure. top -H to confirm it is stopped; wchan to learn the kind of wait (futex_wait_queue_me is the signature of mutexes); gdb -p ... -ex "thread apply all bt" for every thread's stack; and print on the mutex structure to read its __owner and close the cycle with file names and lines. Meteora's case was solved this way in three minutes: aggregator.c:88 took cache→file and api.c:212 took file→cache, with a probability of coincidence of once every four months, which explains why it passed every test. The solution was a documented lock hierarchy — config, cache, file, log — plus a wrapper that aborts in the tests when somebody violates it.

That is the end of the module, and it is worth looking at the whole journey. You started by understanding what goes wrong (03-01): concurrency versus parallelism, interleaving as a mental model, and counter++ broken down into three machine instructions that lose half a million increments. There the critical section appeared with its three requirements — mutual exclusion, progress, bounded waiting — which have served as the criteria throughout the module, along with Amdahl's law and its ceiling of 3.57× for the aggregator.

Then you met the protagonists (03-02): the thread as a flow with only three private things — program counter, registers and stack — the exhaustive table of what it shares and what it does not, the 22 µs against 180 µs that justify its existence, and the revelation that Linux does not implement threads but clone(), with Python's GIL measured without the myths. In IPC (03-03) you solved how processes that do not share memory talk to each other: pipes with their 65,536-byte buffer and their backpressure, FIFOs, POSIX queues with priorities, shared memory over /dev/shm/meteora-cache, sockets and signals. And the asterisk was flagged: shared memory carries data but coordinates nobody.

That asterisk was paid off in synchronization (03-04), the central lesson: three naive attempts that fail, Peterson and his limit on real hardware, compare-and-swap as the foundation of everything, and on top of it spinlocks, mutexes, semaphores, condition variables, rwlocks and barriers. With futex explaining why a mutex costs 20 ns — 841 system calls for two million acquisitions — volatile dismantled, and granularity measured at 7.25× with partitioning. The classic problems (03-05) gave you the vocabulary: producer-consumer with its three semaphores and the trap in the order of the waits; readers-writers with its starvation measured at 3 writes per 30 seconds; philosophers and their cycle; the sleeping barber as meteo-api's thread pool. And this last lesson closed the circle by explaining why the philosophers' solutions worked.

If module 2 answered how a scarce resource is shared out, module 3 has answered how several flows are coordinated over a shared piece of data, and the answer has always had the same shape: an indivisible operation guaranteed by the hardware, a system primitive built on top of it, and a design discipline the programmer has to respect. All three layers are necessary; none is enough on its own.

But notice something. This whole module has happened in memory: counters, caches, shared structures, all of it volatile, all of it lost if meteo-01 is switched off. And yet for three modules we have been naming /var/lib/meteora/readings/2026-08-31.dat, /etc/meteora/meteora.conf and /var/log/meteora/meteo-api.log as if they were obvious. What exactly is a file? How does the system know which disk blocks its 17 MB live in? What really happens when you open a path such as /var/lib/meteora/readings/, and why does that path look so little like what is on the SSD? And how does all of that survive a power cut in the middle of a write?

It is Module 4: File Structures, and it starts in File Systems.