Deadlock in OS

A deadlock in an operating system (OS) is a situation where a group of processes become stuck, each waiting for a resource held by another process. As a result, no process can proceed, and all system operations are blocked. Deadlocks are a serious issue in multitasking and multiprocessing environments.

Important: A Deadlock happens because of improper resource allocation and scheduling, where processes hold resources and wait for other resources held by other processes.

In this article, we will explain the following diagram

Deadlock Real Life Examples

Real-life examples of deadlock in OS, explained in simple terms, are given below

Example 1. One-Way Road (Traffic Deadlock)

Example: Consider a one-way road with two cars coming from opposite directions. Both cars stop in front of each other, waiting for the other to back up. In terms of OS

• Cars = Processes
• Road = Resource

Each process holds the road and waits for the other → Deadlock.

Example 2. Printer and Scanner

• Process A is using the printer and wants the scanner.
• Process B is using the scanner and wants the printer.
• Both are waiting for each other’s device.

In terms of OS

• Process A & B = Processes
• Printer & Scanner = Resources
• Circular waiting occurs → Deadlock.

Types of Resources in OS

A resource is anything that a process needs to complete its task. There are two major types of resources in OS

• Physical Resources: Tangible hardware or real components
• Logical Resources: Abstract or software-related components

Some common examples of resources are given below

Deadlock Conditions

A deadlock can occur only when all four of the following conditions are true at the same time. These are known as the Coffman Conditions.

Note: If even one condition is false, deadlock cannot happen.

1. Mutual Exclusion 

Mutual Exclusion means that a resource cannot be used by more than one process (p) at the same time. If one process is using it, others must wait until it’s released. It ensures that critical resources are not shared simultaneously, preventing conflicts or data corruption.

Example: Two cars are coming from opposite directions to cross a narrow one-lane bridge at a time. where

• Two cars are two processes
• and one-lane bridge is a recource

Mutual exclusion deadlock happens because bridge is a non-shareable resource, and both processes (cars) compete for it at the same time. Since only one can cross at a time, and neither can proceed nor release, deadlock occurs.

2. No Preemption

No preemption means that once a resource is assigned to a process, it cannot be taken away forcefully from that process. The process must willingly release that resource after completing its task.

Example 01: Person A has rented a car and is using it. Person B also needs that car. But the rental agency cannot take the car away from Person A until they return it. The car (resource) stays with the user until they willingly give it back.

Example 02: A person is editing a document on their computer. Another user wants to edit the same file, but can’t access it until the first person saves and closes it. You can’t forcefully take the file while it’s in use — you must wait for the user to finish.

3. Hold And Wait

Hold and Wait means that a process is holding at least one resource and at the same time is waiting to acquire additional resources that are currently being used by other processes.

The process does not release the resource it already holds, even though it can’t proceed without the one it’s waiting for.

Different scenarios of hold and wait deadlock are given below 

Example 01: Phone Charger and Laptop Charger

Person 1 is using a phone charger and needs a laptop charger to charge their laptop. At the same time, Person 2 is using the laptop charger and needs the phone charger.  Both people are holding one charger and waiting for the other one, without releasing the one they already have.

Case	P1 Holding	P1 Waiting	P2 Holding	P2 Waiting	Hold and wait, Deadlock?
1	Laptop charger	Phone charger	Phone charger	–	Yes
2	Laptop charger	–	Phone charger	Laptop charger	Yes
3	Laptop charger	Phone charger	Phone charger	Laptop charger	Yes

Example 02: Printer and Scanner

A person is using the printer and now wants to scan a document using the scanner. However, the scanner is already being used by someone else. The person keeps holding the printer and waits for the scanner to become available.  They are holding one resource (printer) and waiting for another (scanner).

4. Circular Wait

Circular Wait occurs when a group of processes are each waiting for a resource that is held by the next process in the chain, eventually forming a closed loop. This circular chain of waiting prevents all processes from proceeding, causing a deadlock.

Example 01: Four Cars at a Four-Way Intersection

• Car A wants to go forward but is blocked by Car B.
• Car B wants to go forward but is blocked by Car C.
• Car C is blocked by Car D.
• Car D is waiting for Car A to move.

 A → B → C → D → A

All four cars are waiting for each other in a loop, and none can move forward — Circular Wait occurs.

Why Deadlock Prevention Necessary?

Deadlock prevention is necessary because deadlocks can freeze system processes, waste resources, and disrupt critical tasks. Preventing deadlock ensures the system remains efficient, stable, and responsive. The following problems can happen If We Don’t Prevent Deadlock.

• Processes get stuck forever
• Resources are locked and wasted
• System performance drops
• In real-time systems (like banking, critical patient treatment, air traffic control), it can cause failure or disaster

There are four main strategies to handle deadlocks:

1. Deadlock Prevention

In deadlock prevention in OS, the system is designed in such a way that it violates (breaks) even one of the four necessary conditions for deadlock, then Deadlock cannot occur.

• If Mutual Exclusion is violated (break), it means allowing resources to be shared.
• If Hold and Wait is violated (break), require all resources to be requested at once.
• If No Preemption is violated (break), allow the system to take back a resource if needed.
• If Circular Wait is violated (break), apply a fixed ordering of resource requests.

So,

• Deadlock = All 4 conditions must exist
• Break any 1 condition = Deadlock is impossible

I. Violate Mutual Exclusion

Mutual Exclusion can be violated, but only in some special cases.

Mutual Exclusion means that a resource cannot be shared; only one process can use it at a time. To prevent deadlock, one idea is to violate (i.e., avoid using) mutual exclusion, so multiple processes can access the resource simultaneously.

