Deadlock Avoidance

operating-systems concurrency

Definition

Deadlock Avoidance

Deadlock avoidance is a strategy where the operating system selectively grants resource requests only if the system is guaranteed to remain in a safe state. Unlike prevention, it allows the Coffman conditions to potentially exist but prevents the specific sequence of events that leads to a deadlock.

Safe and Unsafe States

• Safe State: A state where there exists at least one sequence of process completions (an “execution path”) that allows every process to satisfy its maximum resource needs without deadlocking.
• Unsafe State: A state where no such sequence exists. A deadlock is not necessarily present in an unsafe state, but it is possible or even unavoidable in the future.

Formal Notation

To evaluate the safety of a state, the system uses the following vectors and matrices for $n$ processes and $m$ resource categories:

• Resource Vector ($R$): Total amount of each resource in the system.
  $R=(R_1,R_2,\dots ,R_m)$
• Available Vector ($V$): Number of unassigned resources currently free.
  $V=(V_1,V_2,\dots ,V_m)$
• Claim Matrix ($C$): Maximum requirement of each process. $C_{ij}$ is the maximum need of process $i$ for resource $j$.
• Allocation Matrix ($A$): Current resource assignment. $A_{ij}$ is the amount of resource $j$ currently held by process $i$.

Strategies

Deadlock avoidance requires that processes declare their maximum resource needs in advance.

Process Initiation Denial

The OS refuses to start a new process $P_{n+1}$ if its potential requirements, combined with the maximum claims of all existing processes, could exceed the total system resources. A new process is only admitted if:

$\forall i\in \{1,\dots ,m\}:R_i\ge C_{(n+1)i}+{\sum }_{k=1}^n{C}_{ki}$

This strategy is highly conservative as it assumes all processes will request their maximum resources at the same time.

Extreme Defensiveness

This strategy is analogous to a bank that only allows a new customer to open an account if the vault contains enough cash to pay out the maximum credit limit of every existing customer AND the new customer simultaneously. While this prevents any possibility of a run on the bank, it is highly restrictive because it ignores the statistical reality that processes rarely require their maximum resource claims at the same instant.

Resource Allocation Denial

The OS evaluates each individual resource request. It provisionally “grants” the request and then runs a safe state algorithm to check if the resulting state allows for a sequence of process completions. If the state is unsafe, the request is denied.

Banker’s algorithm.

Comparison

Deadlock avoidance provides higher concurrency than prevention because it does not impose rigid ordering or restrictive allocation rules, but it requires prior knowledge of process resource needs.

Pessimism of Avoidance

Avoidance strategies are fundamentally defensive. They assume that every process will eventually require its maximum declared resource claim simultaneously. In reality, a process might only need its maximum for a short duration or might never reach it depending on input data. Consequently, a system may be in an unsafe state but never actually reach a deadlock.