Deadlock, Necessary Conditions of Deadlock/Characterization, Deadlocks Handling, Prevention, Avoidance in OS

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters into wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock. System is deadlocked if there is a set of processes such that every process in the set is waiting for another process in the set.

Example 1
System has 2 disk drives.
P1 and P2 each hold one disk drive and each needs another one.

Example 2
- Porcess A makes a request to use the scanner
- Porcess A given the scanner
- Process B request thee CD writer
- Process B given the CD writer
- Now a requrest the CD writer
- A is denied permission until B releases the CD writer
- Also now B ask for the scanner
- Result is DEADLOCK !!

Necessary conditions for deadlock/Deadlock Characterization

A deadlock can arise if the following four conditions hold simultaneously (Necessary Condition).
1. Mutual exclusion: 
Only one process at time can use the resource.
.
2.  Hold and wait: 
A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.

3. No preemption: 
A resource can be released only voluntarily by the process holding it, after that process has completed its task.

4. Circular wait:
A set {P0, P1, …, Pn} of waiting processes must exist such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Deadlocks Handling

Mainly there are four methods of handling deadlock
1. Deadlock avoidance 
To avoid deadlocks the system dynamically considers every request and decides whether it is safe to grant it at this point. The system requires additional prior information regarding the overal potential use of each resource for each process. 

2. Deadlock Prevention 
It means that we design such a system where there is no chance of having a deadlock. The goal is to ensure that at least one of the Coffman's necessary conditions for deadlock can never hold. Deadlock can be prevented deadlocks by constraining how request for resources can be made in the system and how they are handled.

3. Deadlock Detection and Recovery 
We can allow the system to enter a deadlock state, detect it and recover - If a system does not employ either a deadlock prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock.

4.  Ignore the Problem (Ostrich Algorithm) : 
We can ignore the deadlock problem altogether. If the deadlock occurs, the system will stop functioning and will need to be restarted manually. This approach is used in systems in which deadlocks occur infrequently and if it is not a life critical system. This method is cheaper than other methods. This solution is used by most operating systems, including UNIX.

Deadlock Prevention 

If we simulate deadlock with a table which is standing on its four legs then we can also simulate four legs with the four conditions which when occurs simultaneously, cause the deadlock.

However, if we break one of the legs of the table then the table will fall definitely. The same happens with 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.

Deadlock prevention methods are given below
1. Attack mutual Exclusion
Must hold only for non-sharable resources. Sharable resources, on the other hand, do not require mutually exclusive access, and thus cannot be involved in a deadlock.

2. Attack Hold and Wait
Ensure that whenever a process requests a resource, it does not hold any other resources. Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. There is a drawback of low resource utilization in this method.

3. Attack No Preemption
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are preempted (or released). If a process requests some resources and if they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process.

4. Attack Circular Wait
One way to ensure that circular wait never holds is to Impose a total ordering of all resource types, and require that each process requests resources in an increasing or decreasing order of enumeration.

Deadlock Avoidance 

Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources, such as which resources a process will consume in its lifetime. For every resource request, the system sees whether granting the request will cause the system to enter an unsafe state. The system then only grants request that will lead to safe states. In order for the system to be able to determine whether the next state will be safe or unsafe, it must know in advance at any time. 

• Resources currently available
• Resources currently allocated to each process 
• Resources that will be required and released by these process in the future

It is possible for a process to be in an unsafe state but for this not result in a deadlock. The notion of safe/unsafe state only refers to the ability of the system to enter a deadlock state or not. For example, if a process requests A which would result in an unsafe state but releases B which would prevent circular wait then the state is but the system is not in deadlock. One known algorithm that is used for deadlock avoidance is the Banker's algorithm, which requests resource usage limit to be known in advance. However, for many systems it is impossible to know in advance what every process will request. This means that deadlock avoidance is impossible practically.