Browse Prior Art Database

Algorithm for Detection of System Deadlocks

IP.com Disclosure Number: IPCOM000090860D
Original Publication Date: 1969-Jul-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 3 page(s) / 51K

Publishing Venue

IBM

Related People

Collier, WW: AUTHOR

Abstract

Three sets P, F, and H are used in the deadlock scan. The set P consists of the programs which have already been examined to see which other programs, if any, the programs in P have to wait for. The set F consists of programs which hold or will hold resources requested by one or more programs in P. The set H contains the programs which hold or will hold resources requested by a single program from the set F.

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

Algorithm for Detection of System Deadlocks

Three sets P, F, and H are used in the deadlock scan. The set P consists of the programs which have already been examined to see which other programs, if any, the programs in P have to wait for.

The set F consists of programs which hold or will hold resources requested by one or more programs in P. The set H contains the programs which hold or will hold resources requested by a single program from the set F.

For each problem program there is a Program Control Block PCB. For each resource there is Resource Control Block RSB. For each request for a distinct resource there is a Request Control Block RQB.

These control blocks and the fields within them relevant to a deadlock search are shown in drawing A.

Within the PCB the FLINK field is used solely by the PSH and POP operations. The REQORG field is the origin of a queue of RQB's. This queue contains one RQB for each outstanding request, whether satisfied or not, for a resource. The PWORD field has a value equal to the current value of CTR if the program corresponding to the PCB has been placed in the set P. The FWORD field has a value equal to the current value of CTR if the program corresponding to the PCB is currently in the set F. A PCB in the set F is also enqueued through the FLINK field on the queue beginning at FORG.

In the RSB there are, in addition to the identification of the resource itself, two queue origins. The WNTORG field is the origin of a FIFO queue of RQB's. Each RQB is linked to a PCB for a program which has requested, but not yet obtained, the resource identified in the RSB. The HAVORG field is the origin of a second queue of RQB's. Each RQB on this queue is linked to a PCB for a program which has already been assigned the resource identified in the RSB. This queue normally consists of only a single element. It can consist of more when several programs can simultaneously and nondestructively access the resource.

The HLINK field in the RQB is used by the PSH and POP operations to enqueue and dequeue RQB's on the queue originated at HORG. Being enqueued on this queue is equivalent to being a member of the set H. In the implementation, the set H consists of RQB's rather than PCB's. The PCBLNK field is used for linking together the RQB's for a given program. The queue origin is in the REQORG field of the PCB for the given program. This PCB is identified by the PCBADR field within each RQB. The RSBLNK field is used for linking together the RQB's which represent requests for the same resource. The origin of this queue is in either the WNTORG or HAVROR fields of the RSB for the reques...