Deadlock Fundamentals

01 Introduction

Unit 6 presented the mechanisms that make concurrent programs correct: locks, semaphores, monitors, and condition variables. Each of them is a tool for ensuring that shared state is accessed consistently and that processes wait for conditions to become true. Used correctly, those tools produce programs that are correct. Used incorrectly — or used correctly but in an unlucky interleaving — they can produce a state in which no process can make progress. That state is deadlock.

Deadlock is the situation in which a set of processes is permanently blocked because each is waiting for a resource that another process in the set holds. Because every process in the set is waiting, none of them can release the resources they hold, and the wait is permanent. The system does not crash; it simply stops making progress. On a general-purpose machine, a deadlock in a user program may leave a few threads hung while the rest of the system runs normally. In a kernel, a deadlock can hang the entire machine. In a database, a deadlock can prevent a transaction from committing. The consequences range from annoying to catastrophic, and the problem is one of the classical concerns of operating-system design.

The study of deadlock has a long history. Edsger Dijkstra identified the problem in the 1960s in the context of the dining philosophers problem, and the deadly embrace of two tape drives was a familiar failure mode in the batch systems of the era. The formal treatment — the four necessary conditions, the resource allocation graph, the Banker's algorithm — was developed during the 1970s and remains the standard pedagogical framework. This unit presents that framework in the six lessons that follow.

This first lesson sets the foundation. It defines deadlock and distinguishes it from the related phenomena of starvation and livelock. It presents the system model of resources and requests, describes the lifecycle of a resource from request to release, and shows how the cycle of waiting arises. It examines the classic real-world examples — the dining philosophers, the bridge crossing, the traffic intersection — and shows how the same pattern appears in concurrent programs. It closes with a discussion of the scope of the problem and the four strategies that operating systems use to deal with it: prevention, avoidance, detection, and recovery.

02 Learning objectives

This lesson contributes to U7.1 and U7.2, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• Operating System Concepts — Chapter 8, Sections 8.1–8.3, System Model, Deadlock in Multithreaded Applications, and Deadlock Characterization. The standard treatment of the system model and the four necessary conditions.
• OSTEP — Chapter 32, Concurrency Bugs, through the section on Deadlock. OSTEP's treatment focuses on the practical programming view: deadlock as a bug in a concurrent program, introduced through the code that produces it.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 6, Deadlocks, through the section on deadlock detection. A comprehensive treatment that presents the four conditions, the resource-allocation graph, and the dining philosophers alongside the theory.
• Silberschatz et al. — Chapter 8, Sections 8.4–8.8. The formal treatment of the resource allocation graph and the four strategies for handling deadlock.
• Dijkstra, E. W. — Hierarchical Ordering of Sequential Processes. Acta Informatica, 1971. The paper that introduced the dining philosophers problem and the concept of a deadlock.
• Linux man pages: man 7 pthreads (the section on deadlock), man 3 pthread_mutex_init (the discussion of the error-checking and robust mutex types), man 2 fcntl (the record-locking interface, which can deadlock).

04 Core content

4.1 What is deadlock?

A deadlock is a situation in which a set of two or more processes is permanently blocked because each process in the set is waiting for a resource that another process in the set holds. Because every process is waiting, none of them can release the resource it holds, and none of them can acquire the resource it is waiting for. The processes are stuck forever.

The defining feature of deadlock is mutual, permanent blockage. It is not the same as one process waiting for a resource that another process will eventually release; in that case, progress is slow but does happen. Deadlock is the case where no process in the set can proceed, no matter how long the system runs, because the conditions that would allow progress cannot be satisfied without external intervention.

The simplest illustration is two processes and two resources. Process P₁ holds resource R₁ and needs R₂ to continue. Process P₂ holds R₂ and needs R₁. Each waits for a resource the other holds. Neither will release its resource until it gets what it is waiting for. The system cannot make progress.

4.2 The system model

To reason about deadlock precisely, we need a model of the system. The standard model has three elements: resources, processes, and the requests that processes make for resources.

Resources

A resource is any entity that a process may need to complete its work. Resources come in types, each with some number of instances. Examples: a printer (type: printer, one instance), a memory page (type: page frame, many instances), a file (type: file, one instance per open), a semaphore (type: semaphore, one instance), a lock (type: mutex, one instance), a CPU core (type: core, one instance per core).

Processes

A process (or thread, or task) is an execution context that uses resources to make progress. Each process follows a sequence of operations: it requests resources, uses them, and releases them.

