Deadlock

Deadlock

Definition

• A set of process is in a deadlock state if each process in the set is waiting for an event that can be caused by only another process in the set. 
• In other words, each member of the set of deadlock processes is waiting for a resource that can be released only by a deadlock process. 
• None of the processes can run, none of them can release any resources, and none of them can be awakened. 
• It is important to note that the number of processes and the number and kind of resources possessed and requested are unimportant.

• The resources may be either physical or logical. Examples of physical resources are Printers, Tape
• Drivers, Memory Space, and CPU Cycles. Examples of logical resources are Files, Semaphores, and
• Monitors.

Preemptable and Nonpreemptable Resources



Resources come in two flavors:

• A preemptable resource is one that can be taken away from the process with no ill effects. Memory is an example of a preemptable resource.
• A non-preemptable resource is one that cannot be taken away from process (without causing ill effect).
• For example, CD resources are not preemptable at an arbitrary moment.
• Reallocating resources can resolve deadlocks that involve preemptable resources.

Necessary and Sufficient Deadlock Conditions



Coffman conditions that must hold simultaneously for there to be a deadlock.

1.Mutual Exclusion Condition

The resources involved are non-shareable.

Explanation: At least one resource (thread) must be held in a non-shareable mode, that is, only one
process at a time claims exclusive control of the resource. If another process requests that resource, the
requesting process must be delayed until the resource has been released.

2.Hold and Wait Condition

Requesting process hold already, resources while waiting for requested resources.

Explanation: There must exist a process that is holding a resource already allocated to it while waiting for
additional resource that are currently being held by other processes.

3.No-Preemptive Condition
Resources already allocated to a process cannot be preempted.

Explanation: Resources cannot be removed from the processes are used to completion or released
voluntarily by the process holding it.

4.Circular Wait Condition

The processes in the system form a circular list or chain where each process in the list is waiting
for a resource held by the next process in the list.

As an example, consider the traffic deadlock in the following figure


Consider each section of the street as a resource.

1. Mutual exclusion condition applies, since only one vehicle can be on a section of the street at a
time.

2. Hold-and-wait condition applies, since each vehicle is occupying a section of the street, and
waiting to move on to the next section of the street.

3. No-preemptive condition applies, since a section of the street that is a section of the street that is
occupied by a vehicle cannot be taken away from it.

4. Circular wait condition applies, since each vehicle is waiting on the next vehicle to move. That is,
each vehicle in the traffic is waiting for a section of street held by the next vehicle in the traffic.
The simple rule to avoid traffic deadlock is that a vehicle should only enter an intersection if it is assured
that it will not have to stop inside the intersection.
It is not possible to have a deadlock involving only one single process. The deadlock involves a circular
“hold-and-wait” condition between two or more processes, so “one” process cannot hold a resource, yet be
waiting for another resource that it is holding. In addition, deadlock is not possible between two threads in
a process, because it is the process that holds resources, not the thread that is, each thread has access to the
resources held by the process.



Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock.

The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:

•  Temporarily prevent resources from deadlocked processes.
•  Back off a process to some check point allowing preemption of a needed resource and restarting
• the process at the checkpoint later.
• Successively kill processes until the system is deadlock free.
• These methods are expensive in the sense that each iteration calls the detection algorithm until the system
• proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number of proceeds.
• Another potential problem is starvation; same process killed repeatedly.

Deadlock Avoidance
This approach to the deadlock problem anticipates deadlock before it actually occurs. This approach employs an algorithm to access the possibility that deadlock could occur and acting accordingly. This method differs from deadlock prevention, which guarantees that deadlock cannot occur by denying one of the necessary conditions of deadlock.

If the necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being careful when resources are allocated. Perhaps the most famous deadlock avoidance algorithm, due to Dijkstra [1965], is the Banker’s algorithm. So named because the process is analogous to that used by a banker in deciding if a loan can be safely made.