In Deadlocks we learnt that a deadlock can happen only when four conditions hold at the same time: mutual exclusion, hold and wait, no preemption and circular wait. That gives us a very practical idea: if we can make sure that even one of these conditions never holds, deadlock becomes impossible.
This chapter covers two "do it before it happens" strategies:
Deadlock prevention: design the rules of the system so that one of the four conditions can never be true.
Deadlock avoidance: allow all four conditions, but look ahead before granting every request and refuse any request that could lead to deadlock. The most famous avoidance method is Dijkstra's Banker's algorithm.
The third strategy, letting deadlocks happen and then fixing them, is the topic of the next chapter, Deadlock Detection & Recovery.
Prevention vs Avoidance: The Basic Difference
Prevention | Avoidance | |
|---|---|---|
Idea | Break one of the four necessary conditions by design | Decide at run time, request by request, whether granting it is safe |
Advance information needed | None (just follow the rules) | Each process must declare its maximum need for every resource type |
When the check happens | Rules are built into the design or coding style | On every request |
Downside | Often lowers resource utilisation or concurrency | Run-time overhead; maximum needs are rarely known in practice |
Analogy | A road rule: "all traffic on this bridge goes one way only" | A traffic police officer who looks at the whole junction before letting each car in |
Deadlock Prevention: Breaking Each Condition
1. Breaking Mutual Exclusion
If a resource can be shared, nobody ever has to wait for it, so it cannot be part of a deadlock. For example, many processes can read the same read-only file at the same time.
Some resources can be made to look sharable with spooling: instead of giving the printer to one process, every process writes its output to a spool directory on disk, and only the printer daemon ever touches the real printer.
Limitation: many resources are inherently non-sharable. A mutex exists precisely to give exclusive access; making it sharable would bring back the race conditions it was meant to stop. So in general, we cannot prevent deadlocks by denying mutual exclusion.
2. Breaking Hold and Wait
We must make sure that a process never holds some resources while waiting for others. Two ways:
Request everything at once. A process asks for all the resources it will ever need before it starts. It either gets all of them or none of them.
Request only when holding nothing. Before asking for new resources, the process must release everything it currently holds.
Example: a process copies data from a DVD to a disk file and then prints the file.
Method 1: request {DVD drive, disk file, printer} at the start
→ printer sits idle for the entire copying phase
Method 2: request {DVD drive, disk file}, copy, release both
request {disk file, printer}, print, release both
→ better utilisation, but the file could be changed in between
Problems:
Low resource utilisation: resources are allocated long before they are used.
Starvation: a process that needs many popular resources may wait forever for all of them to be free at the same moment.
Programs often do not know in advance everything they will need.
3. Breaking No Preemption
Allow resources to be taken away. One common rule:
If a process holding some resources requests another resource that cannot be given immediately, it must release all the resources it currently holds. It is restarted later when it can get both its old and its new resources.
A variation: if the requested resource is held by another process that is itself waiting, take it from that waiting process.
This works well for resources whose state is easy to save and restore, such as CPU registers (that is exactly what a context switch does) and memory pages (they can be swapped out). It does not work for printers or for mutexes protecting half-updated data.
In thread code, the same idea appears as pthread_mutex_trylock(): try to get the second lock, and if that fails, unlock the first lock and start over. This prevents deadlock, but if threads keep retrying in lock-step you can get a livelock instead, which is why a short random delay before retrying is common.
4. Breaking Circular Wait (the practical one)
Give every resource type a unique number, and require every process to request resources only in increasing order of those numbers.
F(tape drive) = 1
F(disk) = 5
F(printer) = 12
A process holding the disk (5) may request the printer (12),
but NOT the tape drive (1). To get the tape drive it must first
release the disk, then request tape drive → disk → printer.
Why can no cycle form? Suppose there was a cycle P0 → P1 → … → Pk → P0, where each Pi holds Ri and waits for Ri+1 (held by the next process). Because every process only waits for a higher-numbered resource than the ones it holds, F(R0) < F(R1) < … < F(Rk) < F(R0). That says F(R0) < F(R0), which is impossible. So a circular wait cannot exist.
This is the method real programmers use. Large code bases, including the Linux kernel, document the order in which their locks must be taken, and the kernel's lockdep tool reports violations of that order.
Lock ordering in real code
Here is the classic bank-transfer problem. Two threads move money between two accounts in opposite directions, 100,000 times each. Every transfer needs both account locks. If each thread simply locks from first and then to, thread 1 locks A then B, and thread 2 locks B then A, exactly the deadlock from the previous chapter.
The fix is one rule: always lock the lower-numbered account first, no matter which direction the money flows.
#include <stdio.h>
#include <pthread.h>
#define ACCOUNTS 2
#define TRANSFERS 100000
int balance[ACCOUNTS] = {1000, 1000};
pthread_mutex_t lock[ACCOUNTS] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
/* Always lock the LOWER-numbered account first.
This gives every lock a global order, so circular wait is impossible. */
void transfer(int from, int to, int amount) {
int first = from < to ? from : to;
int second = from < to ? to : from;
pthread_mutex_lock(&lock[first]);
pthread_mutex_lock(&lock[second]);
balance[from] -= amount;
balance[to] += amount;
pthread_mutex_unlock(&lock[second]);
pthread_mutex_unlock(&lock[first]);
}
void *a_to_b(void *arg) { (void)arg; for (int i = 0; i < TRANSFERS; i++) transfer(0, 1, 1); return NULL; }
void *b_to_a(void *arg) { (void)arg; for (int i = 0; i < TRANSFERS; i++) transfer(1, 0, 1); return NULL; }
int main(void) {
pthread_t t1, t2;
pthread_create(&t1, NULL, a_to_b, NULL);
pthread_create(&t2, NULL, b_to_a, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("A = %d, B = %d, total = %d\n", balance[0], balance[1], balance[0] + balance[1]);
return 0;
}
gcc -std=c17 -Wall -Wextra -pthread ordered.c -o ordered
./ordered
A = 1000, B = 1000, total = 2000
It finishes every time, and the totals are correct because each transfer is protected by both locks. Both threads do the same number of 1-rupee transfers in opposite directions, so the balances end where they started.
We also tried the "obvious" version where first = from and second = to. It hung and had to be killed by timeout in all 5 of our test runs. With 100,000 transfers per thread, the unlucky timing that causes a deadlock is almost certain to happen at some point. Exactly when it hangs varies from run to run because thread scheduling is not deterministic.
Prevention summary
Condition broken | How | Practical? |
|---|---|---|
Mutual exclusion | Make resources sharable, spooling | Rarely; most resources are inherently exclusive |
Hold and wait | Request all at once, or release all before requesting | Low utilisation, possible starvation |
No preemption | Release held resources if a request fails; take resources from waiting processes | Only for resources whose state can be saved (CPU, memory) |
Circular wait | Global ordering of resources; request in increasing order | Yes, the most widely used |
Deadlock Avoidance: The Idea of a Safe State
Prevention is a set of rigid rules. Avoidance is smarter: it lets processes request resources in any order, but the OS checks every request and only grants it if the system will remain in a safe state.
For this, each process must declare up front the maximum number of instances of each resource type it may ever need.
A state is safe if there exists at least one order of all the processes <P1, P2, …, Pn>, called a safe sequence, such that for each Pi, the resources Pi may still request can be satisfied by the currently available resources plus the resources held by all Pj with j < i.
In plain words: even if every process suddenly asks for its maximum, there is some order in which the OS can run them all to completion. P1 can finish with what is free now; when it finishes and returns its resources, P2 can finish; and so on.
A single-resource example
A system has 10 instances of one resource and three processes:
Process | Maximum need | Currently holds | May still need |
|---|---|---|---|
P0 | 8 | 4 | 4 |
P1 | 3 | 1 | 2 |
P2 | 6 | 3 | 3 |
Held = 4 + 1 + 3 = 8, so free = 2.
P1 needs 2 ≤ free 2 → P1 can finish, releases 1 → free = 2 + 1 = 3
P2 needs 3 ≤ free 3 → P2 can finish, releases 3 → free = 3 + 3 = 6
P0 needs 4 ≤ free 6 → P0 can finish, releases 4 → free = 6 + 4 = 10
Safe sequence: <P1, P2, P0> → the state is SAFE
Now suppose P2 asks for 1 more instance. One instance is free, so the OS could give it. But look at the state that would result: free = 1, and P0 still needs 4, P1 needs 2, P2 needs 2. Nobody can be guaranteed to finish. That state is unsafe, so an avoidance algorithm makes P2 wait, even though the resource is physically available.
Safe, unsafe and deadlocked states
+---------------------------------------------------+
| All possible states |
| |
| +-----------+ +--------------------------+ |
| | SAFE | | UNSAFE | |
| | | | +-------------+ | |
| | no | | | DEADLOCK | | |
| | deadlock | | +-------------+ | |
| +-----------+ +--------------------------+ |
+---------------------------------------------------+
A safe state is never a deadlock.
Every deadlock is an unsafe state.
An unsafe state is not necessarily a deadlock. It only means the OS can no longer guarantee that deadlock will be avoided. If processes happen to release resources before asking for their full maximum, everything might still finish fine.
Avoidance simply never lets the system leave the safe region.
Avoidance with Single-Instance Resources: Claim Edges
If every resource type has exactly one instance, we can use a modified Resource Allocation Graph (from Deadlocks) with a third kind of edge:
Claim edge P ⇢ R (drawn dashed): P may request R at some point in the future. All claim edges are declared before P starts.
When P actually requests R, the claim edge becomes a request edge. When R is allocated, it becomes an assignment edge. When P releases R, it turns back into a claim edge.
Rule: grant a request only if converting the request edge P → R into the assignment edge R → P does not create a cycle in the graph (counting claim edges too). A cycle would mean an unsafe state. Checking for a cycle takes O(n²) time for n processes.
P1 holds R1 and has a claim on R2. P2 has claims on R1 and R2.
P2 now requests R2 (which is free).
If granted: R2 → P2, P2 ⇢ R1 (claim), R1 → P1, P1 ⇢ R2 (claim)
→ cycle P1 ⇢ R2 → P2 ⇢ R1 → P1 → UNSAFE, P2 must wait
This does not work when a resource type has several instances. For that we need the Banker's algorithm.
The Banker's Algorithm
The Banker's algorithm was proposed by Edsger Dijkstra. The name comes from a bank that must never lend out its cash in such a way that it can no longer satisfy all its customers. Each customer has a credit limit (maximum need); the bank gives a loan only if, after giving it, there is still some order in which every customer could be paid up to their limit and repay.
Data structures
For n processes and m resource types:
Name | Size | Meaning |
|---|---|---|
| m | Available[j] = number of free instances of resource type Rj |
| n × m | Max[i][j] = maximum instances of Rj that Pi may ever request |
| n × m | Allocation[i][j] = instances of Rj currently held by Pi |
| n × m | Need[i][j] = Max[i][j] − Allocation[i][j], what Pi may still ask for |
We write X ≤ Y for vectors when every element of X is ≤ the matching element of Y. For example (1, 2, 1) ≤ (2, 2, 2) is true, but (2, 0, 3) ≤ (2, 2, 2) is false because 3 > 2.
The algorithm has two parts: the safety algorithm (is this state safe?) and the resource-request algorithm (should this request be granted?).
Part 1: Safety algorithm
1. Work = Available (copy)
Finish[i] = false for all i
2. Find an i such that
Finish[i] == false AND Need[i] ≤ Work
If no such i exists, go to step 4.
3. Pretend P[i] runs to completion and returns everything:
Work = Work + Allocation[i]
Finish[i] = true
Go to step 2.
4. If Finish[i] == true for all i → state is SAFE
otherwise → state is UNSAFE
Why do we add Allocation[i] and not Max[i]? Because a finished process gives back what it holds. Temporarily it would also borrow Need[i] from Work, but it returns that too, so the net change is +Allocation[i].
Time complexity: up to n passes, each scanning n processes and comparing m values, so O(m × n²).
Part 2: Resource-request algorithm
When process Pi makes a request vector Request[i]:
1. If Request[i] > Need[i] → ERROR: process exceeded its declared maximum
2. If Request[i] > Available → P[i] must WAIT (resources not free)
3. Pretend to allocate:
Available = Available − Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] − Request[i]
4. Run the safety algorithm on this pretend state.
SAFE → grant the request (keep the new state)
UNSAFE → undo step 3, P[i] must WAIT
Banker's Algorithm: A Complete Worked Example
A system has 5 processes P0 to P4 and three resource types A, B, C with 9, 5 and 7 instances in total. At time T0 the state is:
Process | Allocation (A B C) | Max (A B C) |
|---|---|---|
P0 | 1 1 0 | 6 3 2 |
P1 | 2 0 1 | 3 2 2 |
P2 | 3 1 1 | 5 1 3 |
P3 | 1 1 1 | 2 2 2 |
P4 | 0 0 2 | 4 3 3 |
Step 1: Compute Available
Total allocated = (1+2+3+1+0, 1+0+1+1+0, 0+1+1+1+2) = (7, 3, 5)
Available = (9, 5, 7) − (7, 3, 5) = (2, 2, 2)
Step 2: Compute Need = Max − Allocation
Process | Need (A B C) |
|---|---|
P0 | 6−1, 3−1, 2−0 = 5 2 2 |
P1 | 3−2, 2−0, 2−1 = 1 2 1 |
P2 | 5−3, 1−1, 3−1 = 2 0 2 |
P3 | 2−1, 2−1, 2−1 = 1 1 1 |
P4 | 4−0, 3−0, 3−2 = 4 3 1 |
Step 3: Run the safety algorithm
We use a simple rule to pick the next process: each time, scan from P0 upward and take the first unfinished process whose Need ≤ Work.
Work = (2, 2, 2)
Pass 1: P0 Need (5,2,2) ≤ (2,2,2)? No (5 > 2)
P1 Need (1,2,1) ≤ (2,2,2)? Yes → Work = (2,2,2) + (2,0,1) = (4,2,3)
Pass 2: P0 Need (5,2,2) ≤ (4,2,3)? No (5 > 4)
P2 Need (2,0,2) ≤ (4,2,3)? Yes → Work = (4,2,3) + (3,1,1) = (7,3,4)
Pass 3: P0 Need (5,2,2) ≤ (7,3,4)? Yes → Work = (7,3,4) + (1,1,0) = (8,4,4)
Pass 4: P3 Need (1,1,1) ≤ (8,4,4)? Yes → Work = (8,4,4) + (1,1,1) = (9,5,5)
Pass 5: P4 Need (4,3,1) ≤ (9,5,5)? Yes → Work = (9,5,5) + (0,0,2) = (9,5,7)
All Finish = true → SAFE
Safe sequence: <P1, P2, P0, P3, P4>
Notice the final Work (9, 5, 7) equals the total resources. That is a handy self-check: once everyone has finished, everything must be back.
A safe state usually has more than one safe sequence. If you scan in a different order you may get, for example, <P1, P3, P2, P0, P4>, which is also correct. In fact, by trying all 120 orderings of the five processes we found that 48 of them are safe sequences for this state. In an exam, any valid sequence is accepted unless a specific scanning rule is given.
Step 4: Handling requests
Each of the following requests is checked independently against the T0 state above.
Request A: P1 requests (1, 0, 1)
1. Request (1,0,1) ≤ Need[P1] (1,2,1)? Yes
2. Request (1,0,1) ≤ Available (2,2,2)? Yes
3. Pretend: Available = (2,2,2) − (1,0,1) = (1,2,1)
Allocation[P1] = (2,0,1) + (1,0,1) = (3,0,2)
Need[P1] = (1,2,1) − (1,0,1) = (0,2,0)
4. Safety check, Work = (1,2,1):
P0 (5,2,2)? No. P1 (0,2,0)? Yes → Work = (1,2,1) + (3,0,2) = (4,2,3)
P0 (5,2,2)? No. P2 (2,0,2)? Yes → Work = (4,2,3) + (3,1,1) = (7,3,4)
P0 (5,2,2)? Yes → Work = (8,4,4)
P3 (1,1,1)? Yes → Work = (9,5,5)
P4 (4,3,1)? Yes → Work = (9,5,7)
SAFE, sequence <P1, P2, P0, P3, P4>
→ GRANT the request.
Request B: P4 requests (2, 2, 0)
1. Request (2,2,0) ≤ Need[P4] (4,3,1)? Yes
2. Request (2,2,0) ≤ Available (2,2,2)? Yes (the resources ARE free)
3. Pretend: Available = (2,2,2) − (2,2,0) = (0,0,2)
Need[P4] = (4,3,1) − (2,2,0) = (2,1,1)
4. Safety check, Work = (0,0,2):
P0 needs (5,2,2) No
P1 needs (1,2,1) No
P2 needs (2,0,2) No
P3 needs (1,1,1) No
P4 needs (2,1,1) No
Nobody can proceed → UNSAFE
→ Undo, P4 must WAIT.
This is the heart of avoidance: the resources were physically available, but giving them away would have left the system with only (0, 0, 2) free and no process guaranteed to finish.
Request C: P0 requests (3, 0, 0)
1. Request (3,0,0) ≤ Need[P0] (5,2,2)? Yes
2. Request (3,0,0) ≤ Available (2,2,2)? No (3 > 2)
→ P0 must WAIT (not enough free resources; no safety check needed).
Request D: P3 requests (2, 0, 0)
1. Request (2,0,0) ≤ Need[P3] (1,1,1)? No (2 > 1)
→ ERROR: P3 is asking for more than it declared as its maximum.
Banker's Algorithm in C
Here is a compact implementation of both parts, using the same example. The request() function undoes its pretend allocation at the end so that each demo request starts from the T0 state, matching the worked example. A real OS would keep the new state when a request is granted.
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define N 5 /* processes */
#define M 3 /* resource types */
int available[M] = {2, 2, 2};
int max_need[N][M] = {{6,3,2}, {3,2,2}, {5,1,3}, {2,2,2}, {4,3,3}};
int allocation[N][M] = {{1,1,0}, {2,0,1}, {3,1,1}, {1,1,1}, {0,0,2}};
int need[N][M];
/* Safety algorithm: returns true if the current state is safe
and fills seq[] with one safe sequence. */
bool is_safe(int seq[N]) {
int work[M];
bool finish[N] = {false};
memcpy(work, available, sizeof work);
for (int count = 0; count < N; count++) {
int found = -1;
for (int i = 0; i < N && found == -1; i++) {
if (finish[i]) continue;
bool fits = true;
for (int j = 0; j < M; j++)
if (need[i][j] > work[j]) { fits = false; break; }
if (fits) found = i;
}
if (found == -1) return false; /* nobody can finish */
for (int j = 0; j < M; j++) /* pretend it finishes */
work[j] += allocation[found][j];
finish[found] = true;
seq[count] = found;
}
return true;
}
/* Resource-request algorithm for process p. */
void request(int p, const int req[M]) {
printf("P%d requests (%d,%d,%d): ", p, req[0], req[1], req[2]);
for (int j = 0; j < M; j++)
if (req[j] > need[p][j]) { printf("ERROR, exceeds its declared maximum\n"); return; }
for (int j = 0; j < M; j++)
if (req[j] > available[j]) { printf("not enough available, P%d must WAIT\n", p); return; }
for (int j = 0; j < M; j++) { /* pretend to grant */
available[j] -= req[j];
allocation[p][j] += req[j];
need[p][j] -= req[j];
}
int seq[N];
if (is_safe(seq)) {
printf("safe, GRANTED. Safe sequence:");
for (int i = 0; i < N; i++) printf(" P%d", seq[i]);
printf("\n");
} else {
printf("would be UNSAFE, P%d must WAIT\n", p);
}
for (int j = 0; j < M; j++) { /* undo, so each demo request */
available[j] += req[j]; /* starts from the same state */
allocation[p][j] -= req[j];
need[p][j] += req[j];
}
}
int main(void) {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
need[i][j] = max_need[i][j] - allocation[i][j];
int seq[N];
if (is_safe(seq)) {
printf("Initial state is SAFE. Safe sequence:");
for (int i = 0; i < N; i++) printf(" P%d", seq[i]);
printf("\n");
} else {
printf("Initial state is UNSAFE\n");
}
request(1, (int[]){1, 0, 1});
request(4, (int[]){2, 2, 0});
request(0, (int[]){3, 0, 0});
request(3, (int[]){2, 0, 0});
return 0;
}
gcc -std=c17 -Wall -Wextra bankers.c -o bankers
./bankers
Initial state is SAFE. Safe sequence: P1 P2 P0 P3 P4
P1 requests (1,0,1): safe, GRANTED. Safe sequence: P1 P2 P0 P3 P4
P4 requests (2,2,0): would be UNSAFE, P4 must WAIT
P0 requests (3,0,0): not enough available, P0 must WAIT
P3 requests (2,0,0): ERROR, exceeds its declared maximum
The output matches our hand calculation exactly.
Why Isn't the Banker's Algorithm Used Everywhere?
It is elegant, and it is a favourite exam topic, but general-purpose operating systems do not use it for ordinary programs:
Maximum needs are rarely known. How many locks, files or memory pages will a web browser need in its lifetime? Nobody knows in advance.
The number of processes changes constantly, while the algorithm assumes a fixed set.
Resources can disappear, for example when a device is unplugged or fails.
Overhead: O(m × n²) work on every single request is expensive when there are thousands of processes and lock operations happen millions of times per second.
It is conservative: it refuses requests that lead to unsafe states even though many unsafe states would never actually deadlock, so resources may sit idle.
The ideas still matter. Systems that do know their resource needs ahead of time, such as some batch, embedded and real-time systems, can use avoidance, and the safety check is the same idea that the detection algorithm in the next chapter reuses.
Common Mistakes
Comparing Request with Max instead of Need. Step 1 of the request algorithm compares with
Need, which is what the process may still request.Adding Need or Max to Work in the safety algorithm. A finishing process returns its Allocation.
Granting a request because the resources are free. Being free is necessary but not enough; the resulting state must also be safe (Request B above).
"Unsafe means deadlock." Unsafe only means deadlock is possible. Every deadlock is unsafe, but not every unsafe state is a deadlock.
Thinking there is only one safe sequence. There can be many; any one is enough to prove safety.
Forgetting to undo the pretend allocation when the new state is unsafe.
Mixing up prevention and avoidance. Prevention breaks a Coffman condition by design. Avoidance keeps all four conditions possible and checks each request at run time.
Interview Questions
What is the difference between deadlock prevention and deadlock avoidance?
Prevention ensures at least one of the four necessary conditions can never hold, using design rules such as lock ordering. Avoidance allows all conditions but checks each request at run time and grants it only if the system stays in a safe state; it needs each process's maximum need in advance.
Which deadlock condition is most commonly broken in practice, and how?
Circular wait, by imposing a global order on locks or resources and always acquiring them in that order. It costs almost nothing at run time.
Why can't we usually prevent deadlock by breaking mutual exclusion?
Because many resources, such as mutexes and printers, are inherently non-sharable. Making them sharable would break correctness.
What is a safe state?
A state in which there exists a safe sequence: an order of all processes such that each one can obtain its remaining maximum need from the currently free resources plus the resources released by the processes before it in the order.
Is every unsafe state a deadlock?
No. An unsafe state means the system cannot guarantee freedom from deadlock. A deadlock may or may not actually occur, depending on what the processes request next.
What data structures does the Banker's algorithm use?
Available (vector of size m), Max, Allocation and Need (each n × m matrices), where Need = Max − Allocation.
What is the time complexity of the Banker's safety algorithm?
O(m × n²) for n processes and m resource types.
Why is the Banker's algorithm rarely used in real operating systems?
Processes rarely know their maximum needs in advance, the set of processes and resources keeps changing, and running the safety check on every request is too costly. It is also conservative and can leave resources idle.
In the safety algorithm, why do we add Allocation[i] to Work?
Because when process i finishes, it releases everything it holds. The extra Need[i] it temporarily borrowed is also returned, so the net gain to Work is Allocation[i].
Summary
Prevention breaks one Coffman condition by design: sharable resources (mutual exclusion), all-at-once requests (hold and wait), forced release (no preemption), or a global resource order (circular wait).
Lock ordering (breaking circular wait) is the most practical prevention technique and the one used in real code.
Avoidance grants a request only if the system remains in a safe state, a state with at least one safe sequence.
Safe ⇒ no deadlock. Deadlock ⇒ unsafe. Unsafe does not necessarily mean deadlock.
For single-instance resources, avoidance uses a RAG with claim edges and refuses requests that would create a cycle.
The Banker's algorithm handles multiple instances using Available, Max, Allocation and Need = Max − Allocation, with a safety algorithm (O(m × n²)) and a resource-request algorithm.
Request handling: Request ≤ Need (else error), Request ≤ Available (else wait), pretend to allocate, grant only if the result is safe.
Avoidance is expensive and needs information we rarely have. The alternative is to let deadlocks happen and then clean up, which is what we study next in Deadlock Detection & Recovery.