SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 29
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 29 of 90

Deadlocks 2: avoidance, Banker's algorithm, detection and recovery

deadlock avoidancesafe stateunsafe statesafe sequenceBanker's algorithm (Available, Max, Allocation, Need matrices)resource-request algorithmBanker's numericalsdeadlock detection algorithmrecovery by process termination and resource preemptionrollbackvictim selectionostrich algorithmminimum resources to avoid deadlock numericals

These are the notes for CS Fundamentals for Placements, episode 29. Last episode we prevented deadlocks by making one of the four Coffman conditions impossible. Prevention works, but it is strict and wastes resources. Today: deadlock avoidance (look ahead and refuse any request that could lead to trouble), with safe states, safe sequences and the Banker's algorithm; then deadlock detection and recovery; the ostrich algorithm; and the minimum-resources numerical that appears in almost every exam. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags) and run on Linux x86-64 on 4 November 2026. All of today's programs are single-threaded and deterministic, so they print the same output on every run.

Quick refresher

  • A deadlock is a set of processes each waiting forever for a resource held by another process in the set (episode 28).
  • A resource is anything a process needs and may wait for (a printer, a lock, memory). A resource type can have several identical instances (units), e.g. 3 printers.
  • Prevention makes one Coffman condition (mutual exclusion, hold and wait, no preemption, circular wait) impossible.
  • The four ways to handle deadlocks: prevention, avoidance, detection and recovery, and ignoring the problem. Today covers the last three.

The moneylender's problem

A moneylender has ₹12 lakh in his safe and lends it one lakh at a time. Three builders borrow from him, and before starting each one declares the most he could ever need, his maximum claim:

Builder Maximum claim
Kiran 10 lakh
Meera 4 lakh
Arjun 9 lakh

A builder can't repay halfway (half a building earns nothing): he repays everything only when his project is complete. That is exactly how a process behaves: it releases its resources when it finishes.

The obvious rule: lend whenever there is cash

#include <stdio.h>
// A moneylender has 12 lakh. Three builders borrow 1 lakh at a time.
// A builder repays everything only after reaching the full amount.
int main(void) {
    int cash = 12, maxneed[3] = {10, 4, 9}, has[3] = {0}, finished = 0;
    char *name[3] = {"Kiran", "Meera", "Arjun"};
    for (int round = 1; round <= 50 && finished < 3; round++) {
        int moved = 0;
        for (int i = 0; i < 3; i++) {
            if (has[i] == maxneed[i] || cash == 0) continue;
            cash--; has[i]++; moved = 1;     // naive: lend whenever cash exists
            if (has[i] == maxneed[i]) {      // project done: repay everything
                printf("%s finishes, repays %d\n", name[i], has[i]);
                cash += has[i]; has[i] = 0; maxneed[i] = 0; finished++;
            }
        }
        if (!moved) { printf("stuck: cash %d, Kiran %d, Meera %d, Arjun %d\n",
                             cash, has[0], has[1], has[2]); return 0; }
    }
    printf("all %d finished\n", finished);
}

Output:

Meera finishes, repays 4
stuck: cash 0, Kiran 6, Meera 0, Arjun 6

Meera finishes, but then Kiran holds 6 and needs 4 more, Arjun holds 6 and needs 3 more, and the safe is empty. Neither can finish, so neither will ever repay. Twelve lakh, frozen: a deadlock.

Safe and unsafe states

A state of the system is a snapshot: who holds what, what each could still ask for, and what is free right now.

A state is safe if there is some order in which every process can get its remaining need from what is free (plus what earlier processes in the order give back), finish, and release everything. That order is a safe sequence.

A state with no safe sequence is unsafe.

Meaning
Safe state The system can guarantee that every process finishes: no deadlock
Unsafe state No guarantee. A deadlock may follow (if processes really ask for their maximums), but it hasn't happened yet
Deadlocked state Some processes can never continue

