Deadlocks: Conditions, Prevention, and Avoidance

Deadlock

A computer system has many exclusive resources, each usable by only one process at a time. Deadlock is permanent blocking of two or more processes due to resource competition or communication. Without external intervention, none can progress.

Dining Philosophers

Five philosophers sit around a circular table, either eating or thinking. There is a bowl of food and one chopstick between each pair. A philosopher must use both adjacent chopsticks to eat.

Number the philosophers 0 through 4; philosopher index has left chopstick index.

do {
	wait(chopstick[index]);
	wait(chopstick[(index + 1) % 5]);
	eat;
	signal(chopstick[(index + 1) % 5]);
	signal(chopstick[index]);
} while (true);

This algorithm can deadlock: if every philosopher holds the left chopstick, each waits indefinitely for the right one.

Chopsticks represent shared resources. Locking permits only one program or code section to access a resource at a time. A requester waits if another program holds the lock. Several programs using several locks can deadlock, for example when two programs each lock one file and wait for the other file to be unlocked.

Conditions for Deadlock

Four necessary conditions must hold simultaneously:

1. Mutual exclusion: a relevant resource cannot be simultaneously shared.
2. Hold and wait: a participant keeps resources while requesting more.
3. No preemption: those held resources cannot simply be forcibly reclaimed.
4. Circular wait: a closed chain of participants waits on resources held by the next.

Resource-Allocation Graphs

A resource-allocation graph is a directed graph G consisting of vertices V and edges E.

$V=P\cup R$, where P contains all processes and R all resource types. $E\subseteq(P\times R)\cup(R\times P)$. An edge $(P_i,R_j)$ requests a resource; $(R_j,P_i)$ assigns a resource instance to a process.

No cycle means no resource deadlock. A cycle can mean deadlock; with one instance per resource type, it implies deadlock.

Deadlock Prevention

Deadlock can be prevented by breaking a necessary condition:

1. Mutual exclusion: exclusivity cannot arbitrarily be removed from resources that require it; resources that can safely be shared need not require mutual exclusion.
2. Hold and wait: each process requests all required resources at the start. If any requested resource is unavailable, allocate none of the other resources. This can waste resources.
3. No preemption: if a process holding resources requests more and cannot obtain them immediately, it releases its held resources and requests them again later. This applies only to safely releasable and restorable resources, is costly and complex, and may invalidate earlier work.
4. Circular wait: order resources by type and assign numbers, requiring every process to request them in increasing order. Actual needs may follow another order, causing waste. The order must remain consistent, and new devices must respect it.

Ostrich Algorithm

The story that an ostrich hides its head from danger is a myth. A policy of ignoring a problem without a suitable solution is called the ostrich algorithm.

The ostrich algorithm is a fallback rather than a full solution. It addresses potential problems by assuming they are very rare. Some general-purpose operating systems do not provide unified avoidance or detection for every resource deadlock, but UNIX, MINIX, Windows, and their subsystems do not ignore all deadlocks. The assumption is that most users prefer an occasional deadlock to the performance cost of comprehensive handling. Since handling deadlocks can be costly, the policy balances performance and complexity. If a deadlock disrupts operation, manual intervention, including a restart when necessary, may be used.

Deadlock Avoidance

Avoidance evaluates allocation safety before granting resources. Grant a request if it will not produce an unsafe state; otherwise make the process wait.

A system is safe if an order such as $\langle P_1,P_2,\dots,P_n\rangle$ allows every process to obtain its declared maximum demand and finish in sequence. If no such sequence exists, the state is unsafe.

Given correct maximum claims and eventual completion and release, a safe state avoids deadlock. An unsafe state is not necessarily already deadlocked and need not become deadlocked.

Banker's Algorithm

A bank can evaluate whether a loan would disrupt its available funds. Bank resources resemble computer resources, and loans resemble allocations. The algorithm predicts whether an allocation is safe.

It uses these data structures:

1. Available: a vector of m current available counts, changing with allocations and releases. Available[j]=k means k instances of resource Rj are available.
2. Max: an n×m matrix of maximum demands. Max[i,j]=k means process i can require at most k instances of Rj.
3. Allocation: an n×m matrix of assigned resources. Allocation[i,j]=k means process i holds k instances of Rj.
4. Need: an n×m matrix of remaining maximum demand. Need[i,j]=k means process i may still require k instances of Rj.

The matrix relationship is:

$Need[i,j]=Max[i,j]-Allocation[i,j]$

Let Request_i be process Pi's request vector, with Request_i[j]=k requesting k instances of Rj. Check it as follows:

1. If $Request_i\le Need_i$, continue; otherwise report an error.
2. If $Request_i\le Available$, continue; otherwise wait.
3. Tentatively allocate and update:

$\begin{aligned}Available&=Available-Request_i\\Allocation_i&=Allocation_i+Request_i\\Need_i&=Need_i-Request_i\end{aligned}$

4. Check safety. Commit only if safe; otherwise undo the tentative updates and make the process wait.

For example, total resources are (9,3,6), with these demands and allocations:

The resource and allocation vectors give Available (0,1,1). This does not satisfy P1, P3, or P4, but P2 needs only one R3 instance. When P2 completes and releases its allocation, Available becomes (6,2,3), enough for any remaining process. P2, P1, P3, P4 is therefore a safe sequence.

If no safe sequence exists, the system is unsafe and may enter deadlock.