Understanding deadlocks

If each process holds a resource while waiting for another, none may be able to move forward. To distinguish ordinary waiting from deadlock, it helps to understand the conditions that must exist together.

How processes acquire resources

1. Request

A process asks the system for a resource. The system checks whether it is available. If another process holds it, the requesting process may have to wait.

2. Use

The process performs its work using the allocated resource. Code that accesses shared state is protected within a critical section where necessary.

Concurrent access to shared resources can cause inconsistent data or unexpected behavior. Critical sections protect operations that must not overlap.

3. Release

When the process finishes using a resource, it releases it so another waiting process can proceed.

The four conditions for deadlock

All four conditions must hold for a resource deadlock to occur.

Mutual exclusion

At least one resource can be used by only one process at a time.

Hold and wait

A process holds at least one resource while waiting for another.

No preemption

A resource cannot be forcibly taken from its current holder.

Circular wait

In a set of processes {P1, P2, ..., Pn}, each process waits for a resource held by the next, and Pn waits for a resource held by P1.

Resource-allocation graphs

A resource-allocation graph shows which resources processes hold and which they are waiting for. It helps visualize the relationships involved in a potential deadlock.

P1 holds an R2 resource and waits for R1. P2 holds R1 and R2 resources and waits for R3. P3 holds R3 but does not request anything else. Once P3 releases R3, P2 can continue, so there is no circular wait in this example.

If P3 also waits for R2 while holding R3, the example forms a circular wait and reaches deadlock.

Prevention

Deadlock prevention ensures that at least one of the four conditions cannot occur.

Remove mutual exclusion

Make resources shareable where possible. This is not practical for every resource, and shared access may require synchronization.

Remove hold and wait

Require a process to request all necessary resources before it starts. It proceeds only when all are available together.

Allow preemption

If a process cannot obtain an additional resource, require it to release resources it already holds and request the complete set again later.

Remove circular wait

Assign an ordering to resource types and require every process to request them in that order.

Avoidance

Before granting a request, the system checks whether the resulting state would still allow processes to complete. Requests that would leave the system unsafe are deferred.

Resource-allocation graphs

For the appropriate resource model, a graph can track potential future requests. A request is not granted if doing so would create an unsafe cycle.

Banker's algorithm

Processes declare their maximum resource needs in advance. For resource types with multiple instances, the algorithm checks whether granting a request leaves a safe sequence in which all processes can finish. If not, the request waits.

Avoidance can reduce resource utilization because the system must account for declared maximum needs, even when processes do not use them immediately.

Detection

Rather than preventing every deadlock, a system can check for one periodically or when particular conditions occur.

A detection algorithm

Detection considers currently allocated resources, outstanding requests, and available resources.

1. Initialize a working vector with the available resources.
2. Look for an unfinished process whose remaining request can be met by that vector.
3. Assume that process finishes, add its allocated resources back to the vector, and mark it finished.
4. Repeat until no more processes can be marked finished.
5. Processes left unable to finish may identify the deadlocked set.

Frequent detection adds overhead. Running checks less often or limiting their scope can reduce that cost.

Recovery

Once a deadlock is found, the system needs a way to restore progress.

Process termination

Terminating one or more involved processes releases resources. This can resolve the deadlock quickly, but loses work.

Resource preemption

Where the resource permits it, the system reclaims resources from selected processes and reallocates them. The affected processes wait or restart later. Selection can consider priority, resource needs, and waiting time.