Chapter 22 of 38

Deadlock Prevention & Avoidance (Banker's Algorithm)

On this page

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:

  1. 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.

  2. 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

Available

m

Available[j] = number of free instances of resource type Rj

Max

n × m

Max[i][j] = maximum instances of Rj that Pi may ever request

Allocation

n × m

Allocation[i][j] = instances of Rj currently held by Pi

Need

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.