Operating Systems: Concurrent and Distributed Software Design

18.6. Object allocation graphs

Figure 18.4 shows a graphical notation for describing object allocations and requests. The graph shows object types R1 and R2. The dots inside the R1 and R2 boxes indicate the number of objects of that type that exist. The directed edge from the single instance of R1 to process P indicates that P holds that object. The (dashed) directed edge from P to the object type R2 indicates that P is requesting an object of type R2. P is therefore in the blocked state. If a cycle exists in such a graph and there is only one object of each of the object types involved in the cycle then deadlock exists (this is the definition of deadlock). If there is more than one object of each type a cycle is a necessary but not sufficient ...