Deadlock in Operating System: What is, Circular Wait (Examples)

What is Deadlock?

Deadlock is a situation that occurs in an operating system when a process enters a waiting state because another waiting process is holding the demanded resource. Deadlock is a common problem in multiprocessing, where several processes share a specific type of mutually exclusive resource known as a soft lock or software lock.

When a deadlock occurs, none of the involved processes can continue, so the affected work stops until the operating system intervenes.

Example of Deadlock

• A real-world example would be traffic that is going in only one direction.
• Here, a bridge is considered a resource.
• So, when a deadlock happens, it can be resolved if one car backs up (preempt resources and roll back).
• Several cars may have to be backed up if a deadlock situation occurs.
• So, starvation is possible.

Example of deadlock

What is Circular wait?

One process is waiting for a resource that is held by a second process, which is also waiting for a resource held by a third process, and so on. This continues until the last process is waiting for a resource held by the first process. This creates a circular chain.

For example, Process A is allocated Resource B while it is requesting Resource A. In the same way, Process B is allocated Resource A while it is requesting Resource B. This creates a circular wait loop.

Example of Circular wait

For example, a computer has three USB drives and three processes. Each of the three processes holds one of the USB drives. So, when each process requests another drive, the three processes reach a deadlock situation, as each one waits for a USB drive to be released while it is still in use. This results in a circular chain.

Circular wait example

Deadlock Detection in OS

A deadlock occurrence can be detected by the resource scheduler. A resource scheduler helps the OS keep track of all the resources that are allocated to different processes. Once a deadlock is detected, it can be resolved by preempting resources, rolling back a process, or terminating one or more of the deadlocked processes.

Deadlock Prevention in OS

It is important to prevent a deadlock before it can occur. The system checks every transaction before it is executed to make sure it does not lead to a deadlock. Even a small operation that could cause a deadlock in the future is never allowed to execute.

Deadlock prevention is a set of methods for ensuring that at least one of the four necessary conditions cannot hold.

No Preemption

A resource can be released only voluntarily by the process holding it, after that process has finished its task.

• If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all of its resources are released.
• Preempted resources are added to the list of resources for which the process is waiting.
• The process is restarted only when it can regain its old resources as well as the new one that it is requesting.

Mutual Exclusion

Mutual Exclusion is the full form of Mutex. It is a special type of binary semaphore that is used for controlling access to a shared resource. It includes a priority-inheritance mechanism to avoid extended priority-inversion problems and keeps higher-priority tasks blocked for the shortest time possible.

Shared resources such as read-only files never lead to deadlocks, but resources like printers and tape drives need exclusive access by a single process.

Hold and Wait

In this condition, processes must be stopped from holding one or more resources while simultaneously waiting for one or more others.

Circular Wait

This method imposes a total ordering of all resource types. Circular wait prevention also requires that every process request resources in an increasing order of enumeration.

Deadlock Avoidance Algorithms

It is better to avoid a deadlock instead of taking action after the deadlock has occurred. Avoidance needs additional information, such as how resources will be used. Deadlock avoidance is a useful model in which each process declares the maximum number of resources of each type that it may need.

Avoidance Algorithms

The deadlock-avoidance algorithm dynamically assesses the resource-allocation state so that a circular-wait situation can never occur.

For a single instance of a resource type:

• Use a resource-allocation graph.
• A cycle in the graph is necessary and sufficient for a deadlock.

For multiple instances of a resource type:

• A cycle is necessary but not sufficient for a deadlock.
• Use the Banker’s algorithm.

Difference Between Starvation and Deadlock

Here are some important differences between deadlock and starvation:

Deadlock	Starvation
The deadlock situation occurs when one of the processes gets blocked.	Starvation is a situation where all the low-priority processes get blocked while the high-priority processes execute.
Deadlock is an infinite process.	Starvation is a long wait, but not an infinite process.
Every deadlock always has starvation.	Every starvation does not necessarily have a deadlock.
Deadlock happens due to mutual exclusion, hold and wait, no preemption, and circular wait occurring together.	It happens due to uncontrolled priority and poor resource management.

Advantages of Deadlock

Here are the pros of using the deadlock handling method:

• This situation works well for processes that perform a single burst of activity.
• No preemption is needed for deadlock.
• It is a convenient method when applied to resources whose state can be saved and restored easily.
• It is feasible to enforce via compile-time checks.
• It needs no run-time computation, since the problem is solved in the system design.

Disadvantages of Deadlock

Here are the cons of using the deadlock handling method:

• It delays process initiation.
• Processes must know their future resource needs in advance.
• It preempts more often than necessary.
• It disallows incremental resource requests.
• It has inherent preemption losses.

FAQs