Deadlocks

A deadlock is a situation in which a set of processes or threads are all blocked forever, because each one is waiting for a resource that another member of the set holds. Nothing in the set can ever proceed: no amount of waiting will fix it. Deadlocks hang database transactions, freeze multithreaded servers and stall operating-system kernels, which is why the topic appears in nearly every OS interview and exam.

Interviewers commonly probe: the four necessary conditions (the Coffman conditions), reading a resource-allocation graph and deciding whether a cycle means deadlock, the four strategies for handling deadlock (prevention, avoidance, detection and recovery, or ignoring it), a full Banker's algorithm calculation, the difference between deadlock, livelock and starvation, and how deadlocks show up in databases and in multithreaded code. This lesson covers each one with worked numbers; every Banker's and detection calculation below was checked with a short Python program.

A first example

Two threads each need two locks, but take them in opposite orders:

Thread 1                      Thread 2
lock(A)                       lock(B)
   ...                           ...
lock(B)   <- waits for T2     lock(A)   <- waits for T1

If thread 1 takes A and thread 2 takes B before either takes its second lock, each waits for the other forever. This is the same shape as two cars meeting on a narrow bridge from opposite sides, each refusing to reverse, or the dining philosophers all holding their left fork.

In OS terms, a resource is anything a process must acquire before using and release afterwards: a mutex, a semaphore, a file lock, a printer, memory, a database row lock. A resource type may have several identical instances (three printers of the same model), and a request for that type can be satisfied by any free instance. Using a resource always follows the pattern request, use, release.

The four necessary conditions (Coffman conditions)

In 1971, Coffman, Elphick and Shoshani described four conditions that must all hold at the same time for a deadlock to occur:

1. Mutual exclusion: at least one resource is non-shareable; only one process can use it at a time. (A read-only file can be shared; a printer or a mutex cannot.)
2. Hold and wait: a process holds at least one resource while waiting to acquire additional resources held by others.
3. No preemption: resources cannot be forcibly taken away; a process releases a resource only voluntarily, after it is done with it.
4. Circular wait: there is a set of waiting processes P0, P1, ..., Pn such that P0 waits for a resource held by P1, P1 waits for P2, and so on, and Pn waits for a resource held by P0.

Apply them to the two-lock example: locks are exclusive (1); each thread holds one lock while waiting for the other (2); a lock cannot be taken from its holder (3); T1 waits for T2 and T2 waits for T1 (4). All four hold, so deadlock is possible.

These conditions are necessary, not sufficient in general: if any one is missing, deadlock is impossible, which is the basis of prevention. Circular wait in fact implies hold and wait, so the conditions are not fully independent, but they are always taught and asked as four.

Resource-allocation graphs

A resource-allocation graph (RAG) shows who holds what and who waits for what.

• Process nodes, drawn as circles: (P1).
• Resource nodes, drawn as boxes, with one dot per instance: [R1 ..] for two instances.
• Request edge P -> R: process P is waiting for an instance of R.
• Assignment edge R -> P: an instance of R is allocated to P.

Single-instance example: a cycle means deadlock

          request              assigned
   (P1) ---------> [R1 .] ---------> (P2)
    ^                                  |
    |  assigned                        | request
    |                                  v
   [R2 .] <----------------------------+

   P1 holds R2 and wants R1; P2 holds R1 and wants R2.
   Cycle: P1 -> R1 -> P2 -> R2 -> P1   => DEADLOCK

When every resource type has exactly one instance, a cycle in the graph is both necessary and sufficient for deadlock. Every process on the cycle is deadlocked.

Multi-instance example: a cycle does not always mean deadlock

Now let R1 and R2 each have two instances.

               +-------------+
     request   |  R1  .  .   |  assigned
   (P1) -----> |             | ---------> (P2)    P2 is not waiting
    ^          +-------------+ ---------> (P3)
    |                                       |
    | assigned                              | request
    |          +-------------+              |
    +--------- |  R2  .  .   | <------------+
               |             | ---------> (P4)    P4 is not waiting
               +-------------+  assigned

• R1's two instances are held by P2 and P3. R2's are held by P1 and P4.
• P1 wants R1. P3 wants R2.
• There is a cycle: P1 -> R1 -> P3 -> R2 -> P1.

