Deadlockhandling

12 min read2,362 words

Deadlock Handling

Deadlock handling means the techniques used by an operating system to prevent, avoid, detect, and recover from deadlocks.

You already learned what a deadlock is. Now we focus specifically on:

Deadlock Handling | +---------------+---------------+ | | | ↓ ↓ ↓ Prevention Avoidance Detection | ↓ Recovery

1. Why Deadlock Handling Is Needed

Consider:

P1 holds R1 → waits for R2 P2 holds R2 → waits for R1

Now:

P1 ───── waits for ─────→ R2 ↑ │ │ ↓ R1 ←──── held by ─────── P2

Neither process can continue.

The OS therefore needs a strategy for dealing with such situations.

2. Four Main Deadlock Handling Strategies

There are four major approaches:

1. Deadlock Prevention

Make deadlock impossible by breaking one necessary condition.

2. Deadlock Avoidance

Carefully allocate resources so the system stays in a safe state.

3. Deadlock Detection and Recovery

Allow deadlocks to occur, detect them, and recover.

4. Ignore the Problem

Some general-purpose systems may not continuously perform expensive deadlock handling for every possible resource situation. Instead, certain applications or resource managers handle the issue themselves.

3. Deadlock Prevention

The idea is:

Prevent at least one of the four necessary conditions for deadlock.

The four conditions are:

1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait

If any one is permanently prevented, the classical deadlock cannot occur.

4. Prevention of Mutual Exclusion

Deadlock requires at least one non-shareable resource.

So, where possible, make resources shareable.

For example:

Shared Read-only File ↑ P1 + P2 + P3

Multiple processes can read the same data simultaneously.

However, some resources inherently cannot be shared safely.

For example:

Physical Printer

Two processes cannot safely control a printer's output simultaneously without coordination.

So this method has limitations.

5. Prevention of Hold and Wait

A process should not hold one resource while waiting for another.

One approach is:

Require a process to request all resources it needs before beginning execution.

Example:

P1 needs: R1 + R2 + R3 ↓ Request all three ↓ If all available: Allocate ↓ Execute ↓ Release

Problem

Suppose P1 needs:

R1 + R2

but only R1 is currently available.

Instead of taking R1 and waiting for R2, P1 waits without holding R1.

Disadvantages

  • Resources may remain unused.
  • A process may not know all required resources in advance.
  • Processes may hold resources longer than necessary.

6. Prevention of No Preemption

The third condition is:

No Preemption

To prevent it, the OS may allow resources to be taken away from a process under suitable circumstances.

Example:

P1 holds R1 P1 requests R2 R2 unavailable ↓ OS may preempt/release R1 ↓ P1 waits

Later:

P1 gets R1 + R2 ↓ Continues

Important limitation

This works only for resources where preemption is meaningful and safe.

For example:

CPU → can be preempted Memory pages → can often be moved/swapped

But:

Printer operation → cannot always be safely preempted

7. Prevention of Circular Wait

This is one of the most practical methods.

Assign an order to resources.

Example:

R1 < R2 < R3 < R4

Require every process to request resources in increasing order.

Allowed:

P1: R1 → R2 → R3

Not allowed:

P2: R3 → R1

because it violates the resource ordering.

Why Does This Prevent Deadlock?

Suppose:

P1 holds R1 → requests R2 P2 holds R2 → requests R1

This creates:

P1 → R2 ↑ ↓ R1 ← P2

But if every process must request resources in increasing order:

R1 < R2

P2 cannot hold R2 and then request R1.

Therefore the circular wait cannot form.

8. Deadlock Prevention Summary

ConditionPrevention Method
Mutual ExclusionMake resources shareable where possible
Hold and WaitRequest all resources together
No PreemptionAllow resource preemption where possible
Circular WaitImpose resource ordering

Memory trick:

Break M-H-N-C

9. Deadlock Avoidance

Prevention is relatively strict.

Avoidance is more dynamic.

The OS examines each resource request and asks:

"If I give this resource to the process, will the system remain safe?"

Process requests resource ↓ Safety check ↓ +---+---+ | | Safe Unsafe | | ↓ ↓ Grant Wait

10. Safe State

A system is in a safe state if there is some order in which all processes can obtain the resources they still need and eventually finish.

Example:

Safe Sequence: P2 → P1 → P3 → P4

