Deadlock in Operating Systems

Deadlock

 

                                In an operating system deadlock arrived when two or more process want to access the same resource (resource may include processors, memory, network modem, printers and files etc.)  To compete their task or action.

Or when two or more process waiting for each other to complete is called a deadlock situation.

For example:

Process P0 using resource R0 and it need resource R1 to complete its task but at the same time another process P1 is using resource R1 and it need the resource R0 which is currently acquired by P0 to complete its own action so both processes wait for each other to complete their task and they keep waiting for life time because no one can complete its action. So we can say that the both processes are in deadlock situation.

As you can see in the figure given below.

Conditions when deadlock occur:

·         At one time a single process can use the a resource (Mutual Exclusion)

·         A process holding a resource and also waiting for another resource which is currently in use of other process (Hold and Wait)

·         A process can release resource when it completes its execution (No Preemption)

·         When two or more processes waiting for one another to release the resource so they can complete their task.

Solutions:

                                There are three method to get rid of deadlocks

Deadlock prevention:

                                                                In this method it is ensured in the Operating system that system will never enter in deadlock situation.

Every process have access to the shared resource at the same time but not for the unshared resources,

Make sure when a process request for a resource it is not holding any other resources. Process must request for resource and be allocated before start its execution. Or allow the process to request for resource when it has no resource allocated.

If a process request for resources and currently holding some resources then cannot allocate the new resource until it release the currently holding resources.

Restart the process when it regain the old resource and the new one which was requested. Each process must request for resources in increasing order.

Preempted resource should be added in to the required resources list for which process are waiting.

Deadlock avoidance:

Ignore the deadlocks and pretend that deadlock never occurs in the system. Most of the operating system use this method including UNIX.

This method need some prior information available about the processes and the resources.

In this each process which is currently loaded declare the maximum number of resource which required by the process to complete its task. Algorithm for deadlock avoidance check for resources allocation to ensure that there is no process waiting for the resource which is currently in use or it ensure that there is no circular waiting of processes. Maintains a state of available resource and allocated resource, and also keep the record of resourced demand by the processes.

 

Deadlock detection:

                                                                Allow the system to go in the deadlock situation and then recover the system from deadlock using different algorithms.

First allow the system to enter in a deadlock state then define some detection algorithms to detect the deadlock in the system, and make a recovery scheme to recover the system from deadlock condition.

To recover the system from a deadlock state select a victim and reclaim the resource, or roll back the process which is most recently started.

Deadlock recovery:

                                                                If deadlock is occurred now what steps we should take.

Process termination:

·         Delete all the process which are in deadlock condition but is expensive.

·         Delete one by one process until the deadlock is broken.

·         Select a process which is recently start and terminate it.

Resource preemption:

·         Select a resource to preempt.

·         Roll back to a previous safe state.

·         Prevent the one process which is always selected as a victim.

System States:

·         Safe state

·         Unsafe state

·         Deadlock state

System can be in one of the states given above.

Safe state:

                                A system is in a safe state if all the process are in a sequence and resource required by a process are available at the time and not in use of any of the other process. When a process request for the resources system must check that after the allocation of these resource system can remain in safe state.

If a process need a resource which is currently in use so this process can wait until the process release the required resource.

If a system is in safe state that means there is no deadlocks.

Unsafe state:

                                A system is in unsafe state when there is a chance of the occurrence of deadlock or resources allocated which is currently in use of some other processes.

Deadlock state:

                                System in deadlock state when two or more process want the same resources or two or more process waiting for each other to complete their tasks.