But this is not a deadlock. P2 and P4 are not waiting for anything, so they will finish and release their instances. When P2 releases its R1 instance, P1 can take it, finish, and release R2 for P3. Running the detection algorithm on this state (shown later) finds the completion order P2, P1, P3, P4.

The rules:

So with multiple instances, a cycle is necessary but not sufficient, and you need an algorithm like the detection algorithm below to decide.

The wait-for graph

When all resources are single-instance, you can simplify the RAG into a wait-for graph by removing resource nodes: draw Pi -> Pj if Pi is waiting for a resource that Pj holds. A deadlock exists exactly when this graph has a cycle, which a depth-first search finds in time proportional to the number of nodes plus edges. Databases use wait-for graphs to detect deadlocks between transactions.

Four ways to handle deadlock

The last row surprises people. General-purpose operating systems do not run Banker's algorithm on every lock request: it would be too expensive and they do not know processes' maximum needs. They leave application-level deadlock to programmers and tools, while using prevention (careful lock ordering) inside the kernel itself.

Deadlock prevention: break one condition

Break mutual exclusion

Make resources shareable where possible. Read-only files and read-only data can be shared by any number of processes. Spooling turns an exclusive device into a shareable one: processes write print jobs to a disk queue, and only the print spooler daemon ever touches the printer. Lock-free data structures avoid locks entirely.

Limit: many resources are inherently exclusive (a mutex exists precisely to be exclusive), so this rarely solves the general problem.

Break hold and wait

Ensure a process never holds one resource while waiting for another:

• Request everything up front: a process requests all the resources it will need at once, before starting, and gets either all or none.
• Release before requesting: a process may request new resources only when it holds none, so it must release what it has first.

Limits: low resource utilization, since resources sit allocated long before they are used; starvation of processes that need several popular resources, which may never all be free together; and processes often do not know all their needs in advance.

In code, a common form is "try-lock all, or back off": acquire the first lock, try the second with trylock, and if that fails, release the first and retry after a random delay.

Break no preemption

Allow resources to be taken away:

• If a process holding resources requests one that cannot be granted immediately, it releases all the resources it holds, and restarts later when it can get everything.
• Or, if the requested resource is held by another process that is itself waiting, take it from that process.

This works for resources whose state can be saved and restored, such as CPU registers (context switching is preemption) and memory pages (which can be swapped out). It does not work for mutexes protecting half-updated data, or for printers halfway through a page. Databases use a version of it: aborting a transaction rolls back its changes and releases its locks.

Break circular wait

Impose a total ordering on all resource types, and require every process to request resources in increasing order. If a process holds resource number 5, it may request 7 but not 3; to get 3 it must first release 5.

Why it works: suppose a cycle P0 -> P1 -> ... -> Pn -> P0 existed. Each process waits for a resource whose number is greater than the one it holds, so going around the cycle the numbers strictly increase, and coming back to P0 would require a number greater than itself. Contradiction.

This is the most practical prevention technique and is widely used: the Linux kernel documents lock nesting orders and has a runtime validator (lockdep) that warns when code takes locks in an order that could deadlock, and application code orders locks by ID or address. The dining philosophers resource-ordering solution is this technique.

Deadlock avoidance: safe states

Prevention restricts how processes request resources. Avoidance lets processes request freely, but before granting each request, the OS checks whether granting it could lead to deadlock in the future. To do that, it needs extra information: each process declares in advance the maximum number of instances of each resource type it may ever need.

Safe and unsafe states

A state is safe if there is at least one order in which all processes can run to completion, even if each immediately requests its declared maximum. Such an order is called a safe sequence: for each process in the sequence, its remaining needs can be satisfied by the currently available resources plus the resources held by all processes earlier in the sequence (which will have finished and released them).

• A safe state guarantees no deadlock.
• An unsafe state does not mean a deadlock has happened. It means the OS can no longer guarantee avoiding one: if processes make their worst-case requests, deadlock may follow.
• A deadlocked state is one kind of unsafe state.

+--------------------------------------------------+
|                 all possible states              |
|   +-----------------+    +---------------------+ |
|   |      SAFE       |    |       UNSAFE        | |
|   |  (no deadlock   |    |   +-------------+   | |
|   |   possible)     |    |   |  DEADLOCK   |   | |
|   |                 |    |   +-------------+   | |
|   +-----------------+    +---------------------+ |
+--------------------------------------------------+

The avoidance rule is simple: grant a request only if the resulting state is safe; otherwise make the process wait, even if the resources are free right now.