Requests

A request is an operation by which a process asks for an instance of a resource type. If an instance is available, the request is granted; if none is available, the process may block until one becomes available.

The model abstracts away the physical details. A mutex is a resource with one instance. A counting semaphore is a resource with N instances, where N is the initial value. A file is a resource with one instance per open. A printer is a resource with one instance. The model does not care about the physical form; it cares only about the operations that processes perform on the resource and the way the resource is shared among them.

A resource is reusable if it can be released and reacquired by another process. A lock is reusable: a process releases it and another process acquires it. A message is not reusable: once consumed, it is gone. Deadlock in the classical sense concerns reusable resources, because the cycle of waiting depends on the fact that a process can hold a resource for a long time. A slightly different phenomenon, called resource starvation, arises with consumable resources, and is covered in Lesson 7.2.

4.3 The resource lifecycle

Every use of a resource by a process follows the same three-step pattern:

1. Request. The process asks the operating system for an instance of the resource. If the request cannot be granted immediately — because all instances are in use — the process is placed on a wait queue for that resource and blocks.
2. Use. The process uses the resource. For a lock, this is the critical section; for a file, this is the read or write; for a printer, this is the print job.
3. Release. The process releases the resource. The operating system may then grant a pending request from another process that is waiting for the resource.

A process may request many resources over its lifetime, and at any moment it may hold several at once. The pattern of requests and releases is called the process's resource usage sequence. A process may request a resource, use it, release it, then request a different resource, and so on. The set of resources a process holds at any moment is its holding set; the set of resources it is waiting for is its waiting set.

The deadlock condition arises when the holding set of one process intersects the waiting set of another, and the waiting set of the first intersects the holding set of the second. The cycle of mutual dependency is the defining feature of deadlock.

4.4 How the cycle arises

The cycle of waits and holdings does not arise from a single unfortunate request. It arises from the interaction of several requests over time. The following trace illustrates how the simple two-process deadlock of Figure 7.1 develops.

At each step before the deadlock, the operating system made a reasonable decision. At step 1, R₁ was free, so it was granted to P₁. At step 2, R₂ was free, so it was granted to P₂. The deadlock was not caused by a mistake at any one step; it was caused by the way the requests interleaved. If P₁ had requested R₂ before P₂ requested it, or if P₂ had not requested R₁ until after P₁ had released R₂, no deadlock would have occurred.

4.5 Real-world examples

Deadlock is not a theoretical construct. It appears in operating-system kernels, database systems, embedded systems, network protocols, and any concurrent program that uses multiple locks. The following examples are the classics.

• Dining philosophers. Five philosophers sit at a round table, each alternating between thinking and eating. Between each pair of adjacent philosophers lies a single fork — five forks for five philosophers. To eat, a philosopher must pick up both forks adjacent to them. If every philosopher picks up their left fork at the same time, all five wait forever for their right fork, which their neighbour holds. This is the canonical illustration of deadlock, introduced by Dijkstra in 1971.
• The deadly embrace. The classic early-computing example: two processes each need two tape drives; process A holds drive 1 and requests drive 2, while process B holds drive 2 and requests drive 1. Neither can proceed, and the system hangs. The term deadly embrace is a historical name for deadlock.
• Bridge crossing. Two cars approach a narrow bridge from opposite ends. The bridge is only wide enough for one car at a time. Car A enters the bridge and stops because car B has also entered from the other end. Neither can move forward and neither can back up; both are stuck. This is a deadlock of a spatial resource.
• Traffic intersection. Four cars arrive at a four-way intersection simultaneously, each going straight. If the intersection has no traffic lights, and each car enters the intersection and waits to see what the others will do, all four block each other. This is a deadlock of a shared spatial resource.
• Database transaction deadlock. Two transactions each acquire a lock on one row of a table and then try to acquire a lock on the other's row. Neither can proceed; the database system must detect the deadlock and abort one of the transactions. This is a common occurrence in a busy database, and modern database systems have sophisticated mechanisms for handling it.
• Kernel deadlock. The Linux kernel uses many locks, and a bug in the locking discipline can deadlock the entire machine. The kernel's spinlock and mutex primitives are designed to detect and warn about some forms of misuse — for example, acquiring a mutex twice from the same thread — but not every form of deadlock is detectable. Kernel deadlock is one of the reasons the discipline of consistent lock ordering is so important in kernel development.
• Priority inversion. A related problem, examined in Lesson 5.4, in which a high-priority task is delayed by a low-priority task holding a resource. This is not deadlock in the strict sense — the low-priority task can make progress — but it produces a similar effect of a high-priority task being unable to run. The Mars Pathfinder incident is the canonical example.

