Browse Prior Art Database

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

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

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)