Single-instance resources: the claim-edge algorithm

If every resource has one instance, avoidance can use the RAG with an extra kind of edge: a claim edge P - - > R (dashed) meaning "P may request R in the future". When P actually requests R, the claim edge becomes a request edge; the request is granted only if converting it to an assignment edge does not create a cycle (counting claim edges). For multiple instances, you need Banker's algorithm.

Banker's algorithm

Banker's algorithm, designed by Edsger Dijkstra, gets its name from a bank that must never lend out its cash in a way that leaves it unable to satisfy all its customers' credit limits. It handles multiple instances of multiple resource types.

Data structures

For n processes and m resource types:

• Available (length m): free instances of each type right now.
• Max (n × m): the maximum demand each process declared.
• Allocation (n × m): instances currently allocated to each process.
• Need (n × m): remaining instances each process may still request. Need = Max - Allocation.

Safety algorithm

1. Let Work = Available, and Finish[i] = false for every process.
2. Find a process i with Finish[i] = false and Need[i] ≤ Work (every component, resource by resource).
3. If one exists: pretend it runs to completion and releases everything. Set Work = Work + Allocation[i] and Finish[i] = true. Go back to step 2.
4. If none exists: the state is safe if and only if every Finish[i] is true. The order in which processes were picked is a safe sequence.

This takes on the order of m × n² operations.

Resource-request algorithm

When process i requests a vector Request[i]:

1. If Request[i] > Need[i] in any component: error, the process exceeded its declared maximum.
2. If Request[i] > Available in any component: the resources are not free, so the process must wait.
3. Otherwise, pretend to grant it:
   • 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. If it is safe, grant the request for real. If it is unsafe, restore the old state and make the process wait.

Worked example: is the state safe?

Five processes P0 to P4 and three resource types A, B and C. The system has 9 instances of A, 6 of B and 8 of C.

Step 1: compute Available. Total allocated is A: 1 + 2 + 2 + 0 + 1 = 6; B: 1 + 1 + 0 + 2 + 0 = 4; C: 2 + 0 + 1 + 1 + 2 = 6. So Available = (9 - 6, 6 - 4, 8 - 6) = (3, 2, 2).

Step 2: compute Need = Max - Allocation.

Step 3: run the safety algorithm. Start with Work = (3, 2, 2). Each round, scan from P0 downwards and pick the first unfinished process whose Need fits in Work.

All five finish, so the state is safe, with safe sequence P0, P1, P3, P4, P2. As a check, the final Work (9, 6, 8) equals the total resources, as it must once every process has released everything.

Other safe sequences may exist; the algorithm only needs to find one. P2 must come last here, because its Need for A (7) is only satisfiable after nearly everyone has released their A instances.

Request 1: P1 requests (1, 0, 2) and is granted

1. Check against Need: (1, 0, 2) ≤ P1's Need (1, 1, 2). Fine.
2. Check against Available: (1, 0, 2) ≤ (3, 2, 2). Fine.
3. Pretend to grant:
   • Available = (3, 2, 2) - (1, 0, 2) = (2, 2, 0)
   • Allocation[P1] = (2, 1, 0) + (1, 0, 2) = (3, 1, 2)
   • Need[P1] = (1, 1, 2) - (1, 0, 2) = (0, 1, 0)
4. Safety check from Work = (2, 2, 0):

Safe sequence P1, P0, P3, P4, P2. The new state is safe, so the request is granted.

Request 2: P4 requests (3, 0, 0) and is denied

Go back to the original state (before request 1) and suppose instead P4 requests (3, 0, 0).

1. Need check: (3, 0, 0) ≤ P4's Need (3, 3, 1). Fine.
2. Available check: (3, 0, 0) ≤ (3, 2, 2). Fine; the resources are free right now.
3. Pretend to grant:
   • Available = (3, 2, 2) - (3, 0, 0) = (0, 2, 2)
   • Allocation[P4] = (1, 0, 2) + (3, 0, 0) = (4, 0, 2)
   • Need[P4] = (3, 3, 1) - (3, 0, 0) = (0, 3, 1)
4. Safety check from Work = (0, 2, 2):
   • P0 needs (3, 2, 1): A 3 > 0. No.
   • P1 needs (1, 1, 2): A 1 > 0. No.
   • P2 needs (7, 0, 1): A 7 > 0. No.
   • P3 needs (2, 0, 1): A 2 > 0. No.
   • P4 needs (0, 3, 1): B 3 > 2. No.

No process can be guaranteed to finish, so the state would be unsafe. The request is denied: P4 must wait, and the state is rolled back to Available = (3, 2, 2). Notice the resources were physically available; Banker's algorithm refuses because granting them could leave the system unable to satisfy everyone's declared maximums.

A request that must simply wait

If P4 instead requested (3, 3, 1), step 2 fails immediately: B 3 > Available B 2. The process waits without running the safety algorithm at all, because the resources do not exist to give.

Limitations of Banker's algorithm

• Processes must declare their maximum needs in advance, which real programs rarely know.
• The number of processes and resources must be fixed and known; real systems create processes and devices dynamically.
• Every request costs an O(m × n²) safety check.
• It is conservative: it may make processes wait when no deadlock would actually have happened, reducing utilization.

These are why general-purpose operating systems do not use it, but it is a standard exam and interview question because it tests whether you really understand safe states.

Deadlock detection

If a system neither prevents nor avoids deadlock, it can let deadlocks happen and then detect them periodically. Detection does not need maximum demands, only the current state.

Single instance: wait-for graph

Maintain the wait-for graph and search it for a cycle. Any cycle is a deadlock, and the processes on it are the deadlocked set.

Multiple instances: detection algorithm

The algorithm looks like the safety algorithm, with one key difference: it uses each process's current outstanding Request instead of its maximum Need. It asks: "Given what processes are asking for right now, can they all eventually finish?"

1. Work = Available. For each process, Finish[i] = true if it holds no resources (it cannot be part of a deadlock), otherwise false.
2. Find an unfinished process i with Request[i] ≤ Work.
3. If found: assume it gets what it asked for, finishes and releases everything: Work = Work + Allocation[i], Finish[i] = true. Go to step 2.
4. Otherwise: every process with Finish[i] = false is deadlocked.

The optimistic assumption in step 3 (a process that can get its current request will finish without asking for more) is fine, because if it later asks for more and blocks, the next detection run will catch it.

Worked detection example

Four processes and three resource types. The system has 4 instances of A, 3 of B and 3 of C.

Total allocated is (4, 3, 3), so Available = (0, 0, 0).

1. Work = (0, 0, 0). P0 requests nothing, so it can finish: Work = (0, 0, 0) + (1, 0, 1) = (1, 0, 1).
2. P1 requests (1, 0, 2): C 2 > 1. Cannot proceed.
3. P2 requests (2, 1, 0): A 2 > 1. Cannot proceed.
4. P3 requests (0, 1, 0): B 1 > 0. Cannot proceed.

No further progress is possible. P1, P2 and P3 are deadlocked.

Running the same algorithm on the earlier multi-instance RAG (R1 and R2 with two instances each) gives Work = (0, 0) initially; P2 requests nothing and finishes, freeing one R1, so Work = (1, 0); P1 can now get R1 and finishes, Work = (1, 1); P3 gets R2, Work = (2, 1); and P4 finishes, Work = (2, 2). Everyone finishes, which confirms that the cycle there was not a deadlock.

How often should detection run?

• On every blocked request: finds deadlocks immediately and identifies exactly which request closed the cycle, but is expensive.
• Periodically (every few minutes) or when CPU utilization drops below some threshold, a typical symptom of many processes being stuck: cheaper, but deadlocked processes stay stuck longer, and it is harder to tell which process caused it.

Databases choose a middle ground. PostgreSQL, for example, runs its deadlock check only after a lock wait has lasted longer than deadlock_timeout (one second by default), on the theory that most waits end quickly by themselves.

Recovery from deadlock

Once a deadlock is found, something must give.

Process termination

• Abort all deadlocked processes: simple and certain, but throws away all their work.
• Abort one at a time until the cycle is broken, rerunning detection after each abort: less work lost, but more detection overhead.

Choosing the victim should minimize cost. Factors include the process's priority, how long it has run and how close it is to finishing, how many resources it holds (and of which types), how many more it needs, whether it is interactive or batch, and how many processes would need to be terminated.