So: every deadlocked state is unsafe, but not every unsafe state is deadlocked (deadlocked ⊂ unsafe). A builder might finish under budget and repay early; the system just can't count on it.

Example of an unsafe state: cash 3, Kiran holds 6 (needs 4), Arjun holds 3 (needs 6). Nobody's remaining need fits in 3.

Checking a state by hand

Builder Holds Max Needs (Max - Holds)
Kiran 5 10 5
Meera 2 4 2
Arjun 2 9 7

Free cash = 12 - (5 + 2 + 2) = 3.

  1. Meera needs 2 ≤ 3. She finishes and repays 2 → free = 5.
  2. Kiran needs 5 ≤ 5. He finishes and repays 5 → free = 10.
  3. Arjun needs 7 ≤ 10. He finishes and repays 2 → free = 12.

Safe sequence: ⟨Meera, Kiran, Arjun⟩, so the state is safe.

Deadlock avoidance

Deadlock avoidance: before granting any request, pretend to grant it and check whether the new state is still safe. If it is, grant it. If not, the process waits, even if the resource is free right now. The system never enters an unsafe state, so it never deadlocks.

The moneylender with the new rule

#include <stdio.h>
int cash = 12, maxneed[3] = {10, 4, 9}, has[3] = {0};
char *name[3] = {"Kiran", "Meera", "Arjun"};
int safe(void) {             // can EVERYONE still finish, in some order?
    int c = cash, done[3] = {0};
    for (int k = 0; k < 3; k++)
        for (int i = 0; i < 3; i++)
            if (!done[i] && maxneed[i] - has[i] <= c) { c += has[i]; done[i] = 1; }
    return done[0] && done[1] && done[2];
}
int main(void) {
    for (int finished = 0, round = 1; finished < 3 && round <= 50; round++)
        for (int i = 0; i < 3; i++) {
            if (has[i] == maxneed[i] || cash == 0) continue;
            cash--; has[i]++;                       // pretend to lend
            if (!safe()) { cash++; has[i]--; continue; }  // unsafe: say "wait"
            if (has[i] == maxneed[i]) {
                printf("%s finishes, repays %d\n", name[i], has[i]);
                cash += has[i]; has[i] = 0; maxneed[i] = 0; finished++;
            }
        }
    printf("cash back to %d\n", cash);
}

Output:

Meera finishes, repays 4
Arjun finishes, repays 9
Kiran finishes, repays 10
cash back to 12

Same builders, same money, no deadlock. The only difference: sometimes the lender said "not now".

The Banker's algorithm

Real computers have many resource types (printers, scanners, tape drives, ...), each with several instances. The single number "cash" becomes a list. The Banker's algorithm, by Edsger Dijkstra, was developed while designing the THE operating system; its name comes from the fact that it could be used in a banking system, by a banker who never lends himself into trouble.

With n processes and m resource types, it keeps four data structures:

Name Shape Meaning
Available vector of m numbers free units of each type right now
Max n × m matrix the maximum demand of each process for each type (declared in advance)
Allocation n × m matrix units of each type each process holds now
Need n × m matrix Need = Max - Allocation: what each process may still ask for

A vector is a list of numbers; a matrix is a table of numbers with rows and columns. "Need[i] ≤ Work" means every column of row i is ≤ the matching entry of Work.

The safety algorithm

  1. Let Work = Available, and Finish[i] = false for every process i.
  2. Find a process i with Finish[i] == false and Need[i] ≤ Work.
  3. Pretend it runs to completion and releases everything: Work = Work + Allocation[i], Finish[i] = true. Go back to step 2.
  4. When no such i is left: if Finish[i] is true for all i, the state is safe (the order you picked them in is a safe sequence); otherwise it is unsafe.

Cost: up to m × n² operations (n passes, each checking up to n processes with m columns), which is one reason real systems rarely run it on every request.

Numerical: 5 processes, 3 types

