Browse Prior Art Database

Detection of Deadlocks in Decision Free Systems

IP.com Disclosure Number: IPCOM000081656D
Original Publication Date: 1974-Jul-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 62K

Publishing Venue

IBM

Related People

Henhapl, W: AUTHOR [+2]

Abstract

The described algorithm effectively detects the occurrence of deadlock situations in decision-free systems, and evaluates the number of transactions of any processor involved up to its deadlock.

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

Page 1 of 3

Detection of Deadlocks in Decision Free Systems

The described algorithm effectively detects the occurrence of deadlock situations in decision-free systems, and evaluates the number of transactions of any processor involved up to its deadlock.

A decision-free system is a finite set of processors P(i), where 1 </= i </= n, and a finite set of queues Q(j,k), where 1 </= j, k </= n. Each queue Q(j,k) has one enqueueing processor P(j) and one dequeueing processor P(k). A processor P(i) is switched from busy to halt, a message is enqueued to every queue Q(i,m), where 1 </= m </= n.

The following algorithm determines whether a processor P(i) can switch its status any number of times or not. In the latter case, the algorithm evaluates the number of possible switches until the occurrence of a deadlock situation.

The algorithm consists of the following steps:

Step 1: Representation of the system by matrix a(i,k), where 1 </= i, k </= n and a(i,k) is equal to infinity

if there is no queue Q(i,k), or a(i,k) is equal to the

number of waiting messages in the queue Q(i,k).

Step 2: Evaluation of the transitive closure t(i,k) of (Warshall a(i,k), where t(i,k) is the minimum of all sums of Algorithm the expression a(i,j(1)) + a(j(1)),(j(2)) + a(j(2)),(j(3)) + ... +

a(j(1),k)

Step 3: P(i) can switch any number of times if there is no k with t(k,k) = 0, and t(k,i) < infinity. P(i) can

switch from halt

to busy at most N-times if N is the minimum of all

t(k,i), where 1 </= k </= n and...