SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 28
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 28 of 90

Deadlocks 1: conditions, resource allocation graphs and prevention

deadlockreusable vs consumable resourcesCoffman conditions (mutual exclusion, hold and wait, no preemption, circular wait)resource allocation graphsingle vs multiple instance resourcescycle vs deadlockwait-for graphdeadlock prevention by breaking each conditionresource orderinglivelockstarvation vs deadlockdeadlock in code

These are the notes for CS Fundamentals for Placements, episode 28. Last episode, five friends with five chopsticks got stuck forever. Today we find out exactly why that happens: what a deadlock is, the four Coffman conditions every deadlock needs, how to draw deadlocks as a resource allocation graph and a wait-for graph, how to prevent deadlocks by breaking a condition (most often with resource ordering), and two related problems: livelock and starvation. 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: gcc -O2 -Wno-unused-result main.c -o main -lm; on Linux, glibc has the pthread functions built in) and run on Linux x86-64 with 2 CPUs on 4 November 2026.

What is a deadlock?

The story: two cars in a one-lane gali

A narrow lane (gali) is exactly one car wide. A car enters from the left and drives up to the middle: it now holds the left half of the lane. At the same moment, a car enters from the right and holds the right half. To get through, each car needs the half the other one holds, and neither driver will reverse. Nobody moves, ever.

That is a deadlock: a set of processes in which each process is waiting for something that only another process in the same set can give, so none of them can ever continue.

  • A process here is simply a running program, or a thread (one flow of execution inside a program). Everything in this episode applies to both.
  • Note the words "in the same set". If one process is waiting for a slow disk, that is just waiting. It is a deadlock only when the waits loop back among themselves, so that no outside event can ever end them.

Resources: what processes wait for

A resource is anything a process needs and may have to wait for: a lock, a printer, a file, a block of memory, a CPU, a network connection. In the gali, each half of the lane is a resource.

Kind Meaning Examples
Reusable resource Used by one process at a time, then given back, and can be used again printer, lock (mutex), file, memory, CPU
Consumable resource Created by one process and used up (destroyed) by the one that takes it a message, a signal, an interrupt, data in a pipe

Deadlocks happen with both kinds. Two threads that each wait to receive a message from the other before sending their own are deadlocked on consumable resources.

Every use of a reusable resource follows three steps:

  1. Request it (wait if it is not free).
  2. Use it.
  3. Release it.

A deadlock is when the request step never finishes.

A real deadlock in C: Asha pays Ravi, Ravi pays Asha

A bank moves money from one account to another. To stop the balances changing in the middle of a transfer, it locks the sender's account, then the receiver's account, moves the money, and unlocks both. In C, each account gets a mutex (a lock only one thread can hold at a time, from episode 25): pthread_mutex_t, locked with pthread_mutex_lock and unlocked with pthread_mutex_unlock.

Now Asha sends Ravi ₹100 and, at the same moment, Ravi sends Asha ₹50.

First attempt: we forgot the header

#include <stdio.h>
#include <unistd.h>
pthread_mutex_t acc[2] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
int balance[2] = {1000, 1000}, done = 0;   // Asha = 0, Ravi = 1
void transfer(int from, int to, int amt) {
    pthread_mutex_lock(&acc[from]);      // lock the sender's account
    usleep(100000);                      // check the balance: 0.1 s
    pthread_mutex_lock(&acc[to]);        // lock the receiver's account
    balance[from] -= amt; balance[to] += amt; done++;
    pthread_mutex_unlock(&acc[to]); pthread_mutex_unlock(&acc[from]);
}
void *asha(void *a) { transfer(0, 1, 100); return NULL; }  // Asha pays Ravi
void *ravi(void *a) { transfer(1, 0, 50);  return NULL; }  // Ravi pays Asha
int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, asha, NULL); pthread_create(&t2, NULL, ravi, NULL);
    sleep(2);                            // wait 2 seconds, then check
    printf("after 2 s: %d of 2 transfers done\n", done);
}

Real compiler output (first lines):

