Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Linked List Search Table Array for Free Storage Blocks

IP.com Disclosure Number: IPCOM000119398D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 6 page(s) / 235K

Publishing Venue

IBM

Related People

Bender, ES: AUTHOR

Abstract

IBM DPPX/SP and DPPX/370 programs manage free list storage using a "First Fit" mechanism. This mechanism consists of searching a doubly linked list of free blocks arranged in ascending address order. The first free block of sufficient size encountered that satisfies the allocation request is used. The storage requested is taken from the free block and any storage remaining is integrated back onto the free chain. There is one free chain per subpool, a subpool being a section of system storage with certain read/write, visibility and other properties that meet various system requirements. "First Fit" is a desirable method of searching free lists as long as the number of free blocks searched is small.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Linked List Search Table Array for Free Storage Blocks

      IBM DPPX/SP and DPPX/370 programs manage free list
storage using a "First Fit" mechanism.  This mechanism consists of
searching a doubly linked list of free blocks arranged in ascending
address order.  The first free block of sufficient size encountered
that satisfies the allocation request is used.  The storage requested
is taken from the free block and any storage remaining is integrated
back onto the free chain.  There is one free chain per subpool, a
subpool being a section of system storage with certain read/write,
visibility and other properties that meet various system
requirements.  "First Fit" is a desirable method of searching free
lists as long as the number of free blocks searched is small.  The
number of free blocks on any given free list is proportional to the
amount of storage in the subpool and the number of tasks that are
sharing that storage.

      Storage is dynamically allocated and deallocated to the
operating system and to user applications.  This process requires
that the free list chains be searched to either have items extracted
from the chain or to have items integrated back on to the chain.
Storage fragmentation (number of items on the chain) increases with
time and system load which, in turn, causes system performance to
degrade.

      DPPX allocates and deallocates much of its storage from the
free list.  The free list is a chain of various sized storage blocks
that have already been backed.  These blocks of storage are
represented by Free Storage Control Blocks (FSCBs).  An FSCB is a
data area that is built into the first 16 bytes of the free block of
storage which it describes.  The FSCB can represent a contiguous
piece of backed storage anywhere from 16 bytes to the size of the
subpool it lies in.  FSCBs are doubly linked and chained together in
ascending address order.  The FSCB chain is anchored from the subpool
entry of the subpool which it represents.  An FSCB search table array
(FSTA) is introduced which segments the subpool into predetermined
sizes, thereby dividing a long FSCB chain into smaller more
manageable FSCB chains.  The FSTA entries and the FSCBs are chained
together in such a manner that the FSTA itself becomes part of the
FSCB chain.

      There is one FSTA defined for each subpool with one FSTA entry
needed to represent each predetermined storage segment in that
subpool.  The sizes for these segments can vary from subpool to
subpool without affecting the single system-wide mechanism for
allocating and deallocating free storage.  The FSTA is statically
defined at initialization time and occupies contiguous storage
outside the subpool which it represents.  The fact that the FSTA lies
outside the subpool leads to many enhancements in FSCB search,
integration and concatenation algorithms.  Fig. 1 shows the array
according to the invention.

      An FSTA entry looks like a normal FSCB with one...