Original Publication Date: 1977-Aug-01
Included in the Prior Art Database: 2005-Mar-04
This article describes an apparatus in a CPU for detecting deadlocks between processes based upon serially reusable resources.
This article describes an apparatus in a CPU for detecting deadlocks between processes based upon serially reusable resources. The apparatus comprises a m x m matrix of row and column conductors, wherein the ith row and column is associated with a resource and 0 < or = i < or = m-1; m(m-1) switching elements for directionally coupling each row to each column conductor except along the principal diagonal; m detectors capable of selective enablement terminating corresponding columns; m external paths, each path directionally coupling correspondingly the ith column to the ith row; and means for applying at least one pulse to at least the ith row indicative of a new process waiting to utilize the resource associated with the ith row/column conductors; whereby a pulse may be detected on the ith column if there exists a circuit of dependencies among the resources effected by the processes.
This apparatus is premised on the fact that:
a) a resource (whether in use or not) need not be represented in a dependency graph until a process holding it has to wait for another resource, and
b) if deadlock detection is carried out every time a process has to wait for a resource, only possible circuits involving the latter resource need be investigated.
The apparatus comprises a square matrix, similar to a diode decoding matrix, with each column line reconnected to its matching row line in a directional manner as shown in the figure. At the intersection of a row line and a column line is a switchable device diode symbol that can be made conducting or nonconducting based on a trigger signal. On each column line is a "listener", i.e., a pulse detector.
The matrix is operationally e...