main.c:3:1: error: unknown type name 'pthread_mutex_t'
    3 | pthread_mutex_t acc[2] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
      | ^~~~~~~~~~~~~~~
main.c:3:27: error: 'PTHREAD_MUTEX_INITIALIZER' undeclared here (not in a function)
main.c: In function 'transfer':
main.c:6:5: warning: implicit declaration of function 'pthread_mutex_lock' [-Wimplicit-function-declaration]

Why: the mutex type, PTHREAD_MUTEX_INITIALIZER (a ready-made "unlocked" starting value) and every pthread_ function are declared in the header <pthread.h>. Without it the compiler has never heard of them.

The program with the header: a live deadlock

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t acc[2] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
int balance[2] = {1000, 1000}, done = 0;   // Asha = 0, Ravi = 1
void transfer(int from, int to, int amt) {
    pthread_mutex_lock(&acc[from]);      // lock the sender's account
    usleep(100000);                      // check the balance: 0.1 s
    pthread_mutex_lock(&acc[to]);        // lock the receiver's account
    balance[from] -= amt; balance[to] += amt; done++;
    pthread_mutex_unlock(&acc[to]); pthread_mutex_unlock(&acc[from]);
}
void *asha(void *a) { transfer(0, 1, 100); return NULL; }  // Asha pays Ravi
void *ravi(void *a) { transfer(1, 0, 50);  return NULL; }  // Ravi pays Asha
int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, asha, NULL); pthread_create(&t2, NULL, ravi, NULL);
    sleep(2);                            // wait 2 seconds, then check
    printf("after 2 s: %d of 2 transfers done\n", done);
}

Output (the same in 3 of 3 runs):

after 2 s: 0 of 2 transfers done

What happened, step by step:

Time Asha's thread Ravi's thread
0.0 s locks account 0 (Asha) locks account 1 (Ravi)
0.0-0.1 s "checks the balance" (usleep) "checks the balance"
0.1 s wants account 1: held by Ravi's thread → sleeps wants account 0: held by Asha's thread → sleeps
forever waiting waiting

usleep(100000) pauses the thread for 100,000 microseconds = 0.1 s. It only makes the bad timing certain; without it the deadlock would happen sometimes, which is worse, because it would pass your tests and then freeze in production.

When main returns after 2 seconds, the whole process ends, so the program still prints and exits. In a real server, those two threads (and every customer waiting behind them) would hang forever.

Why it froze: the four Coffman conditions

Look closely and four things were true at the same time:

# Condition Plain meaning In the bank code
1 Mutual exclusion A resource can be held by only one process at a time A mutex has one owner
2 Hold and wait A process holds at least one resource while waiting for another Each thread holds one lock and waits for the second
3 No preemption A resource can't be taken away by force; only its holder releases it Nobody can snatch a mutex from a thread
4 Circular wait There is a circle of processes, each waiting for a resource held by the next Asha's thread → Ravi's lock → Ravi's thread → Asha's lock → Asha's thread

Preemption means taking a resource away from a process that holds it, without its agreement (like the scheduler taking the CPU away in preemptive scheduling, episode 21).

These are the Coffman conditions, named after their first description in 1971 by Edward G. Coffman Jr., Michael J. Elphick and Arie Shoshani ("System Deadlocks", ACM Computing Surveys, vol. 3, no. 2, pp. 67-78).

They are necessary conditions: a deadlock can happen only if all four hold at once. So if you make even one of them impossible, deadlock is impossible. That one sentence is the basis of deadlock prevention.

Exam tip: the four conditions are necessary, and (for single-instance resources) together they are also sufficient. Circular wait already implies hold and wait, so the four are not fully independent, but you should still list all four.

Drawing deadlocks: the resource allocation graph (RAG)

To reason about deadlocks, the OS (and you, in an exam) draws a picture. A graph is a set of dots (nodes or vertices) joined by arrows (edges).

A resource allocation graph (RAG) has:

