Browse Prior Art Database

Resource Class Independent Deadlock Detection

IP.com Disclosure Number: IPCOM000046303D
Original Publication Date: 1983-Jun-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Obermarck, RL: AUTHOR

Abstract

This invention relates to an improvement in the method for detecting deadlocks in any one of a multiple of tasks, where the tasks are constrained to wait upon one or more tasks and, further, wherein resources are non-preemptively acquired by tasks from a resource class. The method was first described by Obermarck [*]. Obermarck observed that for all resource classes in which contention for the resource is allowed to suspend a task, there exists a "task-wait-for-task" relationship which can be described as a Boolean expression (logical AND/ORs). Central to the method is the logical inversion of the AND/OR task-wait relations, yielding thereby deadlock-resulting cycle information.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Resource Class Independent Deadlock Detection

This invention relates to an improvement in the method for detecting deadlocks in any one of a multiple of tasks, where the tasks are constrained to wait upon one or more tasks and, further, wherein resources are non- preemptively acquired by tasks from a resource class. The method was first described by Obermarck [*]. Obermarck observed that for all resource classes in which contention for the resource is allowed to suspend a task, there exists a "task-wait-for-task" relationship which can be described as a Boolean expression (logical AND/ORs). Central to the method is the logical inversion of the AND/OR task-wait relations, yielding thereby deadlock-resulting cycle information. The method steps included (l) obtaining the Boolean expression for each suspended task, defining which of the tasks satisfy the resource request for which the suspended task must wait, from each resource manager; (2) creating a directed graph with the nodes representing tasks and the edges representing the "task- wait-for-task" relationships from which elementary cycles are identified and listed; and (3) utilizing the elementary cycle list to supply a truth evaluation for the tasks on the right side of the logically inverted Boolean expressions, with the expressions then evaluated to ascertain whether the tasks on the left side are true (deadlocked) or not.

Where N is the size of the weighting subset, then a computation time of O(N2) is involved utilizing the above method. However, if the following modifications are taken with reference to steps 2 and 3, then the time may be reduced to O(NE), where E is the average number of tasks waiting on a task in the weighting subset. Wh...