Two ways to make deadlock impossible
In guide 1 you met the deadlock — a set of processes each frozen forever, each holding a resource the next one in the ring is waiting for. The crucial fact was that it needs all four of the four necessary conditions at once: mutual exclusion, hold and wait, no preemption, and circular wait. Guide 2 then taught you to draw the resource-allocation graph and read a cycle in it as the warning sign. This guide answers the obvious next question: knowing all that, how do we actually keep deadlock from happening?
There are two distinct attitudes, and it is worth keeping them straight. Prevention is the blunt, structural approach: design the system so that one of the four conditions can never hold, full stop. If even one leg of the table is sawn off, the table cannot stand — deadlock becomes structurally impossible, no runtime checking required. Avoidance is gentler and smarter: allow all four conditions to be possible in principle, but have the kernel examine each request the moment it arrives and grant it only if doing so cannot lead the system into trouble later. Prevention says never build the trap; avoidance says the trap exists, so steer around it on every step.
Prevention: saw off one leg of the table
Deadlock prevention works by guaranteeing that at least one of the four conditions can never be satisfied. The honest catch is that some legs are far easier to saw off than others. Mutual exclusion is usually non-negotiable: a printer or a lock genuinely can only be held by one process at a time, and you cannot wish that away. So prevention almost always targets one of the other three, and each choice extracts a real price.
Attack hold-and-wait by forbidding a process from ever holding one resource while waiting for another: make it request everything it could possibly need up front, all in one shot, and only start running once it has the whole set. No partial holdings means no ring of waiters can form. The price is poor utilization — a process that needs the tape drive only at the very end must grab it at the start and sit on it the whole time — plus possible starvation for a process that needs a popular bundle and can never find all of it free at once. Attack no-preemption instead: if a process holding some resources asks for one it cannot get, force it to give up everything it holds and try again later. That works for resources whose state is easy to save and restore, like CPU registers or memory pages, but it is hopeless for a printer mid-page or a file being written.
The cleanest leg to saw is usually circular wait, and the trick is elegant: impose a single global ordering on every resource type — number them 1, 2, 3, and so on — and require that a process may only request resources in increasing order. If you hold resource 5, you may ask for 6 or 9 but never for 2. Why does this kill the cycle? A circular wait needs some process holding a high-numbered resource while waiting for a low-numbered one held by another, but the ordering rule forbids exactly that backward reach — so the ring can never close. This is the prevention scheme you will actually see in real lock-heavy code: a documented lock-ordering convention that every developer must follow by hand.
Avoidance: stay in a safe state
Prevention is heavy-handed because it constrains how processes may ask, forever. Deadlock avoidance keeps things flexible by asking, at the moment of every single request, a sharper question: if I grant this, can I still guarantee that everyone eventually finishes? To answer it, avoidance needs one extra piece of information that prevention does not: each process must declare in advance the maximum number of each resource it could ever need over its whole lifetime. With that maximum-claim known, the kernel can look ahead.
The central idea is the safe state. A state is safe if there exists at least one ordering of all the processes — call it a safe sequence — such that each process, in turn, can be given everything it might still demand using only the resources currently free plus those that earlier processes in the sequence will release when they finish. Picture a line at a single coffee machine where the barista can prove: I can finish customer A with what is free now, and once A leaves and returns the cup, I will have enough to finish B, then C, and so on to the end. If such a finishing order exists, no one gets permanently stuck. A safe state is therefore a promise: deadlock is provably still avoidable from here.
The banker's algorithm, step by step
The most famous avoidance scheme is the banker's algorithm, named by Dijkstra for a banker who will only lend cash if, even in the worst case, every client can still be paid out their full credit line and repay the loan. It tracks four tables: the total Available units of each resource type, the Max each process declared it might need, the amount each process currently has Allocated, and the Need (simply Max minus Allocation) — the most each process could still ask for. When a request arrives, the banker pretends to grant it, then runs a safety check on the resulting tables. If they are still safe, the grant becomes real; if not, the request is denied and the asker waits.
- Start the safety check with a scratch copy: a Work vector equal to Available right now, and mark every process as not-yet-finished.
- Hunt for any not-yet-finished process whose entire remaining Need is less than or equal to Work — meaning we could satisfy it completely with what is free.
- Pretend that process runs to completion and hands everything back: add its Allocation into Work, then mark it finished. Available has effectively grown.
- Repeat steps 2 and 3, looping over the processes again, since the freshly returned resources may now unblock a process that did not fit a moment ago.
- If every process eventually gets marked finished, a safe sequence exists, so the state is safe. If you get stuck with some processes never satisfiable, the state is unsafe — so the original request must be refused.
Resource type: 12 tape drives total. Need = Max - Allocation
Process Max Allocation Need
P0 10 5 5
P1 4 2 2
P2 9 2 7
-------
held = 9 -> Available = 12 - 9 = 3 free
Safety check (Work starts at 3):
Work=3 -> P1 Need 2 <= 3 : run P1, give back 2 -> Work = 5
Work=5 -> P0 Need 5 <= 5 : run P0, give back 5 -> Work = 10
Work=10 -> P2 Need 7 <= 10 : run P2, give back 2 -> Work = 12
All finished. Safe sequence found: <P1, P0, P2> -> SAFE.Why almost nobody actually runs it
The banker's algorithm is beautiful, and it is one of the rare cases where you can mathematically prove a system will never deadlock. So here is the honest twist that surprises every student: general-purpose operating systems like Linux, Windows, and macOS do not use it. The reasons are practical and damning. It demands that every process declare its maximum resource needs in advance — but a real program almost never knows how many files, locks, or memory pages it will want before it runs. The number of processes and resources keeps changing as programs start and stop, while the algorithm assumes a fixed, known population. And the safety check is not free: it runs on the order of processes times resources work on every single request, which is far too slow to do on every lock acquisition in a busy kernel.
So what do real systems do? Mostly they prevent the easy condition — circular wait — by hand, through disciplined lock ordering, and otherwise they simply ignore deadlock and accept the rare hang (the ostrich approach, which guide 4 covers head-on). The banker's algorithm earns its keep only in narrow, high-stakes places where the resource set really is fixed and known in advance, such as some embedded and real-time controllers. The lasting payoff of learning it is conceptual: the notions of a maximum claim, a safe state, and a safe sequence are how engineers reason about resource safety even when they never write the algorithm out. Next, guide 4 turns to the opposite philosophy — let deadlock happen, then detect it on the wait-for graph and recover, or shrug and ignore it altogether.