4.6 Deadlock, starvation, and livelock

Three related phenomena are often confused. They are distinct, and the distinctions matter for diagnosis and solution.

The distinction between deadlock and starvation is the most important. A deadlocked process is blocked; a starved process is runnable but never scheduled, or is repeatedly overtaken by other processes. A deadlocked system makes no progress at all; a system with starvation makes progress overall, but one specific process does not. The solution to starvation is aging (Lesson 5.4); the solution to deadlock is prevention, avoidance, or detection and recovery (the rest of this unit).

Livelock is the more subtle case. A livelocked process is not blocked — it is running — but it is not making progress. The classic example is two people walking toward each other in a narrow corridor: each steps to the side to let the other pass, they step the same direction, then both step the other way, and so on. In a concurrent program, livelock appears in lock-free algorithms where two threads repeatedly retry a compare-and-swap operation, each invaliding the other's attempt, so neither makes progress. Livelock is rarer than deadlock and harder to detect, because the system appears busy.

4.7 Deadlock in concurrent programs

In the previous unit, we saw that locks and semaphores are the tools for making concurrent programs correct. The price of those tools is the possibility of deadlock. A program that acquires two locks in inconsistent order across different threads is a program that can deadlock.

The pattern is direct: if thread T₁ acquires lock L₁ and then lock L₂, while thread T₂ acquires L₂ and then L₁, and both reach their second acquisition before either reaches its release, then T₁ holds L₁ and waits for L₂, and T₂ holds L₂ and waits for L₁. The deadlock is not caused by a bug in either thread; both threads are doing what they were written to do. The deadlock is caused by the interaction between them.

The standard prevention technique is a global lock order. All threads acquire locks in the same order — always L₁ before L₂, never the reverse. If every thread follows the same order, no cycle of waits and holdings can form, because the cycle would require a thread to wait for a lock with a lower order than one it already holds, which the discipline forbids. This is the simplest and most widely used form of deadlock prevention, and it is the subject of Lesson 7.4.

Lock ordering is easy to state and hard to maintain. A large program has many locks and many code paths, and the discipline must be applied consistently everywhere. A single function that acquires locks in the wrong order, or a single code path that violates the order under some condition, can reintroduce the possibility of deadlock. This is why some systems avoid the problem entirely by using a single global lock, at the cost of serializing all concurrent work — a trade-off examined in Lesson 6.3.

4.8 The four strategies

Operating systems have four strategies for dealing with deadlock. Each is appropriate in a different context.

Prevention

Design the system so that at least one of the necessary conditions for deadlock can never hold. The usual approach is to impose a global lock order (breaking the circular-wait condition) or to require that a process acquire all its resources at once (breaking the hold-and-wait condition). Prevention guarantees that deadlock cannot occur, at the cost of restricting the system's behaviour. Examined in Lesson 7.4.

Avoidance

Allow the necessary conditions to hold, but make scheduling decisions that keep the system in a safe state — a state from which every process can still complete. Before granting a resource request, the system checks whether granting it would leave the system in an unsafe state; if so, the request is deferred. Avoidance is more flexible than prevention but requires advance knowledge of each process's maximum resource needs. Examined in Lessons 7.5 and 7.6.

Detection and recovery

Allow deadlock to occur, detect it when it does, and recover by aborting one or more processes or rolling them back. Detection is done periodically by examining the state of the system for a cycle of waits and holdings. Recovery requires a policy for choosing which process to abort and how to undo its effects. Examined in Lesson 7.7.

Ignorance

Ignore the problem and hope it does not occur. If deadlocks are rare enough — a few per year on a system that runs millions of operations — the cost of preventing or detecting them may exceed the cost of simply rebooting when one occurs. This is the strategy used by most general-purpose operating systems, including Linux, for user-level deadlocks. It is called the ostrich algorithm: bury your head in the sand and hope the problem goes away.

The four strategies are not mutually exclusive. A system may prevent some forms of deadlock, avoid others, detect and recover from still others, and ignore the rest. Linux, for example, uses lock ordering in the kernel to prevent kernel deadlocks, provides error-checking and robust mutex types to help user programs detect some forms of misuse, and relies on the ostrich algorithm for user-space deadlocks — a user program that deadlocks stays hung until it is killed. The choice of strategy depends on the cost of the mechanisms and the frequency of the problem.

