What is Deadlock?

This article gives the information of deadlock related to the operating system. Process complete for physical and logical resources in the system. A process request resources, if those are not available at that time, a process enters into the wait state. It may happen that waiting process will never change the state again, because resources requested by the process are occupied by the some other process. And this condition leads to deadlocks. Deadlocks affect the process by causing indefinite delays in resources allocation. Processing is blocked, waiting on events that could never happen. Such delays have serious consequences for the response time of process and performance of system. Hence, operating system must use resources policies which ensure an absence of deadlock.

The concept of deadlock can be best understood by the following line:

“When two trains approach each other at crossing both shall come to full stop and neither shall start up again until other has gone”. Deadlocks can happen only that time when process have been granted exclusive access to device files. A system is a combination of a finite number of resources to be distributed among a number of computing process. When several copies of resources are available, one of them can be used to satisfy any request for the resource. Resources come into two types:

1. A preempt able resource: It is one that con be taken away from the process owing it without no ill effects.
2.  A non -preempt able resource: it is one that can’t be taken away from its current owner without causing the computation to fail.

Process must request resources before using it must release the resource after using it. A process may request many resources as it requires from the available resources to carry out its designed task. This implies that a process cannot request more number of resources than available.

Under the stable mode of operation a process may utilize a resource in only the following sequence:

1. Request the resources. If request is not granted immediately then requesting the process must wait until it can acquire the resources.
2. Use the resources. I.e. use the memory to perform it task.
3. Release the resources i.e. release memory to perform the task.

Request and release of other operation can be accomplished through wait and signal operation on semaphores, therefore for each use the operating system checks to make sure that the using process has requested and been allocated the resource. A system table records that is currently allocate to another process waiting for this resources. We may think that deadlock can occur on same resources type for example there is two printers in the system both of them are held by two different processes and then the first process wait for the second process to release the printer which is causing deadlock. But deadlock may also involve different resources.

CONDITION FOR DEADLOCK:

Following are the condition for deadlock:

1)      Mutual exclusion: Each resource either currently assigned to exactly one process or is available. Only one process at a time can use the resources. If another process must be delayed until the resources has been released.

2)      Hold and wait: There must be at least one resource that is holding at least one resource and is waiting to acquire resources that are currently being held by other process.

3)      No preemption: Resources previously granted cannot be forcibly taken away from a process. They must b explicitly released by the process holding them.

4)      Circular wait: There must be a set {P0,P1,………Pn}  of waiting process such as that  P0 is waiting for a resources that is held P1,P2 is waiting for a resources that is held by P2 and so on as explained. The circular wait condition implies the hold wait so the four conditions are not completely independent.

 

 

METHODS FOR HANDING DEADLOCK:

Basically there are four ways to deal with deadlock problem they are listed below:

Ignore the problem all to gather.

We can use a set of rules  to ensure that the system will never enter a deadlock state

We can allow the system to go into the deadlock state and then recover.

We can ignore the problem and pretend that deadlock never occurs in the system.

Don’t implementing the problem: The Ostrich algorithm: “Put your head in the sand approach”

i.            If the likelihood of a deadlock is sufficient small and the cost of avoiding a deadlock is sufficient high it might be batter to ignore the problem.

ii.            Clearly not a good philosophy for nuclear missile launchers.

iii.            For embedded system the program runs are fixed in advanced.

To ensure that deadlock never happen the system can use either deadlock prevention or deadlock avoidance scheme. If the system does not employ either deadlock prevention or deadlock avoidance algorithm then a deadlock situation may occurs. In this case the system can provide an algorithm that examines the state of the system to determine whether the deadlock has occurred and an algorithm to recover from deadlock. We may arrive at a situation where the system is in the deadlock state yet has no way of recognizing what has happen. In this case undedicated deadlock will result in deterioration if the system performance. Eventually the system will stop functions and will need to be restarted manually. It can be done in the system where deadlock happen frequently.

DEADLOCK PREVENTION:

There are two methods for deadlock prevention:

a)      Indirect method:

This indirect method of deadlock prevention is to prevent the occurrence of one of the three necessary conditions.

b)      Direct method:

This direct method of deadlock prevention is to prevent the occurrence of circular wait condition.

DEADLOCK AVOIDANCE:

Deadlock prevention ensures that one of the necessary conditions for deadlock cannot occur and hence deadlock cannot hold. But in the deadlock prevention the devices utilization is low and system throughput reduced. Deadlock avoidance requires additional information about how resources are to be requested.