Total resources: A = 8, B = 5, C = 7.

Process Allocation (A B C) Max (A B C) Need = Max - Alloc (A B C)
P0 1 1 0 5 3 2 4 2 2
P1 2 0 1 3 2 2 1 2 1
P2 2 1 1 7 2 3 5 1 2
P3 0 1 2 2 2 4 2 1 2
P4 1 0 1 4 3 3 3 3 2
Sum 6 3 5

Available = Total - sum of Allocation = (8, 5, 7) - (6, 3, 5) = (2, 2, 2).

Trace (scanning P0 to P4, repeating passes):

Step Check Fits? Work after
start (2, 2, 2)
P0 (4,2,2) ≤ (2,2,2)? no (A)
P1 (1,2,1) ≤ (2,2,2)? yes (2,2,2) + (2,0,1) = (4, 2, 3)
P2 (5,1,2) ≤ (4,2,3)? no (A)
P3 (2,1,2) ≤ (4,2,3)? yes + (0,1,2) = (4, 3, 5)
P4 (3,3,2) ≤ (4,3,5)? yes + (1,0,1) = (5, 3, 6)
P0 (4,2,2) ≤ (5,3,6)? yes + (1,1,0) = (6, 4, 6)
P2 (5,1,2) ≤ (6,4,6)? yes + (2,1,1) = (8, 5, 7)

Safe sequence ⟨P1, P3, P4, P0, P2⟩: the state is safe. Self-check: the final Work equals the Total (8, 5, 7), as it always must. Other orders can also be safe (for example ⟨P1, P3, P0, P2, P4⟩, see Practice 1); any one valid sequence is a correct answer.

The safety algorithm in C

#include <stdio.h>
enum { P = 5, R = 3 };                            // 5 processes, 3 types
int avail[R] = {2, 2, 2};                         // free A, B, C
int alloc[P][R] = {{1,1,0}, {2,0,1}, {2,1,1}, {0,1,2}, {1,0,1}};
int maxm[P][R]  = {{5,3,2}, {3,2,2}, {7,2,3}, {2,2,4}, {4,3,3}};
int safe(int print) {
    int work[R], finish[P] = {0}, count = 0, found = 1;
    for (int j = 0; j < R; j++) work[j] = avail[j];
    while (count < P && found) {
        found = 0;
        for (int i = 0; i < P; i++) {
            int ok = !finish[i];                   // need = max - alloc <= work?
            for (int j = 0; j < R; j++) if (maxm[i][j] - alloc[i][j] > work[j]) ok = 0;
            if (!ok) continue;
            for (int j = 0; j < R; j++) work[j] += alloc[i][j];  // finishes, returns all
            finish[i] = 1; count++; found = 1; if (print) printf("P%d ", i);
        }
    }
    return count == P;                             // could everyone finish?
}
int main(void) {
    printf("safe sequence: "); int s = safe(1);
    printf("\n%s\n", s ? "SAFE" : "UNSAFE");
}

Output:

safe sequence: P1 P3 P4 P0 P2 
SAFE

enum { P = 5, R = 3 }; simply gives the names P and R to the constants 5 and 3 (an enum is a list of named integer constants).

The resource-request algorithm

When process i asks for a vector Request_i while running:

  1. If Request_i > Need[i] (in any column): error, the process asked for more than its declared maximum.
  2. If Request_i > Available (in any column): the process must wait: the units aren't free.
  3. Pretend to grant it: Available -= Request_i; Allocation[i] += Request_i; Need[i] -= Request_i.
  4. Run the safety algorithm on the pretend state. Safe → grant for real. Unsafe → undo the three changes, and the process waits.
