Browse Prior Art Database

Deadlock Detection and Breaking

IP.com Disclosure Number: IPCOM000074660D
Original Publication Date: 1971-May-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 25K

Publishing Venue

IBM

Related People

Lum, J: AUTHOR

Abstract

In a shared resource multi-programming environment, a plurality of programs A-B compete for and use shared resources X' and Y'. Associated. with the respective resources are two-lock words X and Y. Each lock word contains a first bit L that when unset indicates the associated resource is free for use and which when set, indicates that the resource is in use. Each lock word also contains a pointer field for pointing to the program control block (PCB) of the program utilizing the resource.

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

Page 1 of 3

Deadlock Detection and Breaking

In a shared resource multi-programming environment, a plurality of programs A-B compete for and use shared resources X' and Y'. Associated. with the respective resources are two-lock words X and Y. Each lock word contains a first bit L that when unset indicates the associated resource is free for use and which when set, indicates that the resource is in use. Each lock word also contains a pointer field for pointing to the program control block (PCB) of the program utilizing the resource.

For each program, the supervisor program defines a unique PCB that allows a program to be interrupted and later continued at a later point in time. The PCB contains that information necessary to allow this interruption action to take place. It also contains an identification of the program and pointers chaining the PCB's in a sequence of priority ranging from high to low. The PCB's at the head of the chain have the highest priority. Each PCB also contains a resource queue field that is set to either 0 or to the address of the lock word associated with a resource requested by the program. In order for a program to utilize a resource, it issues a lock instruction indicating the lock word associated with the resource.

If the lock bit associated with the lock word is 0, indicating that the resource is available, then the lock word lock bit is set on and at the same time, the pointer field is changed to point to the PCB of the program. Thus, in the illustration, lock word X indicates that program D has acquired use of the resource. When a particular program has finished using a resource, it issues an unlock instruction specifying the resource lock word. The lock bit and the lock word pointer are reset to 0 only if the lock word pointer points at the "unlocking" program's PCB. In the event a higher priority program wants to use a resource that is already locked to some other program, the higher priority program becomes queued on that particular resource as by placing the lock word address in the associated PCB. At the same time, the using program is given the priority of the requesting program so as to cause it to run to completion, whereupon the resource can then be allocated to the higher priority program. The using programs priority is raised to that of the higher priority program by giving it control of the system. No rechaining of PCB's is required.

In such a system, a deadlock situation can occur. An example of a chain of events which can lead to the deadlock situation follows:

Assume initially that programs A-E are in the system but that none of these programs are utilizing...