Browse Prior Art Database

Double Indexed Priority Queue

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

Publishing Venue

IBM

Related People

Boggs, JK: AUTHOR [+4]

Abstract

A search through a multilevel list of active queues can be conducted efficiently in an adaptive priority sequence utilizing the following procedure.

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

Page 1 of 2

Double Indexed Priority Queue

A search through a multilevel list of active queues can be conducted efficiently in an adaptive priority sequence utilizing the following procedure.

In the illustration n positionally ordered queue element spaces (Fig. 1) represent the search targets. When an idle (dequeued) one of these spaces is activated (enqueued) the associated program (or system) sets a not shown hardware latch, to signal another program (or system) that information has been enqueued in one or more spaces. At the same time the associated program (or system) sets the activity bit in a pre-assigned byte of the n-byte priority mask (Fig.
2).

When the other (signaled) program (or system) detects the latch condition it "searches" the priority mask, four bytes at a time, for an "on" activity bit. Each four-byte segment of the priority mask is logically ANDed bit-by-bit with a locally stored four-byte search mask (Fig. 2), having 1's in bit positions ANDed with activity bits and 0's in all other bit positions.

Upon detecting an activity bit in "on" condition in any four-byte segment (i.e., a 1 product of logical ANDing) the signaled program (or system) branches on one of the "on" bits, in a predetermined priority order, to process the other seven bits of the respective byte of the segment. The other seven bits contain the address of an index entry (Fig. 3) for indirectly locating the respective (preassigned) queue element space. The index entry is combined with other...