Deadlock occurs when two or more processes are blocked, where each process is blocked awaiting some action by another blocked process.
A process might be blocked awaiting a message from another process, or it might be blocked awaiting a resource currently held by another process. If all the processes in a deadlocked group of processes are blocked awaiting messages, the deadlock is described as a communication deadlock; if all processes in a deadlocked group are awaiting resources, it is a resource deadlock. Mixed cases where some processes in the group are awaiting resources and others are awaiting messages are quite possible.
In either case, whether resources or messages (or both) are involved, the key is that there is a cyclic wait.
In some older texts, the possibility of message passing is completely ignored, and deadlocks are defined entirely in terms of resource contention.
Deadlocks resulting from resource allocation have been widely studied since the late 1960's. Three distinct issues have been raised in this context:
Since a deadlock involves is a cycle of processes waiting for something, the standard algorithms for deadlock detection convert the problem into graph theoretic terms and then use various cycle finding algorithms on the resulting graph.
The following notation is traditionally used in graph theoretic formulations of the deadlock detection problem:
Allocated Process that
resource has the resource
_ _
|_|------------->(_)
Waiting Resource the
process process waits for
_ _
(_)------------->|_|
Waiting Process that
process should send message
_ _
(_)------------->(_)
The graph has vertices for each process (round) and resource (square).
The graph has edges representing the "waits for" relation. A process
can wait for a resource, a resource can wait to be released by a
process, and (in message passing systems) a process can wait for a
message from some other process. The latter is a modern extension
to this old notation.
Here is an example "wait for graph" describing 4 processes, A, B, C and D, and 4 resources, Y, Y, Z and W. A is waiting for X, but B has both X and Z. C has W and is waiting for Y, and D has Y and is waiting for W. Does a deadlock exist?
Processes Resources
_ _
A(_)--------->|_|X
___/
_ / _
B(_)<=== ->|_|Y
\/ __/
_ _____/\/ _
C(_)<-- /\__|_|Z
\/
_ /\____ _
D(_)<-- -->|_|W
\_____/
There is a deadlock involving processes C and D and resources W and Y.
Detecting a cycle in a graph involves traversing the cycle! Thus, the cost of deadlock detection is related to the number of vertices in the cycle, which could be as large as the number of vertices in the graph. As a result, deadlock detection algorithms scale poorly growing in expense as the system grows in size.
As long as a the only wait operations involve processes waiting on resources, the deadlock graph is formally a bipartite graph, that is, a graph where there are two sets of vertices (round and square, here), and where all edges either connect a vertex in one set with a vertex in the other. If processes may wait for messages, the graph is not bipartite, but this has no effect on the relevant algorithms.
In the previous section, we only focused on a subset of the possible wait-for graphs! To understand this, it is appropriate to look at the different classes of wait-for graphs and how these relate to constraints on the systems they model.
The simplest category of systems are those that enforce a single resource model. These allow only one outgoing edge per node in graph. If a process is waiting, it is waiting for a message from a particular sender, or it is waiting for a particular resource, or both; furthermore a resource can be allocated to at most one process.
In this case, detecting deadlocks is trivial because following the path formed by outgoing edges from a blocked node in the graph will lead directly back to that node in a number of computational steps proportional to the length of the cycle, and there are never any branches in the path!
The next most common category of wait-for graphs are those that enforce an and-model These allow many outgoing edges per node in the graph. A waiting process will resume only when all outgoing edges are deleted. This allows one process to await the availability of multiple resources, but most formulations do not allow a resource to be simultaneously allocated to multiple processes. Here is an example:
+ * + -
_ _ _ _ _
(_) (_) (_)->(_) (_)
^^ /|^ |^ O |\ ^
| \/ | \ | \ | \ |
| /\ | \ | \ | \ |
|v \v \v \v v|
|_| |_| |_| |_| |_|
- - + + +
In the above and-model wait-for graph, there is a deadlock in the
cycle surrounding the letter O. If the search for a deadlock finds
all paths of length two rooted at the node marked with a star before
it investigates paths of length three, it will visit all nodes
marked with a plus before it finds the deadlock. Nodes at distance
three from the node marked with * are marked with a minus and are
likely to be visited in the process of finding the deadlock.
A deadlock in such a graph is still determined by the presence of a cycle, but it is no longer a simple cycle to find. The algorithms for finding cycles in such a graph are likely to visit large numbers of nodes that are not on the deadlock cycle, and thus, the computational cost of such algorithms is no longer porportional to the length of the cycle.
Another category of wait-for graphs are those that enforce an or-model. These are also known as communication-model wait-for graphs, because many interprocess communication systems are based on this model. Or-model graphs allow many outgoing edges per node in the graph, but they are not interpreted in the same way as and-model graphs.
In an or-model, a waiting process will resume when it receives any one of the resources for which it is waiting or a message from any one of the processes it is willing to listen to. As a result, as illustrated below, cycles no-longer imply deadlock.
_ _ _ _
(_)-->(_) (_)-->(_)
^ | not a ^ |
| | deadlock | | deadlock
_ | v | v
(_)<--(_)<--(_) (_)<--(_)
A W
In the above example, the left graph is not deadlocked because
the process marked W may receive a message from the process marked
A, which is not blocked. Once process W receives this message, it
is no-longer waiting (all outgoing edges are deleted!).
In an or-model wait-for graph, the mere presence of a cycle does not signify a deadlock. Instead, a deadlock requires what is called a knot in graph theory. Algorithms to detect knots are more complex than algorithms to detect cycles.
Formally, a knot in a graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot have other vertices in knot as destinations.
The algorithm for asking if a vertex is part of a knot begins with that vertex as the root of a traversal of the directed graph. If, during that traversal, any vertex with no outgoing edges is found, the vertex in question is not part of a knot.
Unfortunately, the model most applicable to real systems is a mixed and-or model of wait-for-graph, where the and-model is used for resource allocation and the or-model is used for interprocess communication.
Worse yet, in real systems, when a process awaits a message from another process (for example, when a process does a wait operation on a semaphore), there is no way for the system to know which process might eventually send the required message (which process will signal the semaphore). Thus, in practice, deadlocks are frequently not detectable until all processes in the system are blocked!
Basic graph algorithms are a standard part of undergraduate courses on data structures!
A graph consists of a set of vertices (processes and resources, in our example), and a set of edges (the arrows connecting processes and resources in our example). In general, edges need not have direction associated with them, but in our example application, we are only interested in directed graphs, where edges have direction.
Many of the basic questions we will need to resolve about graphs rest on the same basic meta-algorithm for graph traversal:
Initially, all vertices and edges are unmarked
R is a some vertex, to be used as the root
Mark R
S = { R }
Repeat
Remove a vertex V from S
For each V' reachable from V,
If V' is not marked
mark V'
put V' in S
mark the edge <V,V'>
endif
endfor
Until S is empty
At any point during the execution of this meta-algorithm, the set S
contains the vertices "on the frontier" of the graph being explored.
Marked vertices that are no-longer in S have been fully explored, while
unmarked vertices not yet in S remain to be visited.
If S is managed on a LIFO basis, this algorithm performs a depth-first traversal of the graph, following the longest possible path from the root before returning to visit other parts of the graph. If S is managed on a FIFO basis, this algorithm performs a breadth-first traversal of the graph, visiting all vertices reachable from vertices already in S before visiting others beyond them.
The set of marked edges produced by this algorithm is a tree that spans every vertex in that part of the graph reachable from the root vertex R. That is, it is a spanning tree of the reachable part of the graph. Not all parts of all graphs are reachable from any vertex, so this is not always a spanning tree of the whole graph. Note that, depending on the traversal scheme used (that is, depending on the management of the set S) many different spanning trees can be produced by the same meta-algorithm.
NOTE: Other variants on the above metaalgorithm will show up repeatedly in the remainder of this course! The subject of spanning trees will also show up again and again!
Given a directed graph rooted at vertex R, it is not hard to modify the depth-first recursive tree traversal algorithm to traverse the graph and search for cycles. The modified algorithm only marks those edges and vertices on the path from the root to the leaf currently being examined -- thus, as it follows a path through the tree, it marks edges and vertices, and as it backtracks in its traversal, it unmarks edges and vertices. If this modified algorithm ever encounters a marked vertex as it walks deeper into the graph (as opposed to encountering such a vertex on backtracking), it has found a cycle reachable from the root R.
Once a deadlock is detected, what should be done? The classic solution is to break the cycle by aborting a process in order to free its resources. This is only applicable to systems using a resource model!
What process should be aborted? The obvious answer is to abort the least important process, but this requires a ranking of processes by importance. Process priority, for those operating systems that support such a notion, may or may not relate to importance.
An alternative is to return an error code on the resource allocation request that would have led to a deadlock. If the application is unprepared to deal with this error, it may be aborted, but note that this may mean that the wrong process is aborted, since the last process to join a deadlock cycle need not be the least critical process in the cycle. If a process can be coded to anticipate the possibility of allocation failures, this alternative can be quite useful.
The classic solution is clearly not oriented towards communication deadlocks! Furthermore, aborting a process is hard on critical applications, where less drastic solutions are desirable.
In deciding which process to abort, it is common to abort the process that was the last one added to the cyclic wait -- that is, the one that closed the cycle. This is not aloways the right choice, since the order in which processes join a deadlock is unrelated to the amount of damage that would be caused by aborting the processes.
Ideally, the process to be aborted should be the one where that act will cause the least damage, that is, the least critical process. Few systems provide information sufficient to determine how critical a process is, however. The common alternative of aborting the process with the lowest priority approximates this, since high priority processes are frequently more critical than low priority processes, but this isn't necessarily so.
Communications deadlock cannot be resolved by aborting a process! Aborting all processes in the deadlocked group is possible, of course, but it is hardly desirable, especially if fault tolerance is one of the system goals.
In a fault tolerant system, when a communications deadlock is detected, an appropriate action to take would be to break the deadlock by sending an error message to one of the waiting processes or by causing the call to Receive to return an error code or raise an exception instead of blocking forever awaiting a message that will never arrive.
There is a trivial solution to the problem of deadlock avoidance in a pure resource allocation context: All you need to do is prohibit processes from incrementally allocating resources. If a process is required to allocate all of its resources at once, with the simple rule that it either gets everything it wants or nothing at all, resource deadlocks are not possible.
This trivial solution has been widely used, particularly back in the days of batch operating systems taking input from a stream of punched card. These systems typically required each process to declare all resources it might want as a field of the job card -- the head card on the card deck. This is clumsy, and it requires that the process hold all resources it might need for the duration of its run even if it only needs some of them briefly.
Claiming Resources in a Strict Order Prevents Deadlock
A less trivial solution to the deadlock problem is to require that all resources be acquired in a strictly predetermined order. For example, any process that requires both the modem and the laser printer must acquire the modem first and the printer second. As long as this rule is enforced, it will be possible to guarantee that the system is deadlock free with regard to these two resources because it will be impossible for one process to claim the modem and then request the printer while the other claims the printer and then requests the modem.
It is always possible to impose a total ordering over all resources. Any ordering will suffice, so long as all processes adhere to it. For example, resources may be ordered in alphabetical order by resource class, and then in numerical order, within each resource class, by resource address. Many applications can be rewritten to comply with such an ordering constraint, but many others cannot.
In a banking system, for example, we might require that the records for different bank accounts be claimed in the order of the account numbers. In payroll systems, the employee ID number might be used similarly. So long as we know in advance the account numbers or ID numbers of the different records we need to lock, we can lock them in numerical order in order to guarantee freedom from deadlock.
Of course, there are many situations where we cannot know the identity of some of the items we will have to lock until we have locked and inspected other items. When this is the case, this deadlock avoidance method is not applicable.
In the early 1970's, Dijkstra described a general deadlock avoidance algorithm, applicable in any resource allocation context. He called this the banker's algorithm, and he formulated it in terms of a bank with many customers taking out loans. In this context, a deadlock occurs when the bank's funds are exhausted and no customer can repay a loan because all are blocked awaiting additional money they need in order to complete their business.
Each customer has
Ai, the amount of money currently borrowed
Li, the credit limit (the maximum the bank will loan)
The bank begins with a total of
C the total money supply in this closed economy
The bank is not in immediate danger if:
C-(sumi Ai) > (mini Li-Ai)
The left side of the above relation represents the cash on hand
in the bank. The right side indicates the maximum additional loan that some
particular customer may request, where that customer is the closest to his
or her credit limit of all customers of the bank.
As long as the above inequality holds, some bank customer will be able
to borrow enough money to reach his or her credit limit.
For many customers, it may be necessary to borrow more money before they can begin to repay any, but no customer will need to borrow more than their limit before being able to start repaying. Thus, as long as some customer can borrow to the limit, that customer will be able, eventually, to repay their loan, and therefore, eventually, the bank will get enough money back from that customer to allow some other customer to begin making repayments.
Dijkstra showed that a system is in a safe state, that is, in a state guaranteed to not lead to deadlock, if the state resulting from the customer with the minimum Li-Ai repaying their loan is also safe. This is an inductive definition of a safe state, and the natural statement of the algorithm to detect safety is therefore recursive. This inductive definition of safe system states rests on the observation that the initial state, when the bank has all of the cash, is inherently safe as long as no customer has Li greater than the total available money supply.
Given an algorithm to determine if the system is safe, we can simply deny any request to adjust the credit limit of a user that would put the system into an unsafe state, and we can simply block any allocation request that puts the system into an unsafe state.
As long as processes have a finite lifetime after which they deallocate everything they hold, Dijkstra proved that this scheme guarantees that such blocking will never lead to deadlock.
Effectively, before granting any loan request, the Banker must ask not only "Do I have this money on hand?" but also, "Will I have enough left to allow someone to borrow to their limit, and if they did so and repaid their entire loan, would I have enough to let some other customer do the same, and so on?" If not, the banker must tell the customer to wait.
Resource deadlocks are frequently the result of waiting for specific resources that are not interchangable with others or that are in limited supply. Thus, the severity of the resource deadlock problem can be significantly reduced by eliminating non-interchangable resources and by providing a larger supply of resources.
As an example of this, note the effect that virtual memory has had on the frequency of memory related deadlocks in real systems. In systems developed prior to the availability of virtual memory, such deadlocks were fairly common, but with the introduction of massive virtual address spaces, conflicts over the allocation of specific locations in physical memory have been greatly reduced. The page-frame management software in the virtual memory manager must deal with this possibility, but no other part of the system needs to worry about this.
Another example shows up in the area of input-output channels. When users directly deal with line printers and modems, allocation of such resources is a common source of deadlock. With the introduction of print spoolers, though, a system has multiple virtual printers multiplexed by the spooler onto one physical printer, and printer allocation is no-longer a source of deadlock. Similarly, using protocols like SLIP, multiple applications can share the same modem and use it as a link to multiple remote network resources.
Most operating systems do not include deadlock detection mechanisms. They rely on simple avoidance schemes to avoid deadlocks that are the fault of the system, and they leave users entirely responsible for avoiding deadlocks at the application level. Database management systems sometime actively detect and resolve deadlocks, or avoid them, but frequently, the solution is simple -- deadlocks are declared when a process waits too long for a lock, and then, the transaction in process is simply aborted to resolve the deadlock.