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.
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 cash on hand. The bank is not in immediate danger if: R-(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 any one borrower is entitled to request. 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.
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 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.
Recall the basic notion of a wait-for graph
_ _ (_)------------------->(_) process waits message from for process _ _ (_)------------------->|_| process waits resource for _ _ |_|------------------->(_) resource waits release by for processIn the previous lecture, we 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 WIn 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!
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.