Deadlocks

13 min read2,585 words

Deadlocks

What is a Deadlock?

A deadlock is a situation in an operating system where two or more processes are permanently blocked because each process is waiting for a resource held by another process.

Deadlock = Processes waiting for each other forever.

Simple example

Suppose:

Process P1 has Resource R1 Process P2 has Resource R2

Now:

P1 → waiting for R2 P2 → waiting for R1

Neither can continue.

R1 ↑ │ P2 │ ↓ R2 ↑ │ P1

So:

P1 waits for P2 P2 waits for P1

This is a deadlock.

1. Real-Life Example

Imagine two people:

Person A has Pen Person B has Paper

Person A says:

"Give me the paper; I won't release the pen."

Person B says:

"Give me the pen; I won't release the paper."

Person A │ │ wants Paper ↓ Person B Person B │ │ wants Pen ↓ Person A

Both wait forever.

That is similar to a process deadlock.

2. Operating System Example

Suppose there are two resources:

R1 = Printer R2 = Scanner

And two processes:

P1 needs Printer + Scanner P2 needs Scanner + Printer

Execution:

P1 → gets Printer P2 → gets Scanner

Then:

P1 → waits for Scanner P2 → waits for Printer

Result:

P1 ─────waits────→ Scanner ↑ │ │ ↓ Printer ←────waits── P2

Neither process can proceed.

3. Resource

A resource is anything a process needs to perform its work.

Examples:

  • CPU
  • Memory
  • Printer
  • Scanner
  • Files
  • Database locks
  • I/O devices
  • Network resources
  • Mutex/locks
  • Semaphores

Resources can be:

Reusable Resources

Resources that can be reused after being released.

Examples:

Printer CPU Memory Mutex

Consumable Resources

Resources that are produced and consumed.

Examples can include:

Messages Signals Certain communication buffers

Deadlock discussions in classical OS theory commonly focus on reusable resources.

4. Resource Allocation

A process usually follows:

Request ↓ Allocate ↓ Use ↓ Release

For example:

Process P1 ↓ Request Printer ↓ Printer allocated ↓ Use Printer ↓ Release Printer

Deadlock can occur when processes hold some resources while waiting for others.

5. Resource Allocation Graph

A Resource Allocation Graph (RAG) is used to represent relationships between processes and resources.

There are two types of nodes:

Process

Represented as:

(P1)

Resource

Represented as:

[R1]

6. Two Important Types of Edges

Request Edge

A process is requesting a resource.

P1 ─────→ R1

Meaning:

P1 is waiting for R1.

Assignment Edge

A resource has been allocated to a process.

R1 ─────→ P1

Meaning:

R1 is currently allocated to P1.

7. Resource Allocation Graph Example

Suppose:

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

Graph:

[R1] ─────→ (P1) │ ↓ [R2] │ ↓ (P2) │ ↓ [R1]

There is a cycle:

P1 → R2 → P2 → R1 → P1

This indicates a possible deadlock.

For the special case where every resource type has exactly one instance, a cycle in the resource-allocation graph indicates deadlock.

With multiple instances of resource types, a cycle alone does not necessarily prove deadlock.

8. Four Necessary Conditions for Deadlock

This is one of the most important OS exam topics.

A deadlock can occur only if all four of these conditions hold simultaneously:

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

Memory trick:

M H N C

Or:

"Mutual Hold, No Circular"

Let's understand each.

9. Condition 1 — Mutual Exclusion

At least one resource must be non-shareable.

Only one process can use it at a time.

Example:

Printer ↓ P1 is using it

P2 cannot use the same exclusive resource simultaneously.

P1 → Printer ← P2

But only one can get it.

10. Condition 2 — Hold and Wait

A process is holding at least one resource while waiting for another resource.

Example:

P1 | ├── Holds R1 | └── Waiting for R2

This is:

Hold and Wait

11. Condition 3 — No Preemption

A resource cannot simply be forcibly taken away from a process.

Example:

P1 → owns R1

The OS cannot arbitrarily take R1 away while P1 is using it.

P1 must normally release it voluntarily.

12. Condition 4 — Circular Wait

There must be a circular chain of processes waiting for resources.

Example:

P1 → R2 → P2 → R3 → P3 → R1 → P1

Or simply:

P1 waits for P2 P2 waits for P3 P3 waits for P1

This creates a cycle.

13. The Four Conditions Together

A deadlock requires:

DEADLOCK | +-----------+-----------+ ↓ ↓ ↓ Mutual Hold & No Exclusion Wait Preemption | ↓ Circular Wait