In the detection example, aborting P3 releases (0, 1, 1). Work becomes (1, 0, 1) + (0, 1, 1) = (1, 1, 2). Now P1's request (1, 0, 2) fits, so it finishes: Work = (1, 1, 2) + (2, 1, 0) = (3, 2, 2). Then P2's request (2, 1, 0) fits: Work = (3, 2, 2) + (1, 1, 1) = (4, 3, 3), all resources. Aborting one process was enough.

Resource preemption

Take resources from some processes and give them to others until the cycle breaks. Three issues must be handled:

1. Selecting a victim: which resources from which process, chosen to minimize cost.
2. Rollback: the process that lost a resource cannot simply continue. It must be rolled back to some earlier safe state and restarted from there. The simplest is a total rollback (restart from the beginning); more efficient is rolling back to a checkpoint, which requires the system to save process state periodically. Databases do this naturally: aborting a transaction undoes its changes using the log.
3. Starvation: if the same process is always chosen as the victim, it may never finish. The fix is to include the number of times it has been rolled back in the cost, so a repeatedly preempted process becomes less likely to be chosen.

Deadlock, livelock and starvation

These three are often confused. All three mean "something is not making progress", but differently.

• Deadlock: processes are blocked, waiting for each other in a cycle. Nothing changes state; CPU usage for them is zero.
• Livelock: processes are actively running and changing state in response to each other, but no useful progress results. The classic picture is two people meeting in a corridor who both step aside in the same direction, again and again. In code: two threads that each take one lock, fail to get the second, release, and retry in perfect lockstep forever; or a network protocol in which two nodes keep retransmitting after collisions at the same moment.
• Starvation: a process waits indefinitely while others continue to make progress. The system as a whole works, but one process is always passed over, for example a low-priority process in priority scheduling, or a writer in the readers-preference readers-writers solution.

Deadlocks in databases

Databases hit deadlocks constantly, because transactions take locks on rows as they go and hold them until commit (two-phase locking, covered in concurrency control).

Transaction T1                          Transaction T2
UPDATE accounts SET ... WHERE id = 1;   UPDATE accounts SET ... WHERE id = 2;
  -- locks row 1                          -- locks row 2
UPDATE accounts SET ... WHERE id = 2;   UPDATE accounts SET ... WHERE id = 1;
  -- waits for T2                         -- waits for T1   => DEADLOCK

Databases use detection and recovery:

• They maintain a wait-for graph of transactions and look for cycles, either on every lock wait (MySQL's InnoDB does this by default) or after a timeout (PostgreSQL's deadlock_timeout).
• They pick a victim, typically the transaction that is cheapest to roll back, abort it and release its locks. The victim's client receives an error: InnoDB reports "Deadlock found when trying to get lock; try restarting transaction", and PostgreSQL reports "deadlock detected".
• The application is expected to retry the aborted transaction.

Some systems also use timestamp-based prevention schemes that decide, when a transaction would wait, whether it may wait or must abort:

• Wait-die (non-preemptive): an older transaction may wait for a younger one; a younger transaction requesting a lock held by an older one is aborted ("dies") and restarts later with its original timestamp.
• Wound-wait (preemptive): an older transaction requesting a lock held by a younger one forces the younger to abort ("wounds" it); a younger one requesting from an older one waits.

Both prevent cycles because waits only go in one direction of age, and keeping the original timestamp on restart prevents starvation.

How applications reduce database deadlocks: access tables and rows in a consistent order (for example, always update the lower account ID first), keep transactions short, take the strongest lock you will need early (SELECT ... FOR UPDATE) rather than upgrading later, add indexes so updates lock fewer rows, and always retry on deadlock errors.

Deadlocks in multithreaded code

In application code, deadlocks almost always come from inconsistent lock ordering. The classic interview example is a bank transfer that locks the source account and then the destination. A transfer from A to B and a simultaneous transfer from B to A take the two locks in opposite orders, exactly the two-lock pattern at the start of this lesson.

The fix is to order locks by a stable key such as account ID:

#include <pthread.h>
#include <stdio.h>

struct account {
    int id;
    long balance;
    pthread_mutex_t lock;
};

/* Always lock the account with the smaller id first, whatever the
   direction of the transfer. Two opposite transfers then request the
   locks in the same order, so they cannot wait on each other in a cycle. */
static void transfer(struct account *from, struct account *to, long amount) {
    struct account *first = from->id < to->id ? from : to;
    struct account *second = from->id < to->id ? to : from;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    if (from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }
    pthread_mutex_unlock(&second->lock);
    pthread_mutex_unlock(&first->lock);
}