4.9 Common misconceptions

05 Worked example

The following example traces a two-thread lock-ordering deadlock in C, shows the interleaving that produces it, and demonstrates the fix.

pthread_mutex_t L1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t L2 = PTHREAD_MUTEX_INITIALIZER;

void *t1(void *arg) {
    pthread_mutex_lock(&L1);
    sleep(1);                       /* make the race easier to observe */
    pthread_mutex_lock(&L2);
    /* critical section */
    pthread_mutex_unlock(&L2);
    pthread_mutex_unlock(&L1);
    return NULL;
}

void *t2(void *arg) {
    pthread_mutex_lock(&L2);
    sleep(1);
    pthread_mutex_lock(&L1);
    /* critical section */
    pthread_mutex_unlock(&L1);
    pthread_mutex_unlock(&L2);
    return NULL;
}

gdb -p $(pgrep deadlock)
(gdb) thread apply all bt
(gdb) info threads
(gdb) quit

void *t2_fixed(void *arg) {
    pthread_mutex_lock(&L1);        /* acquire in the same order as T1 */
    sleep(1);
    pthread_mutex_lock(&L2);
    /* critical section */
    pthread_mutex_unlock(&L2);
    pthread_mutex_unlock(&L1);
    return NULL;
}

void *t1_retry(void *arg) {
    for (;;) {
        pthread_mutex_lock(&L1);
        if (pthread_mutex_trylock(&L2) == 0) {
            /* got both locks */
            pthread_mutex_unlock(&L2);
            pthread_mutex_unlock(&L1);
            return NULL;
        }
        /* could not get L2; release L1 and retry */
        pthread_mutex_unlock(&L1);
        sched_yield();              /* give the other thread a chance */
    }
}

PID=$(pgrep deadlock)
cat /proc/$PID/status | grep -E 'State|Threads'
cat /proc/$PID/task/*/stat | awk '{print $1, $2, $3}'

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A deadlock is a situation in which a set of processes is permanently blocked because each waits for a resource that another holds. Because every process is waiting, none can release its resource, and the system makes no progress.
• The system model has three elements: resources (entities a process needs, in types with instances), processes (execution contexts that use resources), and requests (operations by which a process asks for a resource).
• The resource lifecycle has three steps: request (the process may block if no instance is available), use, and release. A process that blocks in the request step has added the resource to its waiting set.
• A deadlock arises when the waits and holdings form a cycle: the holding set of one process intersects the waiting set of another, and vice versa. The cycle has no exit, so no process can proceed.
• Deadlock is a race condition: the same program with the same input may deadlock on one run and complete normally on another, depending on the interleaving chosen by the scheduler.
• Classic examples include the dining philosophers, the deadly embrace of two tape drives, the bridge crossing, the traffic intersection, and the database transaction deadlock. The same pattern appears in any concurrent program that uses multiple locks.
• Deadlock, starvation, and livelock are three distinct phenomena. In deadlock, processes are blocked and the system makes no progress. In starvation, one process is indefinitely postponed while the system makes progress. In livelock, processes are running but not making progress.
• The standard prevention technique for deadlock in concurrent programs is global lock order: all threads acquire locks in the same order, so that no cycle of waits and holdings can form.
• Operating systems use four strategies to deal with deadlock: prevention (make it impossible), avoidance (steer clear of unsafe states), detection and recovery (detect and break the cycle), and ignorance (the ostrich algorithm).
• Linux uses the ostrich algorithm for user-space deadlocks, on the grounds that they are rare and the cost of preventing them would be imposed on all programs.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 8, Sections 8.1–8.3.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 32. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 6.
• Dijkstra, E. W. Hierarchical Ordering of Sequential Processes. Acta Informatica, 1971. The paper that introduced the dining philosophers problem.
• Coffman, E. G., Elphick, M. J., & Shoshani, A. System Deadlocks. ACM Computing Surveys, 1971. The paper that formalized the four necessary conditions for deadlock.
• Holt, R. C. Some Deadlock Properties of Computer Systems. ACM Computing Surveys, 1972. The paper that introduced the resource-allocation graph.
• Havender, J. W. Avoiding Deadlock in Multitasking Systems. IBM Systems Journal, 1968. The first published treatment of lock ordering.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods. The discussion of deadlock in the kernel.
• Linux man-pages: man 7 pthreads, man 3 pthread_mutex_init, man 3 pthread_mutex_lock, man 2 fcntl.