Deadlock is a situation in a system in which each process is waiting for a resource that is currently under the control of some other process. In a multiprogramming environment, several processes request the resources to the operating system. When processes request resources, the operating system will allocate the resources to the processes only if the requested resource by each process is available at that time.

If suppose the requested resource is not available the process that has requested enters into waiting state since the requested resource is acquired by some other waiting process. This situation is called Deadlock.

Necessary Conditions for Deadlock :

A deadlock can occur if the following four conditions hold simultaneously in a system,

• Mutual Exclusion – In a non-sharable environment where not more than a single process can be allocated with a particular resource at a time is referred to as mutual exclusion. In such an environment, a resource in use if requested by some other process, it is kept on hold until the release of that resource.
• Hold and Wait – As the name implies the process is already holding a resource and requires some of the additional resources in use by other processes. Hence this situation is known as hold and wait.
• No Preemption – A resource allocated to one process can be allocated to other only when the process holding it deallocates it after completion. This means that we cannot preempt the resources.
• Circular Wait – There exists a list of waiting processes (P₀, P₁,…, P_n) such that process P₀ is waiting for a resource currently under the usage by process P₁, P₁ is waiting for a resource that is held by P₂, P₂ is waiting for a resource that is held by P₃, and so on. Finally, a process P_n is waiting for the resource held by P₀.

Out of the four conditions described above, the first three conditions are necessary but not enough for the existence of a deadlock. The fourth condition actually results from the first three conditions i.e., the first three conditions result in a sequence of events that finally leads to an unresolved circular wait which is actually the main cause for the occurrence of deadlock.

Deadlock Prevention :

Deadlock prevention means placing restrictions on resource requests so that deadlock cannot occur. Deadlock can be prevented by denying at least any one of the conditions seen above as follows,

Preventing Mutual Exclusion :

Only for non-sharable resources, the mutual exclusion concept should be applied.

For example, a printer is a non-sharable resource. If one program is using a printer then other programs must wait for the printer. This waiting may lead to indefinite waiting, but to overcome this, the non-shareable resource may be made because, for sharable resources, the concept of mutual exclusion is not required.

However, by making the printer sharable, we get an error output. In general, it is not possible to prevent deadlock by denying the mutual exclusion principle, since some resources should be maintained as non-shareable resource i.e. when one program is accessing it other programs cannot access it.

Preventing Hold and Wait :

The hold and wait condition preludes a process from holding some resources while requesting others. There are two protocols to prevent hold and wait.

• Request all the resources before starting execution. Any program must request all the resources before starting the execution, acquire them, use them and release them once execution is completed. In this way, no process will wait for the resources during execution. Thus, hold and wait is prevented.
• Any process will request a new resource only when it has none i.e. if a process has two resources and requires three more resources, then the process can request for these three resources after releasing two resources it is holding. After releasing the resources, it will request new resources. If they are busy, the process waits without holding any resources. Suppose, if the requested resources are free, then they can be allocated to the process.

Consider a process that needs to copy data from the DVD drive to the disk file. If the data need to be printed, it is copied, sorted, and is sent to the printer. For doing all these things the process either needs to request all the resources at the beginning of the process or obtain them when needed. Both the cases prevent the hold and wait condition.

Preventing No Preemption :

If a system follows no preemption, then the resources which are once allocated are not taken back from a process involuntarily. Any system with the above behavior can lead to hold and wait condition, and thereby to deadlock. Hence, no preemption condition should not be applied in order to prevent deadlock.

If a process P₁ request any resource R₁ which is currently held by some other process P₂ then, P₂ is preempted and R₁ is given to P₁.

Consider a car occupying some part of the street which cannot be taken by another car until and unless the first car has been moved. This situation is known as No preemption. An occurrence of this condition can be prevented only if the first car has been moved forcibly giving the other car a chance to place itself and finish its task.

However, this approach is not good because involuntarily taking of resource which is in use by the other process can make all the work inconsistent done by that process till now.

Preventing Circular Wait :

Circular wait occurs, when there are a set of processes {P_j}, that hold units of a set of an ‘n’ different resources {R_j} such that, P_j holds R_j, while it requests units of different resources in the set.

In other words, each of the ‘n’ resources is held by the ‘n’ processes, but each process then requests unavailable units of one of the resource types held by another process. A circular wait is reflected by the resource process relationships (represented wholly within a system state), so the state-transition model does not help in the study of this problem.

To prevent circular wait, we impose ordering of all resource types i.e., a unique integer number is assigned to each resource. This concept is applied only for resources of higher numbers or higher “id”. If a process is requesting resources of a higher “id”, it must be released.

If a process acquires all of the resources, it needs at one time, then it will never be in a situation, where it is holding a resource and waiting for another resource. This will prevent deadlock.

Consider that the resources have been assigned positive integers as, Printer → 1, Tap drive → 2, Card punch → 3, Card reader → 4, Plotter → 5. Now, the process must request the resources in numerical order. For example, the process can request the printer first followed by the card punch and card reader (1, 3, 4). It cannot request a card reader first and then the printer.

Among all the deadlock prevention methods, only circular wait prevention can be implemented practically.