Definition:
Deadlock a situation in which a set of process exists, each of which is blocked awaiting a resource that is already allocated to another process in that set. A set of processes is said to be in a deadlock, if each process in the set is waiting for an event that only another process in the set can cause. Lets take for example this simple illustration in real life scenario; Consider a scenario where you and a friend decided to eat something. Now, to serve yourselves, you picked a bowl but didn’t get a spoon, on the other hand, your friend picked a spoon and didn’t get a bowl. Now, both of you have a resource (bowl or spoon) and require exactly one more resource(spoon or bowl) to eat the dessert. And this is the scene where the “deadlock” comes into the picture. Neither you nor your friend is ready to give his resource to the other person. So both of you stand there waiting for each other infinitely, and this is what we call a situation of deadlock. Deadlock is a situation where two or more processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. In a local area network, most of the resources are shared. It becomes congested when more than two processes are in a deadlock state.
The following four conditions must all hold for a deadlock to exist:
Mutual Exclusion: Mutual exclusion says that a resource can be used by only one process at a time.
Hold and Wait: This is a condition where a process is holding at least one resource and is waiting for other resources.
No Preemption: If a process is holding a resource, it cannot be taken back from it unless the process itself releases the resource explicitly.
Circular Wait: A set of processes are waiting for each other for the resources in a circular fashion. For example, P1 is waiting for P2, P2 is waiting for P3, and P3 is again waiting for P1.

How to deal with Deadlocks in Operating Systems
There are four ways to deal with these resource deadlocks. They are listed below.

1. Ignoring the problem. This is also called the ostrich algorithm


2. Detection and Recovery. Let deadlocks occur, detect them, and then recover from them.


3. Dynamic avoidance using careful resource allocation.


4. Prevention, by negating one of the four conditions.

The Ostrich Algorithm in Deadlocks
This algorithm is the way life should be handled. It gets its name from the ostrich and the way it sticks its head in the sand and ignores everything that’s happening around. Not necessarily a life pro tip, but it works in computers. While a group of highly qualified mathematicians are against this approach, as they want to dive deep into what is causing the deadlock, others find it more tolerate-able.

Pros of ignorance in deadlocks?
No manpower is required to do any extra work. When the system crashes, restart it. This is viable only when a deadlock occurs rarely.

Cons of ignorance in deadlocks?
If it happens quite often, then this is not an optimal solution. You’ll have to invest some time in properly dealing with deadlocks, that’s any of the next three methods.

Deadlock Detection and Recovery
There are two different types of resource deadlocks, and they need to be programmed differently. In one of the types, there is only one resource of each type. This means that multiple desktops share one scanner, one printer, and so on. We use resource graphs to detect a deadlock in this scenario.
In another type, there is more than one resource of each type. This means there are multiple printers for multiple desktops. We need two matrices, the current allocation matrix, and the request matrix to detect a deadlock in this scenario.
To detect a deadlock, if all resource types have only one instance, then we can use a graph called wait-for-graph, which is a variant of the resource-allocation graph. Here, vertices represent processes, and a directed edge from P1 to P2 indicates that P1 is waiting for a resource held by P2. Like in the case of a resource allocation graph, a cycle in a wait-for-graph indicates a deadlock. So the system can maintain a wait-for-graph and check for cycles periodically to detect any deadlocks.
The wait-for-graph is not much of use, if there are multiple instances for a resource, as a cycle may not imply a deadlock. In such a case, we can use an algorithm similar to Banker’s algorithm to detect deadlock, which we’ll discuss later on.
After the detection of a deadlock, we need to recover from it. Following are some ways to recover from a deadlock:

1. Process Termination: To eliminate deadlock, we can simply kill one or more processes. For this, we use two methods:

• Abort all the processes involved in a deadlock


• Abort one process at a time until the deadlock is eliminated.

2. Resource Preemption: To eliminate deadlocks using resource preemption, we preempt some resources from processes and give those resources to other processes. This method will raise three issues

• Selecting a victim: We must determine which resources and which processes are to be preempted and also the order to minimize the cost.


• Rollback: We must determine what should be done with the process from which resources are preempted. One simple idea is a total rollback, which means abort the process and restart it.