Symbol Meaning Library example
Circle Pi A process a reader
Box Rj A resource type a book title
Dot inside a box One instance (one unit) of that resource one copy of the book
Arrow Pi → Rj Request edge: Pi is waiting for one instance of Rj a request slip
Arrow from a dot in Rj → Pi Assignment edge: that instance is held by Pi "issued to Asha" in the register
  • A single-instance resource has exactly one dot (one printer, one lock).
  • A multiple-instance resource has several identical units (3 printers in a pool, 4 GB of memory in pages).

When a request is granted, the request edge flips into an assignment edge. When the process releases the resource, the assignment edge is deleted.

Our bank deadlock as a RAG

T_Asha ──request──▶ [Ravi's lock ●] ──assigned──▶ T_Ravi
   ▲                                                  │
   └──assigned── [Asha's lock ●] ◀──request───────────┘

Following the arrows brings you back to where you started. That is a cycle.

Cycle vs deadlock: the three rules

  1. No cycle → no deadlock. Always.
  2. Cycle, and every resource in it has a single instance → deadlock. Guaranteed.
  3. Cycle, with multiple-instance resources → deadlock is possible, but not certain. You must check whether some process can still finish.

A cycle that is not a deadlock (exam favourite)

  • R1 has 2 instances: one is held by P1, the other by P3.
  • R2 has 1 instance, held by P2.
  • P1 requests R2. P2 requests R1.

Arrows: P1 → R2 → P2 → R1 → P1. A cycle!

But P3 is not waiting for anything. It finishes and releases its copy of R1. Now P2's request for R1 can be granted, P2 finishes and releases R2, and then P1 gets R2 and finishes. No deadlock, even though there was a cycle.

The wait-for graph

When every resource has a single instance, there is a simpler picture. Delete the resource boxes and connect the processes directly:

Pi → Rq → Pj    becomes    Pi → Pj      ("Pi waits for Pj")

This is the wait-for graph: it shows only who is waiting for whom. For single-instance resources, a cycle in the wait-for graph means deadlock, and finding a cycle is a classic graph algorithm.

A deadlock detector in C

The program stores the wait-for graph as an adjacency matrix: waits[i][j] = 1 means process i waits for process j. It finds cycles with depth-first search (DFS): from a process, keep following arrows as deep as you can, and back up when there is nowhere new to go. state[u] remembers whether a process is not yet seen (0), on the current path (1), or fully explored (2). Reaching a process that is on the current path means we have come back around: a cycle.

#include <stdio.h>
#define N 4
int waits[N][N];   // waits[i][j] = 1: process i waits for process j
int state[N], path[N], len = 0;   // state 1 = on the current path
int dfs(int u) {
    state[u] = 1; path[len++] = u;
    for (int v = 0; v < N; v++) if (waits[u][v]) {
        if (state[v] == 1) {       // back to a process on our path: a cycle
            int k = 0; while (path[k] != v) k++;
            printf("cycle:");
            for (; k < len; k++) printf(" P%d ->", path[k]);
            printf(" P%d\n", v); return 1;
        }
        if (state[v] == 0 && dfs(v)) return 1;
    }
    state[u] = 2; len--; return 0;
}
int main(void) {
    waits[0][1] = 1; waits[1][2] = 1;   // P0 waits for P1, P1 for P2
    waits[2][0] = 1; waits[3][1] = 1;   // P2 waits for P0, P3 for P1
    for (int i = 0; i < N; i++)
        if (state[i] == 0 && dfs(i)) { printf("deadlock!\n"); return 0; }
    printf("no cycle: no deadlock\n");
}

Output:

cycle: P0 -> P1 -> P2 -> P0
deadlock!

P3 is not in the cycle, but it waits for P1, which will never finish, so P3 is stuck too. (A process waiting on a deadlocked set is blocked forever, even though it is not part of the cycle.)

Now P2 stops waiting for P0 (the waits[2][0] = 1 assignment is removed):

#include <stdio.h>
#define N 4
int waits[N][N];   // waits[i][j] = 1: process i waits for process j
int state[N], path[N], len = 0;   // state 1 = on the current path
int dfs(int u) {
    state[u] = 1; path[len++] = u;
    for (int v = 0; v < N; v++) if (waits[u][v]) {
        if (state[v] == 1) {       // back to a process on our path: a cycle
            int k = 0; while (path[k] != v) k++;
            printf("cycle:");
            for (; k < len; k++) printf(" P%d ->", path[k]);
            printf(" P%d\n", v); return 1;
        }
        if (state[v] == 0 && dfs(v)) return 1;
    }
    state[u] = 2; len--; return 0;
}
int main(void) {
    waits[0][1] = 1; waits[1][2] = 1;   // P0 waits for P1, P1 for P2
    waits[3][1] = 1;   // P2 no longer waits for P0; P3 waits for P1
    for (int i = 0; i < N; i++)
        if (state[i] == 0 && dfs(i)) { printf("deadlock!\n"); return 0; }
    printf("no cycle: no deadlock\n");
}

Output:

no cycle: no deadlock

DFS visits each process once and looks at each possible arrow, so with an adjacency matrix the check costs O(n²) for n processes. An OS can run exactly this check periodically; that is deadlock detection, the topic of the next episode.

Deadlock prevention: make one condition impossible

Deadlock prevention means designing the system so that at least one of the four Coffman conditions can never be true. Then deadlock can never happen.

Condition to break How Cost / problem
Mutual exclusion Make the resource shareable: read-only files can be read by everyone at once; spooling a printer (jobs are written to a queue on disk, and only one printer program, the spooler, touches the printer) Many resources (locks, a write to a record) are exclusive by nature, so this rarely works
Hold and wait A process requests all its resources at once, before it starts; or it may request only when it holds nothing Low resource utilisation (resources sit idle while held unused); a process needing many popular resources may starve
No preemption If a process holding resources can't get the next one, it releases everything it holds and retries later (or the OS takes resources from a waiting process) Only works for resources whose state can be saved and restored (CPU registers, memory); not for a printer halfway through a page or a half-written file
Circular wait Give every resource type a number, and require every process to request resources in increasing order of number (resource ordering, or a lock hierarchy) Programmers must follow the order everywhere; the most practical method, widely used in real code (including OS kernels)

Why resource ordering can't deadlock

Suppose there were a circle P0 → P1 → ... → Pk → P0, where each Pi holds resource Ri and waits for R(i+1). Because everyone requests in increasing order, number(R0) < number(R1) < ... < number(Rk) < number(R0). That says number(R0) < number(R0), which is impossible. So the circle can't exist.

Resource ordering in the bank

Always lock the lower account number first, whatever the direction of the payment:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t acc[2] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
int balance[2] = {1000, 1000}, done = 0;   // Asha = 0, Ravi = 1
void transfer(int from, int to, int amt) {
    int first = from < to ? from : to;   // lower account number
    int second = from < to ? to : from;  // higher account number
    pthread_mutex_lock(&acc[first]);     // ALWAYS lock the lower one first
    usleep(100000);                      // check the balance: 0.1 s
    pthread_mutex_lock(&acc[second]);
    balance[from] -= amt; balance[to] += amt; done++;
    pthread_mutex_unlock(&acc[second]); pthread_mutex_unlock(&acc[first]);
}
void *asha(void *a) { transfer(0, 1, 100); return NULL; }  // Asha pays Ravi
void *ravi(void *a) { transfer(1, 0, 50);  return NULL; }  // Ravi pays Asha
int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, asha, NULL); pthread_create(&t2, NULL, ravi, NULL);
    sleep(2);                            // wait 2 seconds, then check
    printf("after 2 s: %d of 2 transfers done\n", done);
    printf("Asha %d, Ravi %d\n", balance[0], balance[1]);
}

Output (3 of 3 runs):

after 2 s: 2 of 2 transfers done
Asha 950, Ravi 1050

Ravi's thread now waits for account 0 while holding nothing, so there is no circle. The balances are right: Asha 1000 - 100 + 50 = 950, Ravi 1000 + 100 - 50 = 1050.

Back off and retry: breaking hold-and-wait and no-preemption

pthread_mutex_trylock(&m) tries to lock m but never waits: it returns 0 if it got the lock, and an error code (EBUSY) immediately if the lock is busy. If the second lock is busy, the thread lets go of the first (so it no longer "holds and waits") and tries again later:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t acc[2] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER};
int balance[2] = {1000, 1000}, done = 0, retries = 0;
void transfer(int from, int to, int amt) {
    while (1) {
        pthread_mutex_lock(&acc[from]);           // lock the sender's account
        usleep(100000);                           // check the balance: 0.1 s
        if (pthread_mutex_trylock(&acc[to]) == 0) break;  // got both!
        pthread_mutex_unlock(&acc[from]);         // busy: let go of the first
        retries++; usleep(from == 0 ? 50000 : 170000);   // wait a different time
    }
    balance[from] -= amt; balance[to] += amt; done++;
    pthread_mutex_unlock(&acc[to]); pthread_mutex_unlock(&acc[from]);
}
void *asha(void *a) { transfer(0, 1, 100); return NULL; }
void *ravi(void *a) { transfer(1, 0, 50);  return NULL; }
int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, asha, NULL); pthread_create(&t2, NULL, ravi, NULL);
    sleep(2);
    printf("after 2 s: %d of 2 transfers done, %d retries\n", done, retries);
}