This means:

P2 finishes ↓ Releases resources ↓ P1 finishes ↓ Releases resources ↓ P3 finishes ↓ P4 finishes

11. Unsafe State

An unsafe state means the OS cannot guarantee that all processes can finish safely based on the current allocation information.

Important:

Unsafe does not necessarily mean deadlocked.

Safe ↓ No guaranteed deadlock Unsafe ↓ Deadlock may become possible

12. Banker's Algorithm

The most famous deadlock avoidance algorithm is:

Banker's Algorithm

It determines whether granting a request keeps the system in a safe state.

The main data structures are:

Available

Resources currently available.

Maximum

Maximum resources each process may need.

Allocation

Resources currently allocated to each process.

Need

Remaining resources required.

Formula:

Need = Max − Allocation

13. Banker's Algorithm Example

Suppose:

Available = 3

Processes require:

P1 → Need 4 P2 → Need 2 P3 → Need 1

The OS checks which process can finish with the currently available resources.

P3 needs 1:

1 ≤ 3

So P3 can potentially finish.

After P3 finishes, it releases its allocated resources.

Suppose it releases 2:

Available = 3 + 2 = 5

Now:

P1 → Need 4 ≤ 5

So P1 can finish too.

This continues until the OS finds a safe sequence.

14. Banker's Algorithm Steps

Conceptually:

1. Find a process whose Need ≤ Available 2. Assume it finishes 3. Add its allocated resources back: Available = Available + Allocation 4. Mark that process finished 5. Repeat 6. If all processes can finish: SAFE Otherwise: UNSAFE

15. Deadlock Detection

Another strategy is:

Allow deadlocks to occur, then detect them.

The system periodically or when appropriate checks whether processes are stuck in a deadlock.

Processes ↓ Resource allocation ↓ Possible deadlock ↓ Detection algorithm ↓ Deadlock? / \ No Yes ↓ ↓ Continue Recovery

16. Deadlock Detection for Single Resource Instance

If every resource type has only one instance, a resource-allocation graph can be used.

Example:

P1 → R2 R2 → P2 P2 → R1 R1 → P1

There is a cycle:

P1 → R2 → P2 → R1 → P1

With one instance per resource type, such a cycle indicates deadlock.

17. Detection with Multiple Resource Instances

When resources have multiple instances, a cycle alone is not enough.

For example:

Resource R1 ↓ 3 instances

Several processes may hold or request different instances.

In such cases, the OS uses a detection algorithm based on information similar to:

  • Available
  • Allocation
  • Request

The algorithm tries to determine whether the remaining requests can be satisfied in some completion sequence.

18. Deadlock Recovery

After detecting a deadlock, the OS must recover.

The major methods are:

Deadlock Detected | +── Terminate Process | +── Resource Preemption | +── Rollback

19. Recovery Method 1 — Process Termination

The OS can terminate one or more processes involved in the deadlock.

Example:

P1 ↔ P2 ↔ P3

Terminate P2:

P1 P3 \ / Resources ↑ Released from P2

Once P2 releases its resources, other processes may continue.

20. Which Process Should Be Terminated?

The OS should consider factors such as:

  • Process priority
  • How long the process has executed
  • How many resources it holds
  • How many resources it still needs
  • Cost of restarting it
  • Importance of its work
  • Number of processes that must be terminated

The goal is to recover with minimal cost.

21. Recovery Method 2 — Resource Preemption

The OS can take a resource from one process and give it to another.

Example:

P1 owns R1 P2 needs R1 ↓ OS preempts R1 from P1 ↓ P2 gets R1

However, this creates additional problems:

  • Which process should lose the resource?
  • How should it be rolled back?
  • How do we prevent starvation?

22. Recovery Method 3 — Rollback

The OS can return a process to an earlier safe state.

Process state Checkpoint 1 ↓ Checkpoint 2 ↓ Current state ↓ Deadlock ↓ Rollback ↓ Checkpoint 2

The process can then restart from the earlier checkpoint.

This is especially useful when applications support checkpointing.

23. Starvation During Recovery

Suppose the same process repeatedly loses resources:

P1 ↓ Resource taken ↓ P1 restarts ↓ Resource taken again ↓ P1 restarts ↓ ...

P1 may never finish.

This creates starvation.

Therefore, recovery mechanisms must consider fairness.

