Browse Prior Art Database

FIFO Queue Management Technique

IP.com Disclosure Number: IPCOM000084601D
Original Publication Date: 1975-Dec-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 5 page(s) / 50K

Publishing Venue

IBM

Related People

Duke, AH: AUTHOR

Abstract

A data storage queue management technique is described which simplifies the management of a first-in-first-out (FIFO) queue by eliminating a serially reusable resource from the logic, by reducing the number of pages required for the queue and by reducing the number of storage references necessary to handle the queue, even when elements other than the earliest enqueued element must be dequeued.

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 5

FIFO Queue Management Technique

A data storage queue management technique is described which simplifies the management of a first-in-first-out (FIFO) queue by eliminating a serially reusable resource from the logic, by reducing the number of pages required for the queue and by reducing the number of storage references necessary to handle the queue, even when elements other than the earliest enqueued element must be dequeued.

The technique described herein is related to the techniques described in the following technical articles: "Storage Allocation Mechanism", IBM Technical Disclosure Bulletin, Vol. 17, No. 9, February 1975, pages 2606-2610; and "Set Management Technique", IBM Technical Disclosure Bulletin, Vol. 18, No. 7, December 1975, pages 2124 to 2130. It is assumed herein that the reader is familiar with these related technical articles.

The technique described herein and the above-referenced related techniques each represents an application of an efficient bit scanning mechanism for scanning bit strings and bit masks. The referenced storage allocation technique uses the bit scanning mechanism to maintain a list of free storage space elements. The referenced set management technique uses the bit scanning mechanism to maintain two complementary sets of items in a storage space, one set being a list of free storage elements and the other being a list of storage elements used for some desired purpose. The technique described herein uses the bit scanning mechanism, as well as other features of the two related techniques, to maintain a FIFO queue and the list of free storage elements that may be used in the FIFO queue.

Fig. 1 illustrates the storage organization for an exemplary case of a FIFO queue constructed in accordance with the technique described herein. The storage space in question is divided into many pages of the same fixed size and each page is subdivided into a fixed number of equal size element spaces. Each element space is capable of holding the same fixed number of data bytes, a byte being the smallest unit of addressable storage in the system.

In the Fig. 1 example, three such storage pages are shown. In forming the FIFO queue, these pages are linked together so as to form a closed loop or endless chain. As indicated by the linkage arrows, the linkage progresses in one direction only, as opposed to earlier queue techniques where both forward and reverse linkages were provided.

When first established, the FIFO queue is initialized to contain two pages. Additional pages are automatically added as needed. Thus, Fig. 1 shows the situation existing after one additional page has been added.

At the bottom of each page, there is located a control field which includes a CONTROL MASK field, a NUMBER ENQUEUED field and a NEXT PAGE field. The CONTROL MASK field contains one bit position for each element space on the page. A given mask bit in this field is set to a value of 0 if the corresponding element space is free or not...