#include <stdio.h>
enum { P = 5, R = 3 };
int avail[R] = {2, 2, 2};                         // free A, B, C
int alloc[P][R] = {{1,1,0}, {2,0,1}, {2,1,1}, {0,1,2}, {1,0,1}};
int maxm[P][R]  = {{5,3,2}, {3,2,2}, {7,2,3}, {2,2,4}, {4,3,3}};
int safe(void) {                                  // the safety algorithm, compact
    int work[R], fin[P] = {0}, count = 0, found = 1, i, j, ok;
    for (j = 0; j < R; j++) work[j] = avail[j];
    while (count < P && found) for (found = 0, i = 0; i < P; i++) {
        for (ok = !fin[i], j = 0; j < R; j++) if (maxm[i][j] - alloc[i][j] > work[j]) ok = 0;
        if (ok) { for (j = 0; j < R; j++) work[j] += alloc[i][j]; fin[i] = found = 1; count++; }
    }
    return count == P; }
void request(int i, int a, int b, int c) {
    int req[R] = {a, b, c}, j, ok = 1;
    printf("P%d asks (%d,%d,%d): ", i, a, b, c);
    for (j = 0; j < R; j++) if (req[j] > maxm[i][j] - alloc[i][j]) ok = 0;
    if (!ok) { printf("ERROR, more than its max\n"); return; }
    for (j = 0; j < R; j++) if (req[j] > avail[j]) ok = 0;
    if (!ok) { printf("wait, not free now\n"); return; }
    for (j = 0; j < R; j++) { avail[j] -= req[j]; alloc[i][j] += req[j]; }   // pretend
    if (safe()) { printf("GRANTED, still safe\n"); return; }
    for (j = 0; j < R; j++) { avail[j] += req[j]; alloc[i][j] -= req[j]; }   // undo
    printf("wait, would be UNSAFE\n");
}
int main(void) {
    request(0, 2, 0, 0); request(4, 3, 0, 0);
    request(1, 1, 0, 1); request(2, 0, 3, 0);
}

Output:

P0 asks (2,0,0): wait, would be UNSAFE
P4 asks (3,0,0): wait, not free now
P1 asks (1,0,1): GRANTED, still safe
P2 asks (0,3,0): ERROR, more than its max

Working the first one by hand: after pretending to give P0 (2,0,0), Available = (0, 2, 2), Allocation[P0] = (3, 1, 0), Need[P0] = (2, 2, 2). Now check every Need: P0 (2,2,2), P1 (1,2,1), P2 (5,1,2), P3 (2,1,2), P4 (3,3,2): every one needs at least 1 A, and 0 A are free. Nobody can finish → unsafe → P0 waits, even though the 2 A were free.

The third request, P1 (1,0,1): Available becomes (1, 2, 1), Need[P1] = (0, 2, 0) fits, P1 finishes and returns (3, 0, 2) → (4, 2, 3), and from there the same order as before works. Safe → granted.

The price of avoidance

  • Every process must declare its maximum claim in advance, and most real programs can't know it.
  • The number of processes and resources must stay fixed while the algorithm runs.
  • Every request costs a safety check (up to m × n² steps).
  • Processes wait even when units are free, so resource utilisation is lower.

So many systems choose the opposite approach: grant requests freely and deal with deadlocks if they happen.

Deadlock detection

Deadlock detection: grant requests freely, and periodically (for example every few minutes, or when CPU utilisation drops suspiciously) check whether a deadlock exists.

  • Single-instance resources: look for a cycle in the wait-for graph (episode 28).
  • Multiple instances: the detection algorithm, which is the safety algorithm with two changes: 1. Use Request (what each process is waiting for right now) instead of Need (the most it might ask for). Detection asks "is anyone stuck now?", not "could anyone get stuck later?". 2. A process holding nothing (Allocation = 0) is marked finished at the start: it can't be part of a deadlock.

Processes still unfinished at the end are deadlocked.

Detection in C

Four processes, nothing free:

