Browse Prior Art Database

Queue Structure for a Virtual Storage Environment

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

Publishing Venue

IBM

Related People

Wescott, JL: AUTHOR

Abstract

A data storage queue structure is described which is especially designed for use in a virtual storage data processing system, for enabling queuing operations to be performed with a minimum of page traffic back and forth between main storage and auxiliary storage. This queue structure also provides an efficient mechanism for dynamically expanding and contracting the queue space with queue load requirements.

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

Page 1 of 4

Queue Structure for a Virtual Storage Environment

A data storage queue structure is described which is especially designed for use in a virtual storage data processing system, for enabling queuing operations to be performed with a minimum of page traffic back and forth between main storage and auxiliary storage. This queue structure also provides an efficient mechanism for dynamically expanding and contracting the queue space with queue load requirements.

Virtual storage systems provide an opportunity to economically migrate data items and structures from slower auxiliary storage to faster, more accessible main storage. However, erratic, uncontrolled access of these items can cause excessive virtual storage paging activity, which negates any performance benefits gained by the migration. This is especially true of structures, such as queues, whose physically discontiguous elements are made to appear logically contiguous through chaining techniques. The operations of scanning the queue and adding and removing elements can cause these performance problems.

The queue structure described herein uses a modified indexed chaining technique which is especially designed to minimize these problems. As indicated in Fig. 1, the major components of this queue structure are a queue space which contains the queued data, an index which contains information about and pointers to the queue space, and an index header which points to the index.

The queue space is structured into fixed size allocation units (AUs). AUs are the entities by which the space is expanded and contracted. Their size is specified as a constant at queue creation time. Allocation units, in turn, are divided into segments. These segments are sensitive to areas of virtual storage (pages) which may not be contiguous in main or real storage. Their sizes are variable, responding to the page boundaries within the AU. A segment never appears on more than one virtual storage page, thus assuring that access to any area of it will never cause more than one page fault.

The index connects all the segments in the queue space into a logically contiguous space. Each index entry, in addition to pointing to a queue segment, contains information about the segment, such as the queuing criteria of the queued data in the segment, an identifier of the AU to which the segment belongs, and space-related information to be used in the manipulation of the queue.

It is important to note that the allocation unit resides in contiguous virtual storage which is broken into blocks (segments) of contiguous real storage. The index binds the segments into a logically contiguous queue space.

Index entries may be either in use, i.e., associated with a segment, or reserved (marked "free") for segments which will be added when the queue is expanded. Each type forms a chain originating from the index header. The active chain may be manipulated such that an entire queue segment can be repositioned relative to other segme...