Case 01:  When Mutual Exclusion cannot be violated

Many resources must be used by only one process at a time, for safety and correctness. For example:

• A printer must not be shared while printing.
• If someone is writing to a file, others should not use it.

In these cases, mutual exclusion cannot be violated.

Case 02: When Mutual Exclusion is Violated

In some cases, you can violate mutual exclusion safely; these resources are called shareable resources.

Examples of Shareable Resources:

• Read-only files: Many processes can read the same file without conflict.
• Static web pages: Can be accessed by many users at once.
• Media streaming: Multiple users can stream the same video.

So, if all resources in a system are shareable, mutual exclusion is not needed, and deadlock is impossible.

 Note:  Mutual Exclusion can be violated for shareable resources. But it cannot be violated for non-shareable (exclusive) resources

II. Violate Hold and Wait

Violate hold and wait is a common strategy to avoid deadlock. To prevent Hold and Wait, the system can be designed so that:

• A process must request all required resources at once, before starting execution.
• If any resource is not available, the process releases everything and waits until all are free.

Example:

A process needs a printer and a scanner:

• Instead of getting the printer first and waiting for the scanner,
• It must request both at the same time.
• If either is not available, it waits without holding any.

Benefits:

• Prevents deadlock by ensuring no process holds one resource while waiting for another.

Drawbacks:

• Low resource utilization: Some processes may wait even if some resources are free.
• Can cause starvation (long wait times) if many processes request all resources together.

III. Violate No Preemption

Violating No Preemption is a valid way to prevent deadlock. To prevent deadlock, the system can be designed so that:

 If a process holding a resource is waiting for another one, the system forcibly takes back the resource it holds and puts the process back in the waiting queue.

This allows other processes to use the released resource.

Example:

• Process A holds the printer and requests the scanner.
• The scanner is busy, so the system takes the printer back from A.
• Now Process B can use the printer.

Benefits:

• Helps break circular wait, since no process can hold one resource and wait for another indefinitely.
• Keeps resources available to others when not fully usable.

Drawbacks:

• Not always possible (e.g., can’t partially take back a printing job or a real-time hardware lock).
• May lead to process rollback or loss of progress.

IV. Violate Circular Wait

Violating the Circular Wait is a widely used technique to make systems deadlock-free. To prevent deadlock, the system can be designed to prevent circular waiting by:

Imposing a strict ordering on resource allocation.

How it Works:

• Assign a numerical order to all resources (e.g., Printer = 1, Scanner = 2, Disk = 3).
• A process must request resources in increasing order only.
• If a process holds resource 2, it can’t request resource 1.

Example:

• Process A holds resource 1 and wants resource 2 → Allowed
• Process B holds resource 2 and wants resource 1 → Not allowed → Cycle is avoided

Benefits:

• Simple to implement with resource numbering.
• Guarantees no circular chain of waiting.

Drawbacks:

• May limit flexibility in how processes request resources.
• Requires developers to carefully plan resource request sequences.

2. Deadlock Avoidance in OS

Deadlock Avoidance is a technique used by the operating system to ensure that a system never enters a deadlock state. It requires the system to make safe decisions about resource allocation, only allowing requests if they don’t lead to a deadlock in the future.

The OS checks each resource request:

• If granting it keeps the system in a safe state, it proceeds.
• If granting it leads to an unsafe state, the request is denied or delayed.

Common Deadlock Avoidance Algorithm is the Banker’s Algorithm (by Dijkstra). It simulates the future and only allocates if it finds a safe sequence.

Deadlock Prevention = structurally eliminate one of the four conditions
Deadlock Avoidance = dynamically check and allow only safe allocations

3. Deadlock Detection and Recovery

Unlike deadlock prevention or avoidance, where the goal is to stop deadlock from happening, deadlock detection and recovery allow the system to enter a deadlock state, detects it when it occurs, and then recover from it.

Deadlock detection and recovery is suitable for systems where deadlock is rare but possible.It is also used when deadlock prevention or avoidance is too restrictive or costly 

Let discuss deadlock detection and recovery methods

I. Deadlock Detection Methods

Here are some common methods to detect a deadlock 

 a. Resource Allocation Graph (RAG) – Single Instance per Resource

• Processes and resources are modeled as a graph.
• If a cycle exists in the graph → deadlock has occurred.

b. Wait-for Graph – Multiple Instances

• Derived from RAG by removing resource nodes.
• If a cycle exists → deadlock detected.

c. Deadlock Detection Algorithm – Banker’s Style

Uses data structures like:

• Available[] (resources free)
• Allocation[][] (resources assigned)
• Request[][] (resources requested)

II. Deadlock Recovery

Once deadlock is detected, the OS must recover using one of the following strategies:

a. Process Termination

• Kill one or more processes in the deadlock cycle.

• Options:

  • Terminate all involved processes (brute-force but effective)
  • Terminate one at a time until deadlock breaks (less costly)

b. Resource Preemption

• Temporarily take resources away from some processes.
• Preempted process may be rolled back and restarted later.

4. Deadlock Ignorance

In deadlock ignorance, we assume deadlocks are rare. We do nothing. This is called the Ostrich policy and is used in many general-purpose OS like Windows and Linux.

Deadlock Vs. Starvation in OS Comparison

FAQ: Deadlock in OS

Q1. What causes a deadlock in an OS?
Answer: It happens when multiple processes wait for resources in a circular chain with no preemption allowed.

Q2. Can deadlock be completely avoided?
Answer: Not always. Systems must strike a balance between efficiency and safety.

Q3. What is the best method for deadlock handling?
Answer: It depends on the system. Real-time systems prefer prevention; general OS may use detection or ignore it.