static struct account a = {1, 1000, PTHREAD_MUTEX_INITIALIZER};
static struct account b = {2, 1000, PTHREAD_MUTEX_INITIALIZER};

static void *a_to_b(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++)
        transfer(&a, &b, 1);
    return NULL;
}

static void *b_to_a(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++)
        transfer(&b, &a, 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=%ld b=%ld total=%ld\n", a.balance, b.balance, a.balance + b.balance);
    return 0;
}

It always finishes and always prints total=2000; the individual balances depend on timing, because a transfer is skipped when the source account is empty. With the naive "lock from, then lock to" version, the two threads can deadlock on the first iterations where their timing overlaps.

The same idea in Java, ordering by ID with synchronized blocks:

public class Bank {
    static final class Account {
        final int id;
        long balance;
        Account(int id, long balance) { this.id = id; this.balance = balance; }
    }

    static void transfer(Account from, Account to, long amount) {
        Account first = from.id < to.id ? from : to;
        Account second = from.id < to.id ? to : from;
        synchronized (first) {
            synchronized (second) {
                if (from.balance >= amount) {
                    from.balance -= amount;
                    to.balance += amount;
                }
            }
        }
    }
}

If two accounts could have the same key (or you order by System.identityHashCode, which can collide), you need a tie-breaker lock for the equal case.

Other practical techniques:

• Lock timeouts: pthread_mutex_timedlock or Java's ReentrantLock.tryLock(timeout, unit). On timeout, release everything held, back off for a random time and retry. This breaks hold and wait at runtime; the random delay avoids livelock.
• Hold fewer locks: use one coarser lock where contention is low, keep critical sections short, and never call unknown code (callbacks, listeners, virtual methods supplied by other modules) while holding a lock, since it might take locks of its own in an unknown order.
• Avoid nested locking: copy the data you need under one lock, release it, then work.
• Use higher-level concurrency structures: concurrent queues, actors or message passing reduce the number of locks a programmer manages directly.
• Tooling: in Java, jstack (or a thread dump) reports "Found one Java-level deadlock" with the threads and locks involved, and ThreadMXBean.findDeadlockedThreads() detects them programmatically. In C and C++, ThreadSanitizer reports lock-order inversions, and on a hung process gdb with thread apply all bt shows each thread blocked in a lock call. Inside the Linux kernel, lockdep flags potential ordering violations even if the deadlock never actually occurred during the test.

Interview questions

Q1. What is a deadlock?

A deadlock is a state in which each process in a set is blocked waiting for a resource held by another process in the same set, so none of them can ever proceed. For example, thread 1 holds lock A and waits for B while thread 2 holds B and waits for A. Without outside intervention, such as killing a process or preempting a resource, they wait forever.

Q2. What are the four necessary conditions for deadlock?

Mutual exclusion, where at least one resource can be held by only one process at a time; hold and wait, where a process holds resources while waiting for more; no preemption, where resources cannot be forcibly taken; and circular wait, where a cycle of processes each waits for the next one's resource. All four must hold simultaneously, so breaking any one prevents deadlock.

Q3. Does a cycle in a resource-allocation graph always mean deadlock?

Only if every resource type involved has a single instance; then a cycle is necessary and sufficient. With multiple instances, a cycle means deadlock is possible but not certain, because a process outside the cycle may release an instance that lets a process on the cycle continue. You then need the detection algorithm to decide.

Q4. What is the difference between deadlock prevention and avoidance?

Prevention designs the system so one of the four conditions can never hold, for example with a global lock ordering that rules out circular wait; it needs no runtime information but restricts how resources are requested. Avoidance allows all four conditions but checks each request at runtime, granting it only if the system stays in a safe state; it needs advance knowledge of maximum demands, as in Banker's algorithm.

Q5. What is a safe state? Is an unsafe state a deadlock?

A safe state is one in which there is some order, a safe sequence, in which every process can obtain its maximum remaining needs and finish. An unsafe state is not necessarily deadlocked; it only means the system can no longer guarantee avoiding deadlock if processes make worst-case requests. Every deadlocked state is unsafe, but not every unsafe state is deadlocked.

Q6. Explain Banker's algorithm.

Each process declares its maximum demand. The system tracks Available, Allocation, Max and Need, where Need is Max minus Allocation. On a request, it checks the request against Need and Available, pretends to allocate, and runs the safety algorithm, which repeatedly finds a process whose Need fits in the working Available, assumes it finishes, and adds its allocation back. If all processes can finish, the request is granted; otherwise it is rolled back and the process waits.

Q7. Why don't general-purpose operating systems use Banker's algorithm?

Processes rarely know their maximum resource needs in advance, processes and resources are created and destroyed dynamically, and running an O(m × n²) check on every request would be expensive. It is also conservative, delaying requests that would not have caused deadlock. So Linux and Windows largely ignore application-level deadlock and rely on lock ordering inside the kernel.

Q8. How does deadlock detection differ from the safety algorithm?

Both simulate processes finishing and releasing resources. The safety algorithm uses each process's maximum remaining Need to ask whether the system can be guaranteed to avoid deadlock in the future. The detection algorithm uses each process's current outstanding Request to ask whether a deadlock exists right now; any process that cannot finish in the simulation is deadlocked.

Q9. How can a system recover from deadlock?

By terminating processes, either all deadlocked processes or one at a time until the cycle breaks, choosing victims by cost such as priority, work done and resources held. Or by preempting resources from a victim, which requires rolling it back to a checkpoint or restarting it. To avoid starving one process, the number of times it has been chosen should count in the cost.

Q10. What is the difference between deadlock, livelock and starvation?

In deadlock, processes are blocked waiting for each other and nothing changes. In livelock, processes keep running and reacting to each other, such as repeatedly releasing and retrying locks in lockstep, but make no progress. In starvation, the system progresses but one process is perpetually denied a resource, as with a low-priority process in priority scheduling.

Q11. How do you prevent deadlocks in multithreaded code?

The main technique is a global lock ordering: whenever a thread needs several locks, it takes them in a fixed order, such as by ID, which makes circular wait impossible. Also hold as few locks as possible, never call unknown code while holding a lock, use timed lock attempts with random back-off as a fallback, and prefer higher-level concurrent structures. Tools like jstack, ThreadSanitizer and Linux's lockdep help find violations.

Q12. How do databases handle deadlocks?

Most use detection: they maintain a wait-for graph of transactions, look for cycles on lock waits or after a timeout, and abort a victim transaction, rolling back its changes and releasing its locks. The client receives a deadlock error and should retry. Some systems use timestamp-based prevention schemes like wait-die and wound-wait instead.

Q13. Explain wait-die and wound-wait.

Both use transaction timestamps, where an older transaction has a smaller timestamp. In wait-die, an older transaction may wait for a younger one, but a younger one that requests a lock held by an older one aborts and restarts. In wound-wait, an older transaction requesting a lock held by a younger one forces the younger to abort, while a younger requester waits. Restarted transactions keep their original timestamps so they eventually become the oldest and cannot starve.

Q14. Can a single thread deadlock?

Yes. If it locks a non-recursive mutex and then tries to lock the same mutex again, for example because one locked function calls another that takes the same lock, it waits for itself forever. Recursive (reentrant) locks, such as Java's synchronized and ReentrantLock, avoid this by counting how many times the owner has acquired them.

Q15. In the two-thread, two-lock example, which condition is easiest to break and how?

Circular wait, by making both threads acquire the locks in the same order, for example always A before B. Then whichever thread gets A first will also get B, and the other waits on A without holding anything, so no cycle can form. This requires no extra runtime machinery, which is why lock ordering is the standard technique.

Key takeaways

• Deadlock needs all four Coffman conditions at once: mutual exclusion, hold and wait, no preemption and circular wait.
• In a resource-allocation graph, a cycle means deadlock when resources have single instances; with multiple instances it only means deadlock is possible.
• Prevention breaks a condition; global lock ordering (breaking circular wait) is the most practical form.
• Avoidance keeps the system in a safe state; Banker's algorithm computes Need = Max - Allocation, checks a request against Need and Available, pretends to grant it and runs the safety algorithm.
• An unsafe state is not a deadlock, only the loss of a guarantee.
• Detection uses current requests instead of maximum needs; recovery terminates victims or preempts resources with rollback, counting past rollbacks to prevent starvation.
• Deadlock is everyone blocked; livelock is everyone busy without progress; starvation is one process always losing.
• Databases detect deadlocks and abort a victim transaction, so applications must retry; multithreaded code avoids them with consistent lock ordering and short critical sections.

Next lesson

Continue with Memory management.