Deadlock Prevention In OS

 Deadlock in OS  is a situation where a group of processes become permanently blocked, waiting for each other’s resources. This can cause the entire system to freeze or slow down significantly.

Deadlocks occur when four necessary conditions are true simultaneously:

1. Mutual Exclusion – Only one process can use a resource at a time.
2. Hold and Wait – A process is holding a resource and waiting for more.
3. No Preemption – A resource cannot be forcibly taken from a process.
4. Circular Wait – A closed chain of processes exists, each waiting for a resource held by the next.

A descriptive diagram illustrating a deadlock situation and a no-deadlock situation is provided below.

 Deadlock Prevention Technique in OS

Deadlock prevention is a technique used to prevent deadlocks from occurring in OS. It works by designing the system in a way that at least one of the four conditions mentioned above is never allowed to happen. So,

“Deadlock prevention always ensures one or more of these conditions is always eliminated or removed.”

Let’s discuss how to remove or eliminate deadlock conditions in a very descriptive way

Terms used in this lecture are P1 is Process 1 P2 is Process 2 P3 is Process 3 P4 is Process 4 R1 is Resource 1 R2 is Resource 2 R3 is Resource 3 R4 is Resource 4

1. Remove Mutual Exclusion

Mutual Exclusion means a non-shareable resource can be used by only one process at a time. If another process requests the resource, it must wait until the current process releases it.

How to Remove Mutual Exclusion?

You can remove Mutual Exclusion by making resources shareable. Design the system so that multiple processes can access the resource simultaneously without conflict.

Example 01: Eliminate Mutual Exclusion

Mutual Exclusion exists when a resource (R1) is assigned to only one process at a time.

• Here, P1 is holding R1, so no other process can use it simultaneously.
• When P2 requests R1, it must wait until P1 releases it, demonstrating mutual exclusion.

Mutual Exclusion is removed when a resource can be shared by multiple processes at the same time.

• For example, if R1 is a read-only file, both P1 and P2 can access it simultaneously without conflict.
• Since P2 doesn’t need to wait for P1 to release R1, mutual exclusion does not exist in this case.

Note: Read-only files: Multiple processes can read the same file simultaneously because reading doesn’t change the data.

Example 02: Eliminate Mutual Exclusion

Mutual Exclusion exists when a one-way road (R1) is used by only one car at a time.

• If Car 1 (P1) is on the one-way road, and Car 2 (P2) approaches from the opposite direction, it must wait until the road is clear.

• This demonstrates mutual exclusion because only one car can occupy the one-way road (R1) at a time, regardless of direction.

Mutual Exclusion is removed when a wide two-way road (R1) like is used by multiple cars at the same time.

• Car 1 (P1) and Car 2 (P2) can travel in opposite directions without blocking each other.
• Since both cars can access the road simultaneously, mutual exclusion does not exist in this case.

Note: Watching TV in a lounge allows multiple people to enjoy it together, making it a shareable resource (TV lounge ) that does not require mutual exclusion.

Very Important: Mutual Exclusion is compulsory for some critical resources (like CPU, printer, or memory block). So, deadlock prevention via mutual exclusion is limited in practice. Therefore, OS designers focus more on breaking the other conditions (like hold and wait or circular wait).

2. Remove No Preemption

No Preemption means once a process acquires a resource, it cannot be forefully taken away. The process keeps the resource until it voluntarily releases it after completing its task.

How to remove No Preemption?

If a process holding some resources requests another resource that is not available, then:

• All the held resources are forcefully released.
• The process is moved back to the waiting state.
• Released resources may be reassigned to other processes when needed.

Example 01: Eliminate No Preemption 

No Preemption exists when a process keeps its held resource until it voluntarily releases it.

• Here, R1 is assigned to P1, and now P1 requests R2, which is currently unavailable (held by P2).
• Since P1 cannot be forced to release R1, P2 (or others) must wait, increasing the risk of deadlock.

No Preemption is removed when a process can be forced to release its held resources if it requests another unavailable one.

• Here, R1 is assigned to P1, and when P1 requests R2 (held by P2), the OS forcefully takes back R1 from P1 and gives it to other processes, i.e., P2 if needed.
• This allows R1 to be reassigned to other processes, thus preventing deadlock by removing the no-preemption condition.

Finally, Deadlock is removed, and P1 waits until both R1 and R2 are available.

Example 02: Eliminate No Preemption

No Preemption exists when a person keeps using a resource until they voluntarily release it.

• Person 1 (P1) is using the Printer (R1) and then requests the Scanner (R2), which is currently being used by Person 2 (P2).

• Since P1 cannot be forced to release the Printer, P2 and others must wait, increasing the risk of a deadlock.

No Preemption is removed when a person can be forced to release a resource if they request another one that’s unavailable.

• Person 1 (P1) is using the Printer (R1) and then requests the Scanner (R2), which is currently being used by Person 2 (P2) — so the Printer is taken back from P1 and possibly given to P2 (if needed).

• P1 waits until both Printer and Scanner are available, preventing deadlock by removing the no-preemption condition.

Finally, no preemption deadlock was removed

Important Points about Eliminate No Preemptive

• Not all resources can be preempted safely.
• Printer, I/O devices, or memory buffers may lose data if forcefully taken, so OS avoids preemption in such cases.

