# 22C:116, Lecture Notes, Mar. 3, 1995

Douglas W. Jones
University of Iowa Department of Computer Science

Recall the basic notion of a wait-for graph

```           _                      _
(_)------------------->(_)
process     waits    message from
for       process
_                      _
(_)------------------->|_|
process     waits      resource
for
_                      _
|_|------------------->(_)
resource    waits     release by
for       process

```
In 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          ^     |
_     |     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.

2. Limitations of all formal deadlock models

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!