24. Prevention vs Avoidance vs Detection

This comparison is extremely important.

FeaturePreventionAvoidanceDetection
Basic ideaMake deadlock impossibleStay in safe statesFind deadlock after it occurs
TimingBefore allocationAt every relevant allocation decisionAfter/periodically
ApproachRestrictiveDynamicReactive
Uses safe-state check?Not necessarilyYesNo
ExampleResource orderingBanker's AlgorithmDetection algorithm
Recovery needed?NoUsually noYes

25. Prevention vs Avoidance

These two are often confused.

Prevention

The OS says:

"I will structure resource allocation so at least one deadlock condition cannot happen."

Example:

Always request: R1 → R2 → R3

Avoidance

The OS says:

"I will examine each request and grant it only if the resulting state remains safe."

Example:

Request ↓ Safety Check ↓ Safe? → Grant Unsafe? → Wait

26. Deadlock Handling in Real Systems

Different systems use different strategies.

A system may combine:

Lock ordering + Timeouts + Detection + Recovery

For example, database systems often use deadlock detection and then abort/rollback one transaction.

27. Deadlock vs Starvation vs Livelock

Very important comparison:

DeadlockStarvationLivelock
Processes are blockedProcess keeps waitingProcesses are active
Processes may wait for each otherOther processes keep getting resourcesProcesses repeatedly react
No useful progressSome processes may continueNo useful progress
Circular wait may existCircular wait not requiredCircular wait not required

Easy memory:

Deadlock → Stuck Starvation → Ignored Livelock → Moving but not progressing

28. Practical Deadlock Prevention: Lock Ordering

Consider:

Thread A: Lock A Lock B Thread B: Lock B Lock A

Potential deadlock:

Thread A → holds A → waits B Thread B → holds B → waits A

Better:

Always acquire: Lock A → Lock B

Then:

Thread A: A → B Thread B: A → B

Circular wait is prevented.

This is a common practical synchronization technique.

29. Timeout-Based Handling

Some applications use a timeout.

Example:

Process requests lock ↓ Wait for limited time ↓ Lock acquired? / \ Yes No ↓ ↓ Continue Abort/retry

A timeout can help avoid waiting forever, although it does not mathematically eliminate every possible deadlock situation.

30. Complete Deadlock Handling Diagram

Deadlock | ↓ Deadlock Handling | +-------------+-------------+ | | | ↓ ↓ ↓ Prevention Avoidance Detection | | | ↓ ↓ ↓ Break one of Safe-state Detect cycle/ 4 conditions check unsafe state | | | ↓ | Recovery | | | +------+------+ | | | | | ↓ ↓ ↓ | Terminate Preempt Rollback | ↓ Banker's Algorithm

31. Exam-Oriented Short Notes

Deadlock Prevention

Prevents deadlock by ensuring that at least one of the four necessary conditions—mutual exclusion, hold and wait, no preemption, or circular wait—cannot hold.

Deadlock Avoidance

Dynamically allocates resources only when doing so keeps the system in a safe state.

Banker's Algorithm

A deadlock-avoidance algorithm that checks whether a resource allocation can leave the system in a safe state.

Deadlock Detection

Allows resource allocation to proceed and periodically or when appropriate checks whether a deadlock exists.

Deadlock Recovery

The process of restoring the system after detecting deadlock, using methods such as process termination, resource preemption, or rollback.

🧠 Final Revision

Remember:

DEADLOCK HANDLING | +------------+------------+ | | | ↓ ↓ ↓ PREVENTION AVOIDANCE DETECTION | | | ↓ ↓ ↓ Break one Safe state Find deadlock condition checking | | ↓ ↓ RECOVERY Banker's / | \ Algorithm Kill Preempt Rollback

The most important things to remember:

  1. Prevention → break at least one deadlock condition.
  2. Avoidance → never enter an unsafe state.
  3. Banker's Algorithm → classic deadlock-avoidance algorithm.
  4. Detection → find deadlock after it can occur.
  5. Recovery → terminate, preempt, or rollback.
  6. Resource ordering → practical way to prevent circular wait.
  7. Safe state ≠ deadlock.
  8. Unsafe state ≠ necessarily deadlock, but deadlock may become possible.
  9. Deadlock = stuck, starvation = continuously waiting, livelock = active but no progress.

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy