Prevention, avoidance, and recovery

Topic 5.1 gave the key away: a deadlock needs all four conditions. So make one of them impossible and the problem disappears.

That is prevention, and it is blunt. Every fix costs something Aisha will feel.

There is a subtler option. Let all four conditions stay possible, but check every request before granting it — and refuse the ones that would lead somewhere bad, even when the resources are sitting there free.

That is avoidance, and it is what the Banker's algorithm does.

Why & what

Prevention — break one condition. Take each in turn.

• Break mutual exclusion. Make the resource shareable. This works for read-only files and almost nothing else. You cannot make a printer or a writable log shareable.
• Break hold and wait. Require a process to request everything at once, up front. The editor would have to claim build.log and matrix together. This works, and it is wasteful: the editor holds matrix for the whole session even though it needs it for a second. It can also starve a process that needs many resources at once.
• Break no preemption. Take resources back by force. Fine for a CPU or a memory page, which is why Modules 3 and 7 can preempt freely. Terrible for a half-written file: taking build.log away mid-write leaves it corrupt.
• Break circular wait. Number every resource and require that processes request them in increasing order. If build.log is 1 and matrix is 2, then everyone must take build.log first. A loop cannot form, because forming one would need somebody to request a lower number while holding a higher one.

That last one is the practical winner. It costs nothing at runtime, it just requires programmers to agree on an order. Lock ordering is how real concurrent code avoids deadlock, and it is worth naming in an interview.

Avoidance — the Banker's algorithm. Avoidance needs one extra piece of information: each process must declare in advance the maximum it may ever need.

Two terms:

• A safe state is one where some ordering of the processes exists that lets every one of them finish. Such an ordering is a safe sequence.
• An unsafe state is not a deadlock. It is a state from which a deadlock could be reached. The Banker refuses to enter one, which is why it is conservative.

The rule for every request: pretend you granted it, then check whether a safe sequence still exists. If yes, grant it. If no, make the process wait — even though the resources are physically free.

The name is the analogy: a banker never lends so much that they could not satisfy every customer's credit limit if they all asked at once.

Working the example. Three resource types on the Nova-14: RAM chunks (10), file handles (5), SSD queue slots (7). Currently available: 3, 3, 4.

Look for a safe sequence:

• The browser still needs 1, 2, 2. Available is 3, 3, 4 — enough. Let it finish; it releases 2, 0, 0. Available becomes 5, 3, 4.
• The compile job still needs 0, 1, 1. Enough. It releases 2, 1, 1. Available becomes 7, 4, 5.
• The music player still needs 7, 4, 3. Enough. Available becomes 7, 5, 5.
• The editor still needs 6, 0, 0. Enough.

Every process finished, so the state is safe. The sequence 2104, 2317, 2088, 2210 is the proof. Now a request. The music player asks for 3 RAM chunks and 3 file handles. This is within its declared maximum, and the resources are free. Grant it?

Pretend we did. Available becomes 0, 0, 4. Now check: the browser needs 1, 2, 2 — not available. The compile job needs 0, 1, 1 — not available. The editor needs 6, 0, 0 — not available. The music player itself needs 4, 1, 3 — not available.

Nobody can finish. The state is unsafe, so the request is denied and the music player waits.

How it works

The Banker's safety check, which is what you will be asked to run by hand:

1. Compute Need for every process: Need = Max − Allocation.
2. Start with the current Available vector and an empty finished list.
3. Find any unfinished process whose Need fits inside Available. If none exists, stop.
4. Pretend it runs and finishes. Add its Allocation back to Available and mark it finished.
5. Repeat from step 3. If every process ends up finished, the state is safe and the order you used is the safe sequence.

Recovery, for systems that detect rather than prevent, has two options:

• Kill processes. Either all of them in the cycle, or one at a time until the cycle breaks. Choosing the victim means picking whoever has done the least work, holds the fewest resources, or is easiest to restart.
• Roll back. Return a process to an earlier saved state and take its resources. This needs checkpoints, which is why databases can do it and ordinary programs usually cannot.

Either way, something loses work. There is no painless recovery.

Common confusion

"An unsafe state is a deadlock." It is not, and this is the most important distinction in the topic. An unsafe state is one from which a deadlock is reachable. The system might get lucky — processes might release things earlier than their maximum suggests, and everything works out. The Banker refuses to gamble, which means it sometimes blocks a request that would have been fine.

"The Banker's algorithm is used in real systems." Essentially never. It needs every process to declare its maximum resource use in advance, which programs cannot do; it needs a fixed number of processes and resources, which is not how a laptop works; and the safety check runs on every request. It is taught because it makes the safe-state idea concrete, and because it appears in exams — not because Linux runs it.

"Prevention is free." Every prevention technique costs something. Requesting everything up front wastes resources. Preemption corrupts files. Lock ordering is the cheapest of them, and even that costs discipline across a whole codebase.

"Killing the deadlocked process fixes everything." It breaks the deadlock and destroys that process's work. If the compile job is killed halfway through writing matrix, Aisha is left with a corrupt binary and no error message.

Interview angle

"How do you handle deadlock?" Structure the answer as four strategies and say what each costs: prevention (break a condition, always costly), avoidance (Banker's, needs maximums declared up front), detection and recovery (allow it, find it, kill something), and ignoring it (the ostrich approach, what real systems do).

"Run the Banker's algorithm on this table." Practise until it is mechanical. Compute Need first, always, then walk the list repeatedly. The usual mistakes are forgetting to add the finished process's Allocation back to Available, and stopping at the first pass instead of looping again. "What is the difference between an unsafe state and a deadlock?" Unsafe means a deadlock is possible from here. Deadlock means it has already happened. Every deadlock is unsafe; most unsafe states never become deadlocks.

"How would you prevent deadlock in your own code?" Say lock ordering: number the locks and always acquire them in the same order. It is concrete, practical, and it is what a real answer to a real engineering question looks like.