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.