Browse Prior Art Database

Efficient Management of Fixed-Length Storage Elements

IP.com Disclosure Number: IPCOM000034200D
Original Publication Date: 1989-Jan-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Ernsberger, WG: AUTHOR

Abstract

One common type of storage management is the allocation and deallocation of fixed-length elements of storage from a preallocated pool of such elements. A last-in, first-out (LIFO) algorithm is generally used to allocate these blocks to requestors - the last element returned being the element used to satisfy the next request. This is often implemented by chaining all currently unallocated elements into a list. Allocation is achieved by removing the first element from the head of the list, while deallocation is achieved by adding the returned element to the head of the list. While this method is very simple and pathlength efficient, it causes real storage to be used inefficiently in operating systems having demand-paged virtual memory.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Efficient Management of Fixed-Length Storage Elements

One common type of storage management is the allocation and deallocation of fixed-length elements of storage from a preallocated pool of such elements. A last-in, first-out (LIFO) algorithm is generally used to allocate these blocks to requestors - the last element returned being the element used to satisfy the next request. This is often implemented by chaining all currently unallocated elements into a list. Allocation is achieved by removing the first element from the head of the list, while deallocation is achieved by adding the returned element to the head of the list. While this method is very simple and pathlength efficient, it causes real storage to be used inefficiently in operating systems having demand-paged virtual memory. After a system with this algorithm has been running for a while, the set elements that are currently allocated (and therefore are presumably being referenced) tend to be randomly scattered throughout the set of elements that were ever allocated since the system was initialized. This generally means that all virtual pages that these "ever-allocated" elements reside on tend to be resident in real memory. It is possible to solve this real storage inefficiency by changing the allocation algorithm to scan the elements in their physical ordering in the pool until the first free element is found, and allocating that one. However, this approach replaces a real storage inefficiency with pathlength problems (which get progressively worse the larger the system becomes). It is possible to minimize the pathlength inefficiency of this "first free" algorithm by the use of indexes, binary trees, or other techniques, but this involves additional coding complexity. The technique described below retains the simplicity and low pathlength of the LIFO algorithm, while achieving most of the real storage efficiency of the "first free" algorithm. Assume there is one array of fixed-length elements. That is, the fixed-length elements are contiguous in one block of storage. All unallocated elements are chained together (forward and backward pointers) into a free list. A determination is made whether a given element is allocated or not. This can be accomplished by a special bit for this purpose, or because both forward and backward pointers are zero, or in another method. At initialization time, the elements are chained together in element address order, lowest address to highest address. A FIRST-OR...