Understanding Deadlocks: Causes, Conditions, Prevention, Detection, and Recovery

Preface

In computer systems many resources are exclusive, meaning only one process can use a resource at a time. For example, a printer is an exclusive resource; two printers cannot output simultaneously without causing file‑system failure. The operating system therefore grants a process exclusive access to a resource.

When two processes each hold an exclusive resource while waiting for the other, both become blocked and never release their resources – this situation is called a deadlock.

Deadlocks can occur at any level, even across machines or within database systems. For instance, process A locks record R1, process B locks record R2, and each later requests the other's lock, creating a deadlock.

The article will discuss what deadlocks are, their conditions, prevention techniques, and related concepts such as livelocks.

Resources

Most deadlocks involve resources. When a process has exclusive (or "mutual exclusion") access to a device or file, we call that object a resource. Resources are classified as preemptable and non‑preemptable .

Preemptable and Non‑preemptable Resources

A preemptable resource can be taken away from a process without adverse effects; memory is an example because any process can be forced to release memory.

A non‑preemptable resource cannot be taken away unless an error occurs; a CD drive is an example because a process cannot be interrupted while using it.

Deadlocks are closely related to non‑preemptable resources, although preemptable resources can also cause deadlocks that are usually resolved by redistributing resources.

The abstract sequence of events for using a resource is shown below:

If a requested resource does not exist, the requesting process blocks until the resource becomes available. Some OSes automatically block the process; others return an error code and require the process to retry later.

Resource requests are typically performed via system calls such as request or by opening a special file representing the resource with open. If the file is already in use, the caller blocks until the owning process closes it.

Resource Acquisition

For database records, processes often use a semaphore (initialized to 1) or a mutex to control access.

Mutexes are program objects that allow multiple threads to share a resource safely by acquiring a lock before use and releasing it afterward.

Below is pseudo‑code illustrating semaphore acquisition and release:

typedef int semaphore;
semaphore aResource;

void processA(void) {
  down(&aResource);
  useResource();
  up(&aResource);
}

When multiple resources must be locked simultaneously, the code becomes:

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void) {
  down(&aResource);
  down(&bResource);
  useAResource();
  useBResource();
  up(&aResource);
  up(&bResource);
}

With two processes (A and B) each needing both resources, a change in lock order can cause deadlock:

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void) {
  down(&aResource);
  down(&bResource);
  useBothResource();
  up(&bResource);
  up(&aResource);
}

void processB(void) {
  down(&bResource); // changed order
  down(&aResource);
  useBothResource();
  up(&aResource);
  up(&bResource);
}

In this scenario each process holds one resource and waits for the other, creating a circular wait and thus a deadlock.

Deadlock

A deadlock is defined as a set of processes where each process is waiting for an event that only another process in the set can trigger, causing indefinite blocking.

Resource deadlock is the most common type, but other types exist.

Conditions for Resource Deadlock

Mutual exclusion: each resource is assigned to at most one process.

Hold and wait: processes holding resources may request additional ones.

Non‑preemptability: a resource cannot be forcibly taken from its holder.

Circular wait: a closed chain of processes exists, each waiting for a resource held by the next.

All four conditions must hold simultaneously for a deadlock to occur; breaking any one prevents deadlock.

Deadlock Models

Holt's 1972 model uses circles for processes and squares for resources. An arrow from a resource to a process indicates the resource is held; an arrow from a process to a resource indicates a pending request.

Deadlock Handling Strategies

Ignore the problem (the "ostrich algorithm").

Detect deadlock and recover.

Prevent deadlock by careful resource allocation.

Break one of the four necessary conditions.

Ostrich Algorithm

The simplest approach is to pretend deadlocks never happen, which may be acceptable if their frequency is extremely low.

Deadlock Detection and Recovery

Detection can be performed each time a resource is requested (high CPU cost) or periodically (e.g., every k minutes or when CPU usage drops).

Detection for Single‑Resource Types

A resource‑allocation graph is built; any cycle indicates a deadlock.

Detection for Multiple‑Resource Types

A matrix‑based algorithm uses the existing resource vector, the current allocation matrix C, and the request matrix R to determine safe states.

Recovery Methods

Preemption: forcibly take a resource from a process (difficult and intrusive).

Rollback: revert processes to a previously saved checkpoint where the deadlock had not formed.

Kill processes: terminate one or more deadlocked processes to break the cycle.

Deadlock Avoidance

Banker’s Algorithm (Single Resource)

Dijkstra’s Banker’s algorithm checks each request against a safety criterion; if granting the request would lead to an unsafe state, the request is delayed.

Example diagrams illustrate safe and unsafe allocations.

Breaking the Four Conditions

Break mutual exclusion (e.g., use spooling printers).

Break hold‑and‑wait by requiring processes to request all needed resources up front.

Break non‑preemptability via virtualization.

Break circular wait by imposing a total ordering on resource acquisition.

Other Issues

Two‑Phase Locking

In databases, a transaction first acquires all required locks (phase one); if successful, it proceeds to the execution phase (phase two). If any lock cannot be obtained, all locks are released and the transaction restarts.

Communication Deadlock

Occurs when processes wait for messages from each other; timeouts can mitigate this problem.

Livelock

Processes repeatedly release and reacquire locks without making progress, analogous to two people constantly yielding to each other.

Starvation

A process may never obtain a needed resource if the scheduling policy always favors other processes, leading to indefinite postponement.

Summary

Deadlocks are a universal problem in operating systems where each process in a set waits for resources held by others, causing infinite blocking. Detection and avoidance rely on identifying safe states (e.g., via the Banker’s algorithm) or deliberately breaking one of the four necessary conditions. Additional concerns include communication deadlocks, livelocks, and starvation.

Conclusion

A correction notice has been sent to the publisher.