• Starvation: In a system, it may happen that the same process is always picked as a victim. As a result, that process will never complete its designated task. This situation is called Starvation and must be avoided.

Deadlock Avoidance
To avoid deadlocks, we can make use of prior knowledge about the usage of resources by processes, including resources available, resources allocated, future requests, and future releases by processes. Most deadlock avoidance algorithms need every process to tell in advance the maximum number of resources of each type that it may need. Based on all information, we may decide if a process should wait for a resource or not, and thus avoid chances for the circular wait.
If a system is already in a safe state, we can try to stay away from an unsafe state and avoid deadlock. Deadlocks cannot be avoided in an unsafe state. A system can be considered to be in a safe state if it is not in a state of deadlock and can allocate resources to the maximum available. A safe sequence of processes and allocation of resources ensures a safe state. Deadlock avoidance algorithms try not to allocate resources to a process if it makes the system go into an unsafe state.
A resource allocation graph is generally used to avoid deadlocks. If there are no cycles in the resource allocation graph, then there are no deadlocks. If there are cycles, there may be a deadlock. If there is only one instance of every resource, then a cycle implies a deadlock.

Deadlock Prevention in Operating Systems
Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold and wait, no preemption, and circular wait) does not hold true. We do this by facing each of the four conditions on separate occasions. However, most prevention algorithms have poor resource utilization and hence result in reduced throughputs.

Facing the Mutual Exclusion condition
Let’s recall what the mutual exclusion condition states. Each resource is either assigned to exactly one process, or it is available.
If no resource were ever assigned exclusively to a single process, then we would never have deadlocks. What this means is that all resources should be shared between all processes, and that will never lead to a deadlock. However, if two processes start printing on a shared printer together, then the output would be unreadable. In this model, the only process that actually requests the printer resource is the printer daemon. A daemon is a background process that handles all requests and provides services.
The daemon is strictly programmed to start printing when the complete output file is ready and not when it is being edited.
So how do we face the mutual exclusion condition? We avoid assigning a resource when that is not necessary. And we also try to make sure that as few processes as possible might claim the resource.

Facing the Hold and Wait condition
Let’s recall what the hold and wait condition was. Processes holding resources that were granted earlier can request for newer resources.
This condition is slightly more promising. Here, if the process is allocated all the resources it would require beforehand, then it won’t need to ask for more resources, and there would be no deadlock. If, for some reason, the resource can’t be allocated to the process due to unavailability, then the process just waits until it gets the resource, and then it is processed.
The immediate problem with this is that many processes don’t know what resources they would need until they have already started running. If they knew what resources are required, then we could use the banker’s algorithm. Another issue is that resources will be locked in until the process has completed its run. This does not use the resources optimally.
Some mainframe batch systems require the programmer to list out all the resources it would require at the beginning of the code. This is a waste of the users’ time and also a lot of waste of resources, but it does prevent the deadlock.
A slightly different variant to break the hold and wait condition is to make the process drop all of the resources it is currently holding, whenever requesting for a new resource. Then it can grab hold of all the required resources again. This is also not an optimal use of processing power.

Facing the No Preemption condition
Let’s recall what the no preemption condition was. Any resource that was granted to a process can not be taken from it forcibly until the process has explicitly stated that it doesn’t require the resource any more and frees it up.
Facing this condition is also a possibility to avoid deadlocks. Take, for example, the printer as the resource. If a process has been assigned the printer and is in the middle of printing its output, forcibly taking away the printer because a needed plotter isn’t readily available is tricky at best and impossible at worst. However, some resources can be virtualized to avoid this situation. Spooling printer output to the disk and allowing only the printer daemon access to the real printer eliminates deadlocks regarding the printer, but creating one for disk space.
But then again, not all resources can be virtualized, and sometimes processes will have to lock in the resources, and they can not be taken away (preempted), thus giving us the potential of a deadlock.

Facing the Circular Wait condition
Let’s recall what the circular wait condition was. There must be a circular chain of two or more processes where one process is holding a resource that is needed by the next process in the chain.
To avoid the circular wait, resources may be ordered, and we can ensure that each process can request resources only in increasing order of these numbers. The algorithm may itself increase complexity and may also lead to poor resource utilization.