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

Introduction

In computer systems many resources are exclusive, meaning only one process can use them at a time. When two or more processes each hold a resource while waiting for another, a deadlock occurs.

Resources

Resources are divided into preemptable (e.g., memory) and non‑preemptable (e.g., printers, disks). Deadlocks are most often caused by non‑preemptable resources.

Resource Acquisition

Processes request resources via system calls such as open. Semaphores or mutexes are commonly used to control access.

Mutex is a synchronization primitive that allows only one thread to hold the lock at a time.

Example pseudocode for acquiring and releasing a semaphore:

typedef int semaphore;
semaphore aResource;

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

When multiple processes acquire resources in different orders, deadlock can arise:

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);
}

Deadlock Definition

A deadlock occurs when each process in a set is waiting for an event that only another process in the same set can trigger, leading to an indefinite wait.

Conditions for Resource Deadlock

Mutual exclusion

Hold and wait

No preemption

Circular wait

Breaking any of these conditions prevents deadlock.

Deadlock Models

Holt’s 1972 model uses circles for processes and squares for resources, with directed edges indicating allocation and request relationships.

Deadlock Handling Strategies

Ostrich Algorithm

Ignore the problem; suitable only when deadlocks are extremely rare.

Detection and Recovery

Detect deadlocks using resource‑allocation graphs or matrix‑based algorithms, then recover by preemption, rollback, or killing processes.

Banker’s Algorithm (Avoidance)

Before granting a request, simulate the allocation to ensure the system remains in a safe state; otherwise, delay the request.

Breaking Conditions

Techniques include:

Eliminate mutual exclusion (e.g., spooling printers).

Require processes to request all needed resources at once.

Allow preemption of resources.

Impose a total ordering on resource acquisition.

Other Issues

Communication Deadlock

Occurs when processes wait for messages that never arrive; can be mitigated with timeouts.

Livelock

Processes repeatedly release and reacquire resources without making progress.

Starvation

Some processes may never obtain needed resources due to scheduling policies.

Conclusion

Deadlocks are a fundamental problem in operating systems. Proper detection, avoidance, and recovery techniques—such as the banker’s algorithm, resource ordering, or even the ostrich approach—are essential to maintain system reliability.