Process Allocation (A B C) Request (A B C)
P0 1 0 0 0 0 0
P1 0 1 1 2 0 0
P2 1 1 0 0 0 1
P3 0 0 1 0 1 0
#include <stdio.h>
enum { P = 4, R = 3 };
int avail[R] = {0, 0, 0};                         // free A, B, C right now
int alloc[P][R] = {{1,0,0}, {0,1,1}, {1,1,0}, {0,0,1}};
int req[P][R]   = {{0,0,0}, {2,0,0}, {0,0,1}, {0,1,0}};   // waiting for (not Need!)
void detect(void) {
    int work[R], fin[P], found = 1, i, j, ok;
    for (j = 0; j < R; j++) work[j] = avail[j];
    for (i = 0; i < P; i++) fin[i] = 0;
    while (found) for (found = 0, i = 0; i < P; i++) {
        for (ok = !fin[i], j = 0; j < R; j++) if (req[i][j] > work[j]) ok = 0;
        if (ok) { for (j = 0; j < R; j++) work[j] += alloc[i][j]; fin[i] = found = 1; }
    }
    printf("deadlocked:");
    for (found = 0, i = 0; i < P; i++) if (!fin[i]) { printf(" P%d", i); found = 1; }
    printf(found ? "\n" : " none\n");
}
int main(void) {
    detect();
    printf("abort P3, take back its resources\n");
    for (int j = 0; j < R; j++) { avail[j] += alloc[3][j]; alloc[3][j] = req[3][j] = 0; }
    detect();
}

Output:

deadlocked: P1 P2 P3
abort P3, take back its resources
deadlocked: none

By hand: Work = (0,0,0). P0 requests nothing → finishes, Work = (1,0,0). P1 wants 2 A (only 1), P2 wants 1 C (0), P3 wants 1 B (0): nobody else can go. Deadlocked: P1, P2, P3. After aborting P3, its C returns: Work = (1,0,1). P2 gets its C, finishes, Work = (2,1,1). P1 gets 2 A and finishes. No deadlock.

Recovery from deadlock

Method How Cost
Process termination: abort all deadlocked processes Kill every process in the deadlock Simple, but all their work is lost
Process termination: one at a time Abort one victim, rerun detection, repeat Less waste, but detection runs many times
Resource preemption Take resources away from a victim and give them to others The victim must be rolled back
  • Rollback: returning a process to an earlier saved state, called a checkpoint (a snapshot of its state saved on purpose), or restarting it from the beginning (total rollback), so it can later redo the work.
  • Victim selection: the process picked to lose. Choose the cheapest: lowest priority, least work done so far, fewest resources held, most still needed, interactive vs batch.
  • Starvation risk: if the same process is always the cheapest, it is picked every time and never finishes. Fix: include the number of times it has been rolled back in the cost.

The ostrich algorithm

Prevention and avoidance cost something on every request, forever. In a desktop OS, a deadlock between ordinary programs might happen once in months. So the OS simply ignores the problem: the ostrich algorithm, named after the "ostrich effect", sticking one's head in the sand and pretending there is no problem.

If a deadlock does happen, the user kills the frozen program or restarts the machine. UNIX and Windows take this approach for user programs (ignoring deadlock was also the initial approach of MINIX and UNIX). Inside the kernel, developers still prevent deadlocks carefully, with lock ordering.

