Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Deadlock Detector

IP.com Disclosure Number: IPCOM000088963D
Original Publication Date: 1977-Aug-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Related People

Hebalkar, PG: AUTHOR

Abstract

This article describes an apparatus in a CPU for detecting deadlocks between processes based upon serially reusable resources.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Deadlock Detector

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...