Deadlock Avoidance

Deadlock prevention works by breaking one of the four necessary conditions.

However, prevention can cause:

Low resource utilization
Reduced system throughput
Inefficiency

Deadlock avoidance takes a different approach.

Instead of restricting how resources are requested, the system:

Dynamically examines each resource request and decides whether granting it could lead to a future deadlock.

Core Idea of Deadlock Avoidance

To avoid deadlock, the system must know in advance the maximum resource needs of each thread.

Using this information, the system ensures:

The system never enters an unsafe state.

Safe State (Core Concept)

This is the most important idea in avoidance.

Definition

A system is in a safe state if there exists a safe sequence of threads:

<T_1, T_2, ..., T_n>

Such that for each thread $T_i$ :

Its remaining resource needs can be satisfied by:
- The currently available resources
- Plus resources held by all $T_{j}$ $where j < i$

If this ordering exists, every thread can complete.

Important Relationships

Safe state → No deadlock
Deadlock → Unsafe state
Unsafe state ≠ Deadlock (but may lead to it)

Key Concept: Safe State

A system is in a safe state if:

There exists a sequence of thread execution
Such that each thread can obtain its required resources
Complete its execution
And release resources for others

If no such sequence exists, the system is in an unsafe state.

Important:

Unsafe state ≠ Deadlock
But unsafe state → Deadlock is possible

Deadlock avoidance ensures the system never enters an unsafe state.

Resource-Allocation State

To make decisions, the system considers:

Available resources
Allocated resources
Maximum resource demands of each thread

This information defines the system’s resource-allocation state.

How Deadlock Avoidance Works

Whenever a thread makes a request:

The system pretends to allocate the resource.
It checks whether the system remains in a safe state.
If safe → grant the request.
If unsafe → thread must wait.

Thus, deadlock is avoided dynamically.

Example

consider a system with twelve resources and three threads: T0, T1, and T2. Thread T0 requires ten resources, thread T1 may need as many as four, and thread T2 may need up to nine resources. Suppose that, at time t0, thread T0 is holding five resources, thread T1 is holding two resources, and thread T2 is holding two resources. (Thus, there are three free resources.)

🔹 Initial Situation (Time t₀)

We are given:

Total resources = 12
Threads: T₀, T₁, T₂

Maximum Requirements

Thread	Maximum Needed
T₀	10
T₁	4
T₂	9

Currently Allocated

Thread	Allocated
T₀	5
T₁	2
T₂	2

Available Resources

Total allocated = 5 + 2 + 2 = 9
Available = 12 − 9 = 3

🔹 Step 1: Compute Remaining Need

Remaining Need = Maximum − Allocated

Thread	Need
T₀	10 − 5 = 5
T₁	4 − 2 = 2
T₂	9 − 2 = 7

Available = 3

🔹 Step 2: Check if System is Safe

We try to find a safe sequence.

Can T₁ finish?

T₁ needs 2
Available = 3
✔ Yes

So T₁ finishes and releases its 2 resources.

New Available = 3 + 2 = 5

Can T₀ finish?

T₀ needs 5
Available = 5
✔ Yes

T₀ finishes and releases its 5 resources.

New Available = 5 + 5 = 10

Can T₂ finish?

T₂ needs 7
Available = 10
✔ Yes

T₂ finishes and releases its 2 resources.

Final Available = 12

✔ Safe Sequence Found:

$<T₁, T₀, T₂>$

So the system is in a safe state at time t₀.

Important idea:

Safe means there exists at least one order in which all threads can finish.

🔹 Now Move to Time t₁

Suppose T₂ requests 1 more resource, and the system grants it.

New Allocation

T₂ now holds 3 resources.

New total allocated = 5 + 2 + 3 = 10
New available = 12 − 10 = 2

Recalculate Needs

Thread	Need
T₀	5
T₁	2
T₂	6

Available = 2

🔹 Check If System Is Safe Now

Try to find a safe sequence again.

Can T₁ finish?

T₁ needs 2
Available = 2
✔ Yes

After T₁ finishes:

Available = 2 + 2 = 4

Can T₀ finish?

T₀ needs 5
Available = 4
❌ No

Can T₂ finish?

T₂ needs 6
Available = 4
❌ No

No other thread can proceed.

So we cannot find a safe sequence.

🔴 System Is Now in an Unsafe State

Important:

It is not deadlocked yet
But no safe sequence exists
Deadlock is now possible

🔹 How Deadlock Can Occur

Suppose:

T₀ now requests its remaining 5 resources → cannot be satisfied (only 4 available)
T₂ requests its remaining 6 resources → cannot be satisfied

Now:

T₀ is waiting
T₂ is waiting
No one can proceed

Deadlock occurs.

🔹 Where Was the Mistake?

The mistake was:

Granting T₂ one additional resource when it was available.

Even though the resource was free, giving it caused the system to move from:

✔ Safe state
to
❌ Unsafe state

Deadlock avoidance would have:

Simulated granting the resource
Checked for safety
Detected unsafe state
Denied the request

🔹 Key Insight of the Example

This example teaches a very important concept:

Just because a resource is available does NOT mean it is safe to allocate it.

Deadlock avoidance algorithms:

Always check safety first
Only grant a request if the system remains safe

🔹 Why Resource Utilization May Be Lower

In avoidance:

A thread may be denied a resource
Even if the resource is currently available
Because granting it would create an unsafe state

Thus:

✔ Deadlock is avoided
❌ But resource usage may be temporarily reduced

Important Observations

Avoidance requires prior knowledge of maximum demand.
It ensures system never enters unsafe state.
It may reduce resource utilization.
It has runtime overhead.

Prevention vs Avoidance

Feature	Prevention	Avoidance
Break necessary condition?	Yes	No
Requires max demand?	No	Yes
Dynamic checking?	No	Yes
Efficiency	Often low	Better
Overhead	Low	Higher

Final Conceptual Summary

Deadlock avoidance:

Uses advance information
Checks safety before allocation
Prevents unsafe states
Does not eliminate necessary conditions
Is more flexible but computationally heavier