Output (5 of 5 runs):

after 2 s: 2 of 2 transfers done, 1 retries

Notice the two sides wait different times before retrying (50 ms vs 170 ms). The next section shows why that matters.

Livelock

The story: two polite people in a corridor

Two very polite people meet face to face in a narrow corridor. Both step aside to let the other pass, at the same moment, into the same lane. So both step back. Again, and again. Nobody is waiting: both are busy moving. But nobody gets anywhere.

That is a livelock: processes keep changing state in response to each other, so they are running, but none of them makes progress. The term was coined by Edward A. Ashcroft in a 1975 paper about airline booking systems.

The corridor, simulated

This program is a deterministic simulation (one thread, two variables), so the output is the same on every run:

#include <stdio.h>
// Two polite people meet in a narrow corridor with 2 lanes.
// Each step, if the other is in my lane, I step to the other lane.
int main(void) {
    int asha = 0, ravi = 0;              // both start in lane 0
    for (int step = 1; step <= 1000; step++) {
        int a_blocked = (asha == ravi), r_blocked = (ravi == asha);
        if (a_blocked) asha = 1 - asha;  // Asha steps aside
        if (r_blocked) ravi = 1 - ravi;  // Ravi steps aside, same moment
        if (step <= 4) printf("step %d: Asha lane %d, Ravi lane %d\n", step, asha, ravi);
        if (asha != ravi) { printf("passed at step %d\n", step); return 0; }
    }
    printf("after 1000 steps: still face to face\n");
}

Output:

step 1: Asha lane 1, Ravi lane 1
step 2: Asha lane 0, Ravi lane 0
step 3: Asha lane 1, Ravi lane 1
step 4: Asha lane 0, Ravi lane 0
after 1000 steps: still face to face

The retry code from the bank example could do exactly this if both threads waited the same time and stayed perfectly in step: lock, fail, release, wait, lock, fail, release, forever.

The fix: break the symmetry (random backoff)

Each person tosses a coin before moving: rand() % 2 is 0 or 1 at random. (rand() comes from <stdlib.h>; without srand, it starts from the same seed every run, so this output is also the same every run.)

#include <stdio.h>
#include <stdlib.h>
// Two polite people meet in a narrow corridor with 2 lanes.
// Each step, if the other is in my lane, I step to the other lane.
int main(void) {
    int asha = 0, ravi = 0;              // both start in lane 0
    for (int step = 1; step <= 1000; step++) {
        int a_blocked = (asha == ravi), r_blocked = (ravi == asha);
        if (a_blocked && rand() % 2) asha = 1 - asha;  // coin toss: move?
        if (r_blocked && rand() % 2) ravi = 1 - ravi;  // coin toss: move?
        if (step <= 4) printf("step %d: Asha lane %d, Ravi lane %d\n", step, asha, ravi);
        if (asha != ravi) { printf("passed at step %d\n", step); return 0; }
    }
    printf("after 1000 steps: still face to face\n");
}

