InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Detection of Queue Overflow in Decision Free Systems

IP.com Disclosure Number: IPCOM000083569D
Original Publication Date: 1975-Jun-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 2 page(s) / 44K

Publishing Venue


Related People

Henhapl, W: AUTHOR [+3]


A decision-free system is a finite set of procedures P(i), where 1

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

Page 1 of 2

Detection of Queue Overflow in Decision Free Systems

A decision-free system is a finite set of procedures P(i), where 1 </- i</- n, and a finite set of queues Q(i,k), where 1 </- j,k </- n. Each queue Q(j,k) has exactly one enqueueing processor P(j) and exactly one dequeueing processor P(k). Processor P(i) can switch its status from halt to busy when all queues Q(1,i), where 1 </-i </- n, are not empty. If the status of P(i) is switched from busy to halt, one message is enqueued to every queue Q(i,m), where 1</- m </- n.

The algorithm described is used to determine the maximum number of messages that are to be held in the various queues. Thus it computes the minimum queue lengths required for proper operation. The algorithm consists of the following steps: Step 1: Representation of the system by the 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 queue Q(i,k). Step 2: Evaluation of the transitive closure {t(i,k)} of {a(i,k)}, where t(i,k) is the minimum of all sums of the form (Warshall algorithm): a(i,j) + a(j(1), j(2)) + a(j(2), J(3)) + ... + a(j(1),k). Step 3: Evaluation of 1(i) = min ({t(k,i) | 1 </- k </- n and t(k,k) = 0}). Step 4: The number of messages in queue Q(i,k) is unlimited when t(k,i) and 1(i) is infinite, otherwise it is equal to a(i,k) + Example.

In the diagram below the initial state of a decision-free system is shown to illustrate the a...