If any one of the four conditions is prevented, deadlock can be prevented.

This is the basic idea behind deadlock prevention.

14. Deadlock vs Starvation

These are different.

Deadlock

Processes are stuck waiting for each other.

P1 → waits for P2 P2 → waits for P1

Neither progresses.

Starvation

A process waits for a very long time because other processes keep getting resources/CPU.

P1 → waiting P2 → gets resource P3 → gets resource P4 → gets resource P5 → gets resource ... P1 → still waiting

Difference

DeadlockStarvation
Processes may wait for each otherOne process may continuously lose access
No involved process can make progressOther processes may continue
Circular waiting can existCircular waiting is not required
System can become stuckSystem may continue operating

15. Deadlock vs Livelock

Another important concept is livelock.

Deadlock

Processes don't make progress and remain blocked.

P1 → waiting P2 → waiting

Livelock

Processes keep changing their state/responding to each other but still don't make useful progress.

Example:

P1 → moves aside P2 → moves aside P1 → moves back P2 → moves back ...

They are active but not progressing.

16. Deadlock Handling

Operating systems can deal with deadlocks using several approaches.

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

The main approaches are:

  1. Deadlock Prevention
  2. Deadlock Avoidance
  3. Deadlock Detection and Recovery
  4. Ignoring the problem in some systems/workloads

17. Deadlock Prevention

Deadlock prevention ensures that at least one of the four necessary conditions can never hold.

Deadlock ↓ Break one necessary condition ↓ Deadlock cannot occur

Prevent Mutual Exclusion

Make resources shareable where possible.

For example, some data can be shared by multiple processes.

However, this isn't possible for inherently exclusive resources such as certain device operations.

Prevent Hold and Wait

Require a process to request all resources before it starts.

P1 ↓ Request R1 + R2 ↓ Gets both ↓ Execute ↓ Release

Problem:

Resources may remain unused while the process waits.

Prevent No Preemption

Allow resources to be taken back under suitable conditions.

For example:

P1 holds R1 P1 requests R2 R2 unavailable ↓ System may release/preempt resources held by P1

This approach isn't practical for every resource.

Prevent Circular Wait

Assign an ordering to resources.

Example:

R1 < R2 < R3 < R4

Require processes to request resources only in increasing order.

Then:

P1: R1 → R2 P2: R2 → R3

but a process cannot request:

R3 → R1

This prevents circular dependencies.

18. Deadlock Avoidance

Deadlock avoidance doesn't simply forbid a condition permanently.

Instead, the OS examines resource requests and asks:

If I grant this request, will the system remain in a safe state?

If yes:

Grant request

If no:

Delay request

The most famous deadlock-avoidance algorithm is:

Banker's Algorithm

19. Safe State

A system is in a safe state if there is at least one sequence in which all processes can obtain their required resources and complete.

Example:

Safe sequence: P2 → P1 → P3 → P4

This means the system can schedule/resource-allocate processes in an order that allows all of them to finish.

20. Unsafe State

An unsafe state means the system cannot guarantee that all processes can complete without deadlock.

Important:

Unsafe state does not necessarily mean deadlock has already occurred.

It means deadlock could become possible depending on future requests.

Safe State ↓ Requests granted safely ↓ Safe State Unsafe State ↓ Deadlock may become possible

21. Banker's Algorithm

The Banker's Algorithm is a classic deadlock-avoidance algorithm.

It is called "Banker's" because it resembles a bank deciding whether it can safely grant a customer's loan without running out of resources needed to satisfy everyone.

The OS considers:

  • Available resources
  • Resources currently allocated
  • Maximum resource needs
  • Remaining needs

22. Banker's Algorithm Data

Typically, we use:

Available

Resources currently available.

Max

Maximum resources each process may need.

Allocation

Resources currently allocated to each process.

Need

Remaining resources required.

Formula:

Need = Max − Allocation

Example:

ProcessMaxAllocationNeed
P1734
P2523

The system checks whether processes can finish in some safe order.

23. Simple Banker's Example

Suppose:

Available = 3

Processes need:

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

P3 can finish because:

1 ≤ 3

After P3 finishes, it releases its resources.

Suppose it releases 2:

Available = 3 + 2 = 5

Now P1 and P2 may become executable.

The OS searches for a:

Safe sequence

24. Deadlock Detection

Another approach is to allow deadlocks to occur and detect them.

Processes run ↓ Deadlock may occur ↓ Detection algorithm ↓ Deadlock found?

If a deadlock is detected:

Yes ↓ Recovery

