Browse Prior Art Database

Best Fit Algorithm for SQA Storage Management

IP.com Disclosure Number: IPCOM000079099D
Original Publication Date: 1973-May-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 80K

Publishing Venue

IBM

Related People

Skidmore, FH: AUTHOR

Abstract

A best fit algorithm is provided for System Queue Area (SQA) storage management. The SQA of main storage contains system control blocks required to supervise control of system resources. When the SQA is first initialized by the Nucleus Initialization Program (NIP), a descriptor queue element (DQE) is created at the low end of the SQA containing the starting address of the SQA, its length and a pointer to a free queue element (FQE). The FQE initially contains the length of the SQA minus the space used by those control blocks set up by NIP. As storage is allocated and freed, additional FQEs are created to describe free areas, which are noncontiguous with other previously freed areas as illustrated above.

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

Page 1 of 2

Best Fit Algorithm for SQA Storage Management

A best fit algorithm is provided for System Queue Area (SQA) storage management. The SQA of main storage contains system control blocks required to supervise control of system resources. When the SQA is first initialized by the Nucleus Initialization Program (NIP), a descriptor queue element (DQE) is created at the low end of the SQA containing the starting address of the SQA, its length and a pointer to a free queue element (FQE). The FQE initially contains the length of the SQA minus the space used by those control blocks set up by NIP. As storage is allocated and freed, additional FQEs are created to describe free areas, which are noncontiguous with other previously freed areas as illustrated above.

In storage allocation based on a "First Fit" algorithm, when a storage request is made, a search of the FQE queue is made in descending address order by comparing the size of the request with each succeeding FQE, until the first FQE is found defining free-storage area available to satisfy the request. When such a free area is found, the search is terminated, the area is allocated and the FQE modified to reflect the reduction of available free storage area. This algorithm while satisfactory is somewhat inefficient, especially where the requests of a given size are nearly equal to the freed areas for that size. The "Best Fit" algorithm takes advantage of this situation to better the management of available storage.

In the "Best Fit" algorithm, once a storage request has been identified as a SQA request, the search of the FQE queue is initiated in descending order. The first FQE is examined to determine whether there is a block of free space associated therewith and, if so, whether it is large enough to acc...