Efficient Management of Fixed-Length Storage Elements
Original Publication Date: 1989-Jan-01
Included in the Prior Art Database: 2005-Jan-27
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.