Deadlock Handling in OS

Deadlocks introduction:

In a computer system, a situated arise when two or more processes attempt to access some resources, but the resources are locked by the other processes, and hence cannot be shared. Each of these processes will keep on waiting for its required resource which is held by some other process. No process will finish ever as each process is in waiting for the state. Such a situation is called a deadlock.

In other words,'' a set of different processes is said to be in a deadlock state if every process in the set is waiting for an event that can be caused by another process in the set of a computer network system.

Deadlock Example

Deadlock may occur in the computer system as well as in daily life activities. Here are some examples of deadlock:

A deadlock situation may also arise in the real world. Suppose two trains approach each other from the opposite side on a single track as shown. Each train wishes another one to get back to mack way for it. But this will never happen. 

Necessary Conditions for Deadlock 

 we have discussed two processes only. However, in the actual computer system, many more processes may get involved in a deadlock. Therefore, to completely define a deadlock in a system, the following four conditions must exist in that system: 

Mutual Exclusion

Mutual exclusion condition means to lock a resource in exclusive mode or non-shareable mode. For a deadlock to happen, each involved resource must behave exclusively allocated to only one process at a time. If another process needs to use that resource, it must wait until the resource has been released.

Hold-and -Wait 

In a deadlock, each involved process holds one or more resource and waits for additional resources which are currently begin held by other processes in the system. It means that a deadlock may occur only if every involved process holds one or more resources and further needs additional resources.

 No Preemption

A deadlock system cannot be taken away forcefully from the processes holding them. Suppose process P1 holds the resources R1 and waits for the resource R2, which is locked by the process P2 in exclusive mode. The condition of no-preemption requires that the operating system cannot be preempted (or release forcefully) the resources R2 (for process P1) from the processes P2.

Circular Wait

A closed chain has processes that must exist for a system to be in a deadlock, such that each process chain holds at least one resource needed by the next process in the chain. Suppose there are three processes P1, P2, and P3 and three resources R1, R2, and R3 and three resources R1, R2, and R3. The process P1 is waiting to get R1, which is held (acquired)by the process P2, the process P2 is waiting to get R2, which is held by the process P3, and P3 is waiting to get R3, which is held by the process P1. The circular wait situation occurs.

System Resource-Allocation Graph

A gray is a collection of points and lines connecting them. The points of a graph are commonly known as nodes or vertices. Whereas, the lines connecting the nodes of a graph are called edges or arcs.

• Request Edge,
• Assignment Edges

Uses of Resources-Allocation Graph:

Edges in a resource-allocation graph are also classified into two types to determine whether or not a deadlock exists in a system. If the graph contains no cycle, then the system is safe and no deadlock ex If a graph contains a cycle, then a deadlock may exist. Usually, deadlock may occur when all resource has exactly one instance and cannot be shared by different resources.

Methods for handling deadlocks:

Different OS adopts different strategies to handle deadlock.

1. We can use a protocol to prevent or avoid deadlock so that the system will never enter a deadlock state.

2. We can allow the system to enter a deadlock state, detect the deadlock, and cover it.

3.We can ignore the deadlock problems and make-believe that deadlocks never occur in the system. this method of commonly used in some of the OS including Unix and windows. It can also be handled by developing a program.

Deadlock Prevention

We know that a deadlock occurs when all four necessary conditions for deadlock are applied in a system. Deadlock can be prevented by designing a system in such a way that at least one of the four deadlock conditions cannot occur. By implementing this policy, we can prevent the occurrence of a deadlock in a system, but other problems may be created through this approach. Now, we examine deadlock prevention techniques related to each of the four conditions

1. Mutual Exclusion 
2. Hold-and -Wait

Disadvantages

Some main disadvantages of this  policy are as following :

1. A process may not know in advance all of the resources, it will be required. The resources needed may depend on its computations.
2. Its several resources are allocation at the beginning of the process, the process may hold these resources for a long time; during that time they are denied to other processers.
3. Starvation is possible, which means that a process requesting several resources may never find them all, available at one time. It is because at least one of the resources that it needs is always allocated to some other process.

Problems with Second Strategy

Unfortunately, in most cases, the second strategy may create serious problems. For example, a disk is allocated to process P1 to copy data on it. Suppose written on the disk.

No Preempting

The third condition for deadlock is that there is no preempting of the resources already allocated to other processes. This condition can be prevented in server ways.

Eliminating this condition is less practicable than eliminating Mutual Exclusion. To prevent the ''No Preempting'' condition.

Circular Wait

However, the following problems may arise in eliminating the circular wait.

• Circular wait prevention slows down processes and denies resource access. It means that it reduces the resources utilization and performance of the overall system.
• Although the numerical ordering of resources eliminates the problem of deadlock from a system, it may be impossible to find an ordering that satisfies every process in a system.