25. Deadlock Recovery

Once a deadlock is detected, the OS needs to recover.

Common approaches include:

1. Terminate Processes

Terminate one or more processes involved in the deadlock.

P1 ↔ P2 ↔ P3 ↓ Terminate P2 ↓ Resources released ↓ Others continue

2. Resource Preemption

Take resources away from some processes and give them to others, when the resource and application semantics permit it.

P1 owns R1 ↓ Preempt R1 ↓ Give R1 to another process

This is not possible for every resource.

3. Rollback

Return a process to an earlier safe state/checkpoint and restart it later.

Current state ↓ Rollback ↓ Previous safe state

26. Deadlock Detection vs Prevention vs Avoidance

PreventionAvoidanceDetection
Stops deadlock conditions from formingMakes allocation decisions to stay safeAllows possibility of deadlock
Breaks at least one necessary conditionChecks safe/unsafe stateSearches for deadlock
ConservativeDynamicReactive
Example: resource orderingBanker's AlgorithmDetection algorithm
Deadlock preventedDeadlock avoided if assumptions holdRecovery required if detected

27. Deadlock Recovery Comparison

MethodIdea
Process terminationStop one or more processes
Resource preemptionTake resources from processes
RollbackReturn process to earlier state
RestartRestart selected process/processes

28. Resource Ordering

Resource ordering is a very useful practical technique.

Suppose:

R1 < R2 < R3

Processes must request resources in that order.

Allowed:

P1: R1 → R2 P2: R2 → R3 P3: R1 → R3

Not allowed:

P1: R2 → R1

because it violates the ordering.

This prevents circular wait.

29. Practical Programming Example

Suppose two threads/processes use two locks.

Thread 1

Lock A Lock B

Thread 2

Lock B Lock A

Possible situation:

Thread 1 → holds A → waits for B Thread 2 → holds B → waits for A

Deadlock!

A common solution is to establish a consistent lock order:

Always acquire: A → B

Then both threads follow:

Thread 1: A → B Thread 2: A → B

This avoids the circular wait.

30. Deadlock Example with Database Locks

Imagine:

Transaction T1 ↓ Locks Account A ↓ Waiting for Account B

Meanwhile:

Transaction T2 ↓ Locks Account B ↓ Waiting for Account A

Result:

T1 ──waits──→ B ↑ │ │ ↓ A ←──waits── T2

This is a classic resource deadlock.

31. Important Deadlock Terms

TermMeaning
DeadlockProcesses permanently wait for resources
ResourceSomething required by a process
Mutual ExclusionResource can be used by only one process at a time
Hold and WaitProcess holds one resource while waiting for another
No PreemptionResource cannot be forcibly taken
Circular WaitProcesses form a circular waiting chain
Safe StateSystem can find a safe completion sequence
Unsafe StateSystem cannot guarantee safe completion
StarvationProcess waits indefinitely because others are favored
LivelockProcesses remain active but make no useful progress
Banker's AlgorithmDeadlock avoidance algorithm

32. Most Important Diagram

Remember this:

DEADLOCK | +---------------+---------------+ | | | ↓ ↓ ↓ Mutual Exclusion Hold & Wait No Preemption | | | +---------------+---------------+ | ↓ Circular Wait | ↓ DEADLOCK

All four conditions must be present for the classical deadlock situation.

Break any one:

Break one condition ↓ No deadlock

33. Deadlock Complete Flow

Processes | ↓ Request Resources | ↓ Resources Allocated | ↓ Process Holds Resources | ↓ Requests More Resources | ↓ +----------+----------+ | | Safe Unsafe | | ↓ ↓ Continue Deadlock possible | ↓ Detection | ↓ Recovery

🧠 Quick Revision

Four necessary conditions:

M H N C

M → Mutual Exclusion H → Hold and Wait N → No Preemption C → Circular Wait

Three main approaches:

Prevention ↓ Break one condition Avoidance ↓ Stay in safe state ↓ Banker's Algorithm Detection + Recovery ↓ Detect deadlock ↓ Recover

Most important exam definitions

Deadlock:

A deadlock is a condition in which a set of processes are permanently blocked because each process is waiting for a resource held by another process in the set.

Deadlock Prevention:

A technique that prevents deadlock by ensuring that at least one of the four necessary conditions for deadlock cannot hold.

Deadlock Avoidance:

A technique in which the operating system dynamically examines resource allocation requests and grants them only when the system remains in a safe state.

Banker's Algorithm:

A deadlock-avoidance algorithm that checks whether granting a resource request leaves the system in a safe state.

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy