Deadlock detection using (0,1)-labelling of resource allocation graphs

Abstract

A deadlock detection method based on the use of the resource allocation graph is presented. The method is different from the existing deadlock avoidance techniques in that the original directed resource allocation graph is first transformed into an undirected (0 1)-labelled graph in which the deadlock would occur only if a cycle has been labelled alternatingly with 0s and 1s. The algorithm is applicable to the centralised and distributed systems. Another feature of the algorithm is that it call be used in distributed systems, since the detection of deadlock is carried out by an interprocess communications which is basically the er;change of 0 and 1 bits among the processes. The worst case cost of the algorithm is O(e), which is low enough to run it at the background of the operating system.