Hence, removing the No Preemption condition works only with safe-to-preempt resources, and other deadlock conditions (like circular wait) are handled for the rest.

3. Remove Hold and Wait

Hold and Wait means a process is holding at least one resource while waiting to acquire additional resources that are currently being held by other processes, leading to a deadlock.

How to Remove Hold and Wait?

You can eliminate the Hold and Wait condition by changing how resources are requested.

• A process must request all required resources at once, before execution begins.
• If all the requested resources are available, the process gets them and continues.
• If any resource is not available, the process waits without holding any resource.

This avoids the “hold while waiting” scenario entirely.

Example 01: Eliminate Hold and Wait

Hold and Wait exists when a process holds at least one resource and simultaneously waits for one or more additional resources that are currently held by other processes.

• Here, R1 is assigned to P1, and now P1 requests R2 (available) and R3 (held by P2).

• Since P1 is holding R1 and waiting for R3, this creates a hold and wait condition, which increases the risk of deadlock.

Hold and Wait is removed when a process is required to request all needed resources at once before execution begins.

• P1 requests R1, R2, and R3 together; since R3 is held by P2, the request is denied, and P1 waits without holding any resource. P1 release R1 and don’t get R2 as well until all requested resources are available.
• This eliminates the hold and wait condition because P1 doesn’t hold R1 while waiting for R3, thus helping prevent deadlock.

Finally, the hold and wait condition is eliminated, and the system becomes deadlock-free.

Example 02: Eliminate Hold and Wait 

Hold and Wait exists when a person holds at least one item and waits for additional ones that are currently held by others.

• Person1 (P1) is using the Mobile (R1) and now requests the Laptop (R2) (available) and the Car (R3), which is currently being used by Person2 (P2).

• Since P1 is holding the Mobile and waiting for the Car, this creates a hold and wait condition, which may lead to a deadlock-like situation.

Hold and Wait is removed when a person is allowed to take all required items only if all are available at once; otherwise, they must wait without holding anything.

• Person1 (P1) requests the Mobile (R1), Laptop (R2), and Car (R3) together. Since the Car (R3) is with Person2 (P2), P1 waits without holding the Mobile or Laptop.
• P1 gets executed only when all three items (R1, R2, R3) become available at the same time, thus preventing the hold and wait condition and avoiding deadlock.

Finally, Hold and Wait is removed

Example 03: Hold and Wait Scenario

• A student grabs a computer and then waits for a projector to become free before starting a presentation.
• A rule says: You can only enter the presentation room if both the computer and the projector are available. Otherwise, wait outside without holding anything.

4. Remove Circular Wait

Circular Wait means a set of processes are waiting for resources in a circular chain, where each process is waiting for a resource held by the next one in the chain.

• This forms a deadlock loop. If such a circular chain is allowed to form, deadlock is inevitable.

How to Eliminate Circular Wait?

You can eliminate the Circular Wait condition by imposing a strict ordering of all resource types.

• Assign a unique number (or priority) to each resource type.
• Processes must request resources in increasing order of those numbers.
• A process can only request a resource with a higher number than what it already holds.
• This prevents a circular chain from forming, because processes move only in one direction through the resource order.

Example 01: Eliminate Circular Wait 

Consider the following 4 processes and 4 Resources

Circular Wait exists when there is a closed chain of processes, where each process is waiting for a resource held by the next one in the cycle.

• P1 holds R1 and waits for R2 (held by P2) → P2 holds R2 and waits for R3 (held by P3) → P3 holds R3 and waits for R4 (held by P4) → P4 holds R4 and waits for R1 (held by P1).
• This forms a circular chain of dependency, where no process can proceed, resulting in a deadlock due to the circular wait condition.

Circular Wait is removed by assigning a fixed order to all resources, such as R1 < R2 < R3 < R4. Every process must request resources only in increasing order — they are not allowed to request a lower-numbered resource after holding a higher one.

In this example, P1 can request R1, then R2, but P1 cannot request R2 first and then R1. If P4 is holding R4, it cannot request R1, because that would be going against the order.

Finally, the Circular Wait deadlock is removed

Real Life Example 02:  Eliminate Circular Wait 

Consider four cars on a two-way road that are approaching from opposite directions; a deadlock may occur. A critical section is the area where cars can create a deadlock for each other.

We can represent in a table as

Circular Wait → DEADLOCK!

Look at the following diagram, where a deadlock occurs

According to the circular wait elimination rule, P4 with R4 can’t request to R1. So, P4 release R4 and get it later when both R1 and R4 are available. So, finally deadlock of circular wait is removed.

Circular Wait Broken → Deadlock Impossible

How is Car 4 (P4) Executed? Request resources in number order, regardless of path. Even if P4 needs R4 first and then R1, but We tell it to acquire: R1 first, THEN R4. Car The resources it needs Order Required Car1 R1 → R2  Already in increasing order R1 → R2 Car2 R2 → R3 Already in increasing order R2 → R3 Car3 R3 → R4 Already in increasing order R3 → R4 Car4 R4 → R1 Request R1 first → then R4. So, R1 → R4 (increasing Order)

Deadlock Prevention vs. Deadlock Avoidance