Output:

step 1: Asha lane 1, Ravi lane 0
passed at step 1

In real systems this is random backoff: after a failed attempt, wait a random time before retrying, and often double the maximum wait after each failure (exponential backoff). Ethernet uses it to schedule retransmissions after a collision (two network cards transmitting at once), and so do well-written retry loops.

Deadlock vs livelock vs starvation

Deadlock Livelock Starvation
What the stuck processes are doing Blocked, waiting; nothing changes Running, changing state One process waits; others run
Does the system make progress? Not the processes in the set No Yes, but not for the starving process
Can it end by itself? Never Possibly, by luck Possibly, if the competition stops
Example 0 of 2 transfers done the corridor dance the writer waiting through 30 reads (episode 27); a low-priority process (episode 22)
Fix Prevention, avoidance, detection + recovery Randomness, asymmetry, one decider Fair queues, aging (raise priority while waiting)

Every process stuck in a deadlock is starving, but a starving process is not necessarily deadlocked.

The whole chain

Step Obvious attempt What broke Fix
1 Lock sender, then receiver Opposite transfers: 0 of 2 done Understand the four conditions
2 "A cycle in the RAG = deadlock" False with multiple instances Three rules; wait-for graph for single instances
3 Look for deadlocks by eye Hard in big systems DFS cycle finder on the wait-for graph
4 Lock in whatever order the code happens to use Circular wait Resource ordering: 2 of 2 done
5 Retry with the same fixed wait Livelock: still face to face Random backoff: passed at step 1

Common mistakes

Mistake What you see Why Fix
Using pthread_mutex_t without the header error: unknown type name 'pthread_mutex_t' (+ implicit declaration of function 'pthread_mutex_lock') pthreads are declared in <pthread.h> #include <pthread.h>
Taking two locks in different orders in different functions after 2 s: 0 of 2 transfers done (or a rare, random hang) Circular wait One global lock order
Locking the same non-recursive mutex twice in one thread The thread hangs on itself A default mutex is not re-entrant Restructure, or use a recursive mutex deliberately
Saying "a cycle in a RAG always means deadlock" Wrong exam answer Another instance may be freed Cycle is sufficient only for single-instance resources
Retrying with the same fixed delay on both sides after 1000 steps: still face to face Both stay in step: livelock Random or different backoff
Calling starvation a deadlock Wrong theory answer In starvation, the system still progresses Use the comparison table
Forgetting to unlock on an early return Every other thread hangs on that lock The lock is never released Unlock on every path

Mini project: a lock-order checker

Write a program with 4 accounts and 6 threads that make random transfers (rand() % 4 for sender and receiver, skipping from == to), each doing 10,000 transfers.

  1. First use "lock sender, then receiver". Run it a few times; print the number of transfers finished after 3 seconds and see it get stuck.
  2. Then switch to "lock the lower number first". Check that every run finishes and that the total money (sum of the 4 balances) never changes.
  3. Bonus: keep a global wait-for matrix (waits[i][j]), updated (under its own mutex) whenever a thread is about to block on a lock held by another thread, and run the DFS from this episode in a monitor thread every 100 ms. Print the cycle when it finds one.

Practice

1. Draw the RAG for the 5 dining friends from episode 27, at the moment they deadlock.

Solution

Five process circles F0..F4 and five single-instance resource boxes C0..C4 (the chopsticks). Assignment edges: C0 → F0, C1 → F1, C2 → F2, C3 → F3, C4 → F4 (each holds the left one). Request edges: F0 → C1, F1 → C2, F2 → C3, F3 → C4, F4 → C0 (each wants the right one). Following the arrows: F0 → C1 → F1 → C2 → F2 → C3 → F3 → C4 → F4 → C0 → F0, a cycle. All resources are single-instance, so this is a deadlock.

2. With 3 processes and a resource R1 that has 2 instances, build a RAG that has a cycle but no deadlock.

Solution

R1 (2 instances): one held by P1, one held by P3. R2 (1 instance): held by P2. P1 requests R2, P2 requests R1. Cycle: P1 → R2 → P2 → R1 → P1. P3 requests nothing, finishes, releases its R1 instance, P2 gets it and finishes, releasing R2 for P1. Everyone completes.

3. "Request all resources at once, before starting." Which condition does it break, and what does it cost?

Solution

Hold and wait: a process never holds some resources while waiting for others. Costs: resources are held long before (or long after) they are needed, so utilisation drops; a process must know everything it will need in advance; and a process that needs several popular resources may wait a very long time (starvation).

4. Change the bank TRYLOCK program so it can livelock, then fix it.

Solution

Make both sides wait the same time and make the timing symmetric, e.g. replace the delay with usleep(50000) for both, and also have each thread wait the same time before its first lock. The two threads can then lock, fail, release and retry in step. (On a real machine the scheduler's small timing differences often break the symmetry anyway, which is why livelocks are rare and hard to reproduce; the corridor simulation shows the pure effect.) Fix: usleep(rand() % 100000), a random backoff, or a fixed lock order.

5. In the wait-for graph P0 → P1, P1 → P2, P2 → P3, P3 → P1, which processes are deadlocked?

Solution

The cycle is P1 → P2 → P3 → P1, so P1, P2 and P3 are deadlocked. P0 is not in the cycle, but it waits for P1, which will never finish, so P0 is blocked forever too.

6. Is this code deadlock-free? Thread A: lock(m1); lock(m2); ... unlock both. Thread B: lock(m2); unlock(m2); lock(m1); lock(m2); ...

Solution

Yes. Thread B never holds m2 while waiting for m1: it releases m2 before asking for m1. When it does hold two locks, it takes them in the same order as A (m1, then m2). There is no hold-and-wait in the wrong order, so no circular wait.

Quick quiz

// every thread must lock in this order:
// account 0 → account 1 → account 2 → ...
lock(acc[min(from, to)]);
lock(acc[max(from, to)]);

Which Coffman condition does this break? A. Mutual exclusion B. Hold and wait C. No preemption D. Circular wait

Answer

D, circular wait. Threads still hold one lock while waiting for another (hold and wait remains), but because everyone goes up in the same order, a circle of waits can never close.

Interview questions

  1. What is a deadlock? A set of processes, each waiting for an event (usually the release of a resource) that only another process in the set can cause, so none can continue.
  2. What are the four necessary conditions for deadlock? Mutual exclusion, hold and wait, no preemption, circular wait (the Coffman conditions, 1971).
  3. Does a cycle in a resource allocation graph mean deadlock? Yes if every resource involved has a single instance; with multiple instances, it means deadlock is possible but not certain. No cycle always means no deadlock.
  4. What is a wait-for graph and when can you use it? The RAG with resource nodes removed, edges Pi → Pj meaning "Pi waits for Pj". It detects deadlock (as a cycle) when every resource has a single instance.
  5. How would you prevent deadlock in code that locks two bank accounts? Lock in a fixed global order (e.g. by account number), or use trylock with back-off, or one coarse lock for both.
  6. Which prevention method is most practical, and why? Breaking circular wait with resource ordering: it costs almost nothing at runtime, just discipline.
  7. What is the difference between deadlock and livelock? In deadlock, processes are blocked and nothing changes; in livelock, they keep running and changing state but make no progress.
  8. Deadlock vs starvation? Starvation: the system progresses but one process never gets its turn; deadlock: a set of processes can never progress. Deadlock implies starvation of those processes; not the reverse.
  9. How do you fix a livelock? Break the symmetry: random (exponential) backoff, priorities, or let only one party decide.
  10. What is the difference between reusable and consumable resources? Reusable resources are returned after use (locks, printers); consumable ones are destroyed when taken (messages, signals).
  11. Can a single thread deadlock? Yes, by locking a non-recursive mutex it already holds; it then waits on itself.

Glossary

Term Meaning in plain words Example
Process A running program the bank server
Thread One flow of execution inside a program Asha's transfer thread
Deadlock A set of processes each waiting forever for something another in the set holds 0 of 2 transfers done
Resource Anything a process needs and may wait for a lock, a printer
Reusable resource Used, then given back, usable again a mutex
Consumable resource Used up when taken a message
Request / use / release The three steps of using a resource lock, transfer, unlock
Mutex A lock that only one thread can hold at a time pthread_mutex_t
pthread_mutex_lock Take a mutex, waiting if it is busy lock an account
pthread_mutex_unlock Release a mutex unlock an account
pthread_mutex_trylock Try to take a mutex; return at once if it is busy the back-off version
PTHREAD_MUTEX_INITIALIZER A ready-made value for an unlocked mutex acc[2] = {...}
<pthread.h> The C header for threads and mutexes #include <pthread.h>
usleep Pause a thread for some microseconds usleep(100000) = 0.1 s
Coffman conditions The four necessary conditions for deadlock (1971) ME, H&W, NP, CW
Mutual exclusion Only one holder at a time one owner per mutex
Hold and wait Holding one resource while waiting for another holds Asha's lock, wants Ravi's
Preemption Taking a resource away by force the scheduler taking the CPU
No preemption Resources can't be taken away; only the holder releases a mutex
Circular wait A closed circle of processes, each waiting for the next Asha → Ravi → Asha
Necessary condition Must be true for something to happen; if false, it can't all four for deadlock
Graph Dots (nodes) joined by arrows (edges) the RAG
Resource allocation graph (RAG) Processes, resources, request and assignment edges library register
Instance One unit of a resource type one copy of a book
Single-instance resource A resource type with exactly one unit one printer
Multiple-instance resource A resource type with several identical units 3 printers
Request edge Arrow P → R: P waits for R request slip
Assignment edge Arrow R → P: R is held by P "issued to"
Cycle A path of arrows that returns to its start P0 → P1 → P2 → P0
Wait-for graph Processes only; Pi → Pj means Pi waits for Pj waits[i][j]
Adjacency matrix A table where cell [i][j] says whether an edge i → j exists waits[N][N]
Depth-first search (DFS) Follow arrows as deep as possible, then back up dfs(u)
Deadlock prevention Design so one Coffman condition can never hold lock ordering
Spooling Queue jobs on disk so one program uses the device print spooler
Resource utilisation How much of the time resources are actually in use drops with "request all at once"
Resource ordering (lock hierarchy) Number resources; request in increasing order lower account first
Deadlock detection Let deadlocks happen, find them (e.g. a cycle) the DFS program
Livelock Processes keep reacting to each other, no progress the corridor
Random backoff Wait a random time before retrying coin toss
Exponential backoff Double the maximum random wait after each failure Ethernet after a collision
Starvation One process waits indefinitely while others progress the writer in episode 27
Aging Raising a waiting process's priority over time fixes starvation

Summary

  • A deadlock is a set of processes each waiting forever for a resource held by another member of the set. Live: Asha's and Ravi's opposite transfers gave 0 of 2 transfers done.
  • It needs all four Coffman conditions: mutual exclusion, hold and wait, no preemption, circular wait. Break any one, and deadlock is impossible.
  • A resource allocation graph shows request edges (P → R) and assignment edges (R → P). No cycle → no deadlock; cycle with single-instance resources → deadlock; cycle with multiple instances → maybe.
  • The wait-for graph keeps only processes; a DFS finds its cycles (live: cycle: P0 -> P1 -> P2 -> P0).
  • Prevention breaks a condition; the practical one is resource ordering (live: 2 of 2 transfers done). Back-off with trylock breaks hold-and-wait.
  • Livelock: busy but no progress (live: still face to face), fixed by random backoff. Starvation: one process never gets its turn, fixed by aging or fair queues.

Next episode: Deadlocks 2: avoidance, the Banker's algorithm, detection and recovery: safe states, safe sequences, the Banker's algorithm step by step with numericals, the detection algorithm, recovery, and the ostrich algorithm.