Strategy Idea Cost Used where
Prevention Make one Coffman condition impossible Strict rules, idle resources Lock ordering in kernels and apps
Avoidance Never enter an unsafe state (Banker's) Max claims in advance, checks on every request Rare: some embedded and real-time systems
Detection + recovery Let it happen, find it, fix it Detection runs; lost work Databases (they abort a transaction)
Ignore (ostrich) Assume it won't happen A rare hang UNIX, Windows (for user programs)

Numerical: minimum resources to rule out deadlock

n processes share one resource type; each needs at most k units. What is the minimum number of units R so that deadlock is impossible?

Worst case: every process holds k - 1 units and asks for one more. That uses n(k - 1) units. If none are left, everyone waits forever. With one more unit, some process gets its k-th unit, finishes, and releases all k, and then everyone else can finish too.

R_min = n(k - 1) + 1

Example: 3 processes, each needs up to 3 printers → 3 × 2 + 1 = 7.

Checked by brute force in C

#include <stdio.h>
// 3 processes, each may need up to 3 printers. How many printers rule out deadlock?
int main(void) {
    int n = 3, k = 3;
    for (int R = 4; R <= 8; R++) {
        int bad = 0;
        for (int a = 0; a < k && !bad; a++)          // a, b, c: printers each one holds
            for (int b = 0; b < k && !bad; b++)
                for (int c = 0; c < k && !bad; c++) {
                    int free = R - a - b - c;
                    if (free < 0) continue;          // more than we own: impossible
                    // stuck if nobody can get what it still needs
                    if (k - a > free && k - b > free && k - c > free) {
                        printf("R = %d: deadlock possible, holding %d,%d,%d\n", R, a, b, c);
                        bad = 1;
                    }
                }
        if (!bad) printf("R = %d: deadlock impossible\n", R);
    }
    printf("formula n(k-1)+1 = %d\n", n * (k - 1) + 1);
}

Output:

R = 4: deadlock possible, holding 0,2,2
R = 5: deadlock possible, holding 1,2,2
R = 6: deadlock possible, holding 2,2,2
R = 7: deadlock impossible
R = 8: deadlock impossible
formula n(k-1)+1 = 7

A related form: if the processes need different maximums k1, k2, ..., kn, then R_min = Σ(ki - 1) + 1. And the reverse question, "R units, each process needs k; the most processes without deadlock?": n(k - 1) + 1 ≤ R, so n ≤ (R - 1) / (k - 1).

The whole chain

Step Obvious attempt What broke Fix
1 Lend whenever cash exists stuck: cash 0 Safe state: lend only if everyone can still finish
2 One kind of resource Real systems have many types Banker's: Available, Max, Allocation, Need
3 Grant because units are free P0 asks (2,0,0): wait, would be UNSAFE Resource-request algorithm: pretend and check
4 Avoid everything in advance Needs max claims, slow Detection with Request + recovery
5 Pay for any of these on every request Deadlocks are rare The ostrich algorithm

Common mistakes

Mistake What you see Why Fix
Adding Need to Work when a process finishes Wrong safe sequence A finished process returns what it holds Work += Allocation[i]
Forgetting to compute Need first Comparing Max with Work Need = Max - Allocation Always write the Need table first
Comparing only one column "Fits" when it doesn't All m columns must fit Check every column
Granting because units are free P0 asks (2,0,0): wait, would be UNSAFE Free now ≠ safe later Pretend, then run the safety check
Saying "unsafe = deadlocked" Wrong theory answer Unsafe only means no guarantee Deadlocked ⊂ unsafe
Using Need in detection Reports deadlocks that aren't there Need is a maximum, not a current wait Use the Request matrix
Final Work ≠ Total An arithmetic slip Every unit must come back Use it as a self-check

Mini project: a Banker's simulator

Extend the REQUEST program into an interactive simulator: read the number of processes and resource types, the Total vector, and the Max and Allocation matrices from the input box (stdin), print the Need matrix and a safe sequence, then read requests one per line (i a b c) and print GRANTED / WAIT (not free) / WAIT (unsafe) / ERROR for each, updating the state after each grant. Bonus: add a release i a b c command, and print all safe sequences (try every order with recursion).

Practice

1. Find a second safe sequence for today's numerical.

Solution

⟨P1, P3, P0, P2, P4⟩: Work (2,2,2) → P1 → (4,2,3) → P3 → (4,3,5) → P0 needs (4,2,2) ≤ (4,3,5) yes → (5,4,5) → P2 needs (5,1,2) ≤ (5,4,5) yes → (7,5,6) → P4 needs (3,3,2) yes → (8,5,7). Also ⟨P3, P1, P4, P0, P2⟩ works: P3 needs (2,1,2) ≤ (2,2,2) → (2,3,4) → P1 (1,2,1) → (4,3,5) → P4 → (5,3,6) → P0 → (6,4,6) → P2 → (8,5,7).

2. In today's starting state, can P3 get (0,1,0)? Show the check.

Solution

Request (0,1,0) ≤ Need[P3] (2,1,2): yes. ≤ Available (2,2,2): yes. Pretend: Available = (2,1,2), Allocation[P3] = (0,2,2), Need[P3] = (2,0,2). Safety: P0 (4,2,2) no; P1 (1,2,1) no (B: 2 > 1); P2 no; P3 (2,0,2) ≤ (2,1,2) yes → Work (2,3,4); P4 (3,3,2) no (A). Pass 2: P0 no (A 4 > 2); P1 (1,2,1) yes → (4,3,5); P2 (5,1,2) no; P4 (3,3,2) yes → (5,3,6). Pass 3: P0 yes → (6,4,6); P2 yes → (8,5,7). Safe → granted.

3. 5 processes, each needs at most 4 units of one resource. Minimum units for no deadlock?

Solution

5 × (4 - 1) + 1 = 16. With 15, each could hold 3 and wait for a 4th forever.

4. Why does detection treat a process with Allocation = 0 as finished?

Solution

A process that holds nothing can't be blocking anyone, so it can't be part of a circle of waits. Even if it is waiting, it is waiting on others, not causing a deadlock; if the others finish, it will get what it needs.

5. Total = 10 units of one type. P0: Max 8, holds 4. P1: Max 4, holds 2. P2: Max 6, holds 2. Is it safe?

Solution

Available = 10 - 8 = 2. Needs: P0 4, P1 2, P2 4. P1 (2 ≤ 2) → 4 free. P0 (4 ≤ 4) → 8. P2 (4 ≤ 8) → 10. Safe, ⟨P1, P0, P2⟩.

6. 6 tape drives, each process needs at most 2. What is the maximum number of processes with no deadlock?

Solution

n(2 - 1) + 1 ≤ 6 → n ≤ 5. 5 processes. With 6, each could hold 1 and wait for a second.

Quick quiz

4 processes share one resource type, and each needs at most 3 units. What is the fewest number of units so that deadlock can never happen?

A. 8 B. 9 C. 12 D. 13

Answer

B, 9. n(k - 1) + 1 = 4 × 2 + 1 = 9. With 8, all four could hold 2 each and wait forever for a third.

Interview questions

  1. Prevention vs avoidance? Prevention makes a Coffman condition impossible by design; avoidance allows all four but checks every request and refuses those that lead to an unsafe state.
  2. What is a safe state? One with a safe sequence: an order in which every process can obtain its remaining need, finish and release.
  3. Is every unsafe state a deadlock? No. Unsafe means the system can't guarantee no deadlock; deadlocked states are a subset of unsafe states.
  4. Explain the Banker's algorithm. Available, Max, Allocation, Need = Max - Allocation; the safety algorithm finds a safe sequence; the resource-request algorithm pretends to grant and grants only if the result is safe.
  5. What's its time complexity? O(m × n²) for the safety algorithm.
  6. Why isn't the Banker's algorithm used in general-purpose OSes? Processes rarely know their maximum needs; the process set changes constantly; the check is expensive; it reduces utilisation.
  7. How does the detection algorithm differ from the safety algorithm? It uses the current Request matrix instead of Need, and treats processes with zero allocation as finished.
  8. How often should detection run? A trade-off: often (even on every blocking request) catches deadlocks early but costs CPU; rarely is cheap but deadlocked processes wait longer. Common triggers: a timer, or CPU utilisation dropping.
  9. How do you recover from a deadlock? Abort processes (all, or one at a time) or preempt resources with rollback to a checkpoint; choose the victim by cost and avoid always picking the same one.
  10. What is the ostrich algorithm and who uses it? Ignoring deadlocks because they're rare; UNIX and Windows do this for user programs.
  11. Minimum resources so n processes, each needing k, never deadlock? n(k - 1) + 1.

Glossary

Term Meaning in plain words Example
Deadlock Processes each waiting forever for another's resource stuck: cash 0
Resource type A kind of resource printers
Instance One unit of a resource type one printer
Maximum claim The most a process declares it may ever need Kiran: 10 lakh
State Snapshot of who holds what and what is free the tables
Safe state Some order lets every process finish ⟨Meera, Kiran, Arjun⟩ exists
Unsafe state No safe sequence exists; deadlock may follow cash 3, needs 4 and 6
Safe sequence An order in which all processes can finish ⟨P1, P3, P4, P0, P2⟩
Deadlock avoidance Grant a request only if the result is still safe the new lending rule
Banker's algorithm Dijkstra's avoidance algorithm for many resource types today's numerical
THE operating system Dijkstra's OS during whose design the Banker's algorithm was made
Vector A list of numbers Available = (2, 2, 2)
Matrix A table of numbers Allocation
Available Free units of each type (2, 2, 2)
Max Maximum demand of each process for each type P0: (5, 3, 2)
Allocation What each process holds now P0: (1, 1, 0)
Need Max - Allocation P0: (4, 2, 2)
Work The safety algorithm's running copy of Available grows as processes finish
Finish[i] Whether process i could finish in the check true / false
Safety algorithm Finds a safe sequence or says unsafe safe()
Resource-request algorithm Error / wait / pretend-and-check for a new request request()
enum A list of named integer constants in C enum { P = 5, R = 3 };
Resource utilisation How much of the time resources are in use lower under avoidance
Deadlock detection Grant freely, check later whether a deadlock exists detect()
Request matrix What each process is waiting for right now P1: (2, 0, 0)
Detection algorithm Safety algorithm with Request instead of Need deadlocked: P1 P2 P3
Wait-for graph Processes only, Pi → Pj if Pi waits for Pj single-instance detection
Recovery Getting out of a deadlock abort P3
Process termination Aborting processes to break a deadlock abort all, or one at a time
Resource preemption Taking resources away from a process give P3's C to P2
Rollback Returning a process to an earlier saved state restart from a checkpoint
Checkpoint A saved snapshot of a process's state saved every few minutes
Victim The process chosen to abort or lose resources P3
Victim selection Choosing the cheapest victim lowest priority, least work
Starvation A process never gets to finish while others do always the victim
Ostrich algorithm Ignore deadlocks because they're rare UNIX, Windows
R_min = n(k - 1) + 1 Fewest units so n processes needing k each can't deadlock 3 × 2 + 1 = 7

Summary

  • Avoidance keeps the system in a safe state: one with a safe sequence in which everyone can finish. Unsafe means no guarantee; deadlocked ⊂ unsafe. Live: lending freely gave stuck: cash 0; lending only when safe gave cash back to 12.
  • The Banker's algorithm (Dijkstra, for the THE OS) uses Available, Max, Allocation, Need = Max - Allocation. The safety algorithm adds Allocation to Work for each process that can finish (live: P1 P3 P4 P0 P2, SAFE). The resource-request algorithm: error if over Need, wait if over Available, otherwise pretend and grant only if still safe.
  • Detection uses Request instead of Need (live: deadlocked: P1 P2 P3). Recovery: abort all or one at a time, or preempt resources with rollback; pick the victim by cost and watch for starvation.
  • The ostrich algorithm ignores deadlocks: UNIX and Windows do this.
  • Minimum units: n(k - 1) + 1 (live brute force: R = 7 for 3 processes needing 3).

Next episode: Memory management 1: address binding and contiguous allocation: logical vs physical addresses, the MMU, loading and linking, first/best/worst fit, fragmentation and the buddy system.