Browse Prior Art Database

Deadlock/Interlock Detection

IP.com Disclosure Number: IPCOM000079869D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 21K

Publishing Venue

IBM

Related People

Roever, PR: AUTHOR

Abstract

An interlock/deadlock detection algorithm utilizing global bit matrix manipulations is described. A square-bit matrix is introduced showing just the wait dependencies between tasks. A characteristic of such a matrix is that if there is any submatrix with only nonzero rows and columns, then the submatrix would describe a set of tasks waiting on themselves. The determination of the existence of such a submatrix is accomplished by simple, logical operations against the bit matrix.

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 54% of the total text.

Page 1 of 3

Deadlock/Interlock Detection

An interlock/deadlock detection algorithm utilizing global bit matrix manipulations is described. A square-bit matrix is introduced showing just the wait dependencies between tasks. A characteristic of such a matrix is that if there is any submatrix with only nonzero rows and columns, then the submatrix would describe a set of tasks waiting on themselves. The determination of the existence of such a submatrix is accomplished by simple, logical operations against the bit matrix.

In the following, a scheme is described, which yields the same results by global matrix manipulations. This method is, in most cases, more efficient, because it is less dependent on the number and relative position of the matrix entries.

Specifically, a square-bit matrix is introduced to show just the wait dependencies between tasks. (A 1 bit in row 5 and column 2 for instance, would indicate that task 5 is waiting for control of one or more resources currently held by task 2.)

By definition, a deadlock (also called interlock) has occurred if a set of tasks n(1), n(2), ... n(r), r>1) are related such that: task n(1) waits on task n(2)

task n(2) waits on task n(3)

task n(1-r) waits on task n(r)

task n(r) waits on task n(1).

In the above-mentioned matrix, this would show up as a submatrix consisting of rows and columns n(1), n(2), ... n(r), none of which are empty. On the other hand, if there is any submatrix with only nonzeros rows and columns, then obviously the submatrix would describe a set of tasks waiting on themselves. In other words: If a bit matrix showing wait dependencies is given, then deadlock detection is equivalent to the detection of a submatrix with all rows and columns being nonzero. Whether or not there is such a submatrix can be determined by simple logical operations against the bit matrix.

Let D(o) be the bit matrix to be checked for deadlock. From D(o) derive intermediate matrices X(o) and Y(o) such that the elements Xij of X(o) are defined as

(Image Omitted)

and Y(o) is the transpose of X(o) (Yij = Xji). X(o), therefore, has nonempty rows and columns where D...