Browse Prior Art Database

Algorithm for Variable Length Storage Allocation in a Circular Address Space

IP.com Disclosure Number: IPCOM000077440D
Original Publication Date: 1972-Jul-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 4 page(s) / 197K

Publishing Venue

IBM

Related People

Larson, LE: AUTHOR [+2]

Abstract

This algorithm, utilizing a circular storage concept and variable-length elements with pointers, provides distinct performance advantages over existing operating system (OS) allocation methods. Each new search for available space begins at the storage element following the storage element that ended the last search in the circular path. This method provides for fast allocation with a short search, and has the ability to deallocate without a search.

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

Page 1 of 4

Algorithm for Variable Length Storage Allocation in a Circular Address Space

This algorithm, utilizing a circular storage concept and variable-length elements with pointers, provides distinct performance advantages over existing operating system (OS) allocation methods. Each new search for available space begins at the storage element following the storage element that ended the last search in the circular path. This method provides for fast allocation with a short search, and has the ability to deallocate without a search.

Every element of space (portion of a page) in the circle has the same format as that shown in Fig. 1. The back pointer points back to the length field (L) of the previous element in the circle. The chain pointer points to the next element (either used/unused) in the circle. L is the length and takes on the various values: 0 - space is in use (or no space available). 1-127 - length of the space divided by 32. 125 (X'80') - used as a search "stop mark", it marks where the search began in the circular path, thus where it must end if sufficient space is not found to satisfy a request.

Before the function acquires any pages for suballocation, the only existing element is a dummy page as seen in Fig. 2. This is simply a starting point to make the algorithm work.

When the first page is added to the circular space, the pointers seen in Fig. 3.

Fig. 4A illustrates a simple circular path with two pages acquired for the function by two successive GETMAIN...