“Crises and deadlocks when they occur have at least this advantage, that they force us to think.”- Jawaharlal Nehru (1889 - 1964) Indian political leader
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.
The simplest example of deadlock is where process 1 has been allocated non-shareable resources A, say, a tap drive, and process 2 has be allocated non-sharable resource B, say, a printer. Now, if it turns out that process 1 needs resource B (printer) to proceed and process 2 needs resource A (the tape drive) to proceed and these are the only two processes in the system, each is blocked the other and all useful work in the system stops. This situation ifs termed deadlock. The system is in deadlock state because each process holds a resource being requested by the other process neither process is willing to release the resource it holds.
Resources come in two flavors: preemptable and nonpreemptable. 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. On the other hand, a
nonpreemptable 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.
Deadlocks that involve nonpreemptable resources are difficult to deal with.
Consider each section of the street as a resource.
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.
In general, there are four strategies of dealing with deadlock problem:
Now we consider each strategy in order of decreasing severity.
Havender in his pioneering work showed that since all four of the conditions are necessary for deadlock to occur, it follows that deadlock might be prevented by denying any one of the conditions.
1 | ≡ | Card reader |
2 | ≡ | Printer |
3 | ≡ | Plotter |
4 | ≡ | Tape drive |
5 | ≡ | Card punch |
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.
In this analogy
Customers | ≡ | processes |
Units | ≡ | resources, say, tape drive |
Banker | ≡ | Operating System |
Customers | Used | Max | |
---|---|---|---|
A B C D |
0 0 0 0 |
6 5 4 7 |
Available Units = 10 |
Fig. 1 |
In the above figure, we see four customers each of whom has been granted a
number of credit nits. The banker reserved only 10 units rather than 22 units to
service them. At certain moment, the situation becomes
Customers | Used | Max | |
---|---|---|---|
A B C D |
1 1 2 4 |
6 5 4 7 |
Available Units = 2 |
Fig. 2 |
Safe State The key to a state being safe is that there
is at least one way for all users to finish.
In other analogy, the state of figure 2 is safe because with 2 units left, the
banker can delay any request except C's, thus letting C finish and release all
four resources.
With four units in hand, the banker can let either D or B have the necessary
units and so on.
Unsafe State Consider what would happen if a request from B for one more unit were granted in above figure 2.
We would have following situation
Customers | Used | Max | |
---|---|---|---|
A B C D |
1 2 2 4 |
6 5 4 7 |
Available Units = 1 |
Fig. 3 |
This is an unsafe state.
If all the customers namely A, B, C, and D asked for their maximum loans, then banker could not satisfy any of them and we would have a deadlock.
Important Note: It is important to note that an unsafe state does not imply the existence or even the eventual existence a deadlock. What an unsafe state does imply is simply that some unfortunate sequence of events might lead to a deadlock.
The Banker's algorithm is thus to consider each request as it occurs, and see if granting it leads to a safe state. If it does, the request is granted, otherwise, it postponed until later. Haberman [1969] has shown that executing of the algorithm has complexity proportional to N2 where N is the number of processes and since the algorithm is executed each time a resource request occurs, the overhead is significant.
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:
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.