Concurrent and Distributed Systems

11/20/2019 Design of Multithreaded Software - Chapter 7: Simultaneous exclusive access to multiple resources

file:///Users/doza/Desktop/Design of Multithreaded Software - Chapter 7_ Simultaneous exclusive access to multiple resources.htm 1/1

This diagram shows that one instance of type X may be holding R1 and waiting for R2 while another holds R2 and waits for R3. If an entity of type X attempts to acquire R3 while still holding both R1 and R2, then R1 and R2 and the arrow between them are enclosed in a box:

The box with the arrow to R3 indicates that an entity of type X holds both R1 and R2 while waiting for R3. The reason for the special notation is that only a single entity of type X is involved, first in a situation where it holds R1 and waits for R2 and then in one where it’s waiting for R3 while holding both R1 and R2. If there is circularity in the wait-chain diagram, a potential for deadlock exists. There is circularity if we can start at some resource node R1, follow an arrow to another node, then a third, and ultimately get back to R1 while moving in the direction of the arrows. Deadlock can exist only if there are enough entities to populate the wait chain, however. We can find out how many entities are needed by counting the arrows. In the diagram below, it takes two arrows marked X and one arrow marked Y to get from node R1 back to R1. That means that it takes two entities of type X and one of type Y to cause deadlock. If an arrow from a box is included in the count, then the arrows inside the box aren’t counted.

Here is a wait-chain diagram for the intersection example:

It’s obvious from the diagram that four entities of type V can deadlock. There are no boxes because no vehicle holds more than a single quadrant of the intersection at once. Figure 7-2 shows a wait-chain diagram of a schematic program with two task types, S and T. Each acquires resources A, B,… by means of calls such as A.acquire and B.acquire. That is, by making the call A.acquire, the task attempts to acquire A. This may involve a wait. While waiting, the task holds onto whatever resources it has already acquired and not yet released. Upon return from the call A.acquire, the task has exclusive access to A, which it releases by calling A.release.

200