Browse Prior Art Database

Method for Queue Management

IP.com Disclosure Number: IPCOM000079853D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 6 page(s) / 166K

Publishing Venue

IBM

Related People

Costain, RP: AUTHOR [+3]

Abstract

Queue management is provided for a data-processing system having provision for interrupts to allow manipulation of a queue chain, without the necessity of disabling interrupts during manipulation. Information 10 is posted in the queue header 11, 12 of a queue element being manipulated in the chain by a low-priority task. A high-priority task may interrupt, but must inspect the queue header. Upon the header of that element containing the posted information, the high priority task must bypass that queue element and, if its operation affects that chain, repair the chain for the low-priority task prior to relinquishing control.

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

Page 1 of 6

Method for Queue Management

Queue management is provided for a data-processing system having provision for interrupts to allow manipulation of a queue chain, without the necessity of disabling interrupts during manipulation. Information 10 is posted in the queue header 11, 12 of a queue element being manipulated in the chain by a low-priority task. A high-priority task may interrupt, but must inspect the queue header. Upon the header of that element containing the posted information, the high priority task must bypass that queue element and, if its operation affects that chain, repair the chain for the low-priority task prior to relinquishing control.

For the purpose of illustration, the posted indicators are "00", indicating no enqueueing or dequeueing by the enabled task; "08", indicating that the enabled task is dequeueing; and "04", indicating that the enabled task is enqueueing.

The low priority enabled task operation to dequeue a queue element is illustrated in Figs. 1 and 2.

All queue chains begin from a queue header 11 having no associated queue element body. The initial header 11 forming the starting point for the queue chain is located in main storage at location "QSTART." The queue elements 13, 14, 15 are located at the symbolic main storage addresses "QEL A", "QEL B" and "QEL C", respectively.

The queue chain is defined by a series of pointers from one queue header to the following queue element. Thus, field 16 of queue header 11 includes the indicator 00 and a pointer QEL A to queue element 13.

The program code for a low priority enabled task to dequeue a queue element is entered at step 20. At the step 21, the pointer to QSTART, which is included in the instruction, is loaded to a general register. Step 22 sets the pointer of word 23 to all 0's. Step 24 then sets the indicator 10 of the same word to 08, to thereby indicate that a dequeue operation is to begin.

Step 25 reserves a portion of the chain to the low-priority task. Step 25 is a single, noninterruptable, move characters instruction. The instruction moves the characters comprising fields 16 and 23 to fields 26 and 16, respectively. The result of this step is illustrated by "time 2" in Fig. 2. The code 08 is now present in field 16. This code comprises an indicator to the high priority interrupting task, that the enabled task is in the process of dequeueing the queue element addressed in field 26. Steps 27 and 28 comprise the actual dequeueing of the queue element at address QEL A. Step 27 loads the address QEL A from field 26 to a general register.

The queue element is actually dequeued in step 28, which moves both parts of field 29 of header 13 to field 16 of header 11. This must be accomplished by utilization of the single move characters short instruction. Exit step 30 is then taken back to the low priority enabled task main code.

1

Page 2 of 6

The enqueueing process for a low priority enable task is illustrated by Figs. 3 and 4. As before, the header 11 i...