Deadlock in Operating System

A Deadlock is a situation where each of the computer process waits for a resource which is being assigned to some another process.
In this situation, none of the process gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released.
Deadlock VS Starvation:
Deadlock is a situation where no process got blocked and no process proceeds.
Starvation is a situation where the low priority process got blocked and the high priority processes proceed.

Necessary conditions for Deadlocks

Mutual Exclusion
A resource can only be shared in mutually exclusive manner.
It implies, if two process cannot use the same resource at the same time.
Hold and Wait
A process waits for some resources while holding another resource at the same time.
No preemption
The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.
Circular Wait
All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process.

Deadlock Ignorance
Deadlock Ignorance is the most widely used approach among all the mechanism.
This is being used by many operating systems mainly for end user uses.
In this approach, the Operating system assumes that deadlock never occurs.
It simply ignores deadlock.
This approach is best suitable for a single end user system where User uses the system only for browsing and all other normal stuff.
Deadlock prevention
Deadlock happens only when Mutual Exclusion, hold and wait, No preemption and circular wait holds simultaneously.
If it is possible to violate one of the four conditions at any time then the deadlock can never occur in the system.
The idea behind the approach is very simple that we have to fail one of the four conditions but there can be a big argument on its physical implementation in the system.
Deadlock avoidance
In deadlock avoidance, the operating system checks whether the system is in safe state or in unsafe state at every step which the operating system performs.
The process continues until the system is in safe state.
Once the system moves to unsafe state, the OS has to backtrack one step.
In simple words, The OS reviews each allocation so that the allocation doesn't cause the deadlock in the system.
Deadlock detection and recovery
This approach let the processes fall in deadlock and then periodically check whether deadlock occur in the system or not.
If it occurs then it applies some of the recovery methods to the system to get rid of deadlock.

If we can be able to violate one of the four necessary conditions and don't let them occur together then we can prevent the deadlock.
Mutual Exclusion
Spooling can be an effective approach to violate mutual exclusion but it suffers from some kinds of problems.
We cannot violate mutual exclusion for a process practically.
Hold and Wait
A process must be assigned all the necessary resources before the execution starts.
A process must not wait for any resource once the execution has been started.
But it is practically not possible. Possibility of getting starved will be increases due to the fact that some process may hold a resource for a very long time.
No Preemption
If we take the resource away from the process which is causing deadlock then we can prevent deadlock.
This is not a good approach at all since if we take a resource away which is being used by the process then all the work which it has done till now can become inconsistent.
Circular Wait
To violate circular wait, we can assign a priority number to each of the resource.
A process can't request for a lesser priority resource.
This ensures that not a single process can request a resource which is being utilized by some other process and no cycle will be formed.
Among all the methods, violating Circular wait is the only approach that can be implemented practically.

In deadlock avoidance, the request for any resource will be granted if the resulting state of the system doesn't cause deadlock in the system. The state of the system will continuously be checked for safe and unsafe states.
In order to avoid deadlocks, the process must tell OS, the maximum number of resources a process can request to complete its execution.
The simplest and most useful approach states that the process should declare the maximum number of resources of each type it may ever need. The Deadlock avoidance algorithm examines the resource allocations so that there can never be a circular wait condition.
A state of the system is called safe if the system can allocate all the resources requested by all the processes without entering into deadlock.
If the system cannot fulfill the request of all processes then the state of the system is called unsafe.
The key of Deadlock avoidance approach is when the request is made for resources then the request must only be approved in the case if the resulting state is also a safe state.

The OS can detect the deadlocks with the help of Resource allocation graph.
Detection
Single Instance --> Detect Cycle
Multiple Instance --> Safety Algorithm
In single instanced resource types, if a cycle is being formed in the system then there will definitely be a deadlock.
In multiple instanced resource type graph, detecting a cycle is not just enough. We have to apply the safety algorithm on the system by converting the resource allocation graph into the allocation matrix and request matrix.

In order to recover the system from deadlocks, either OS considers resources or processes.
For Resource
Preempt the resource
- We can snatch one of the resources from the owner of the resource (process) and give it to the other process with the expectation that it will complete the execution and will release this resource sooner. Well, choosing a resource which will be snatched is going to be a bit difficult.
Rollback to a safe state
- System passes through various states to get into the deadlock state. The operating system canrollback the system to the previous safe state. For this purpose, OS needs to implement check pointing at every state.
- The moment, we get into deadlock, we will rollback all the allocations to get into the previous safe state.
For Process
Kill a process
- Killing a process can solve our problem but the bigger concern is to decide which process to kill.
- Generally, Operating system kills a process which has done least amount of work until now.
Kill all process
- This is not a suggestible approach but can be implemented if the problem becomes very serious.
- Killing all process will lead to inefficiency in the system because all the processes will execute again from starting.