Browse Prior Art Database

Constant Search Time for a Free Cell in a Multi-Extent Cell Pool

IP.com Disclosure Number: IPCOM000116774D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 68K

Publishing Venue

IBM

Related People

Sutherland, D: AUTHOR [+2]

Abstract

Disclosed is a method that provides a minimal constant search time for a free cell in a multiple-extent cell pool and allows for efficient expansion and contraction of the cell pool.

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

Constant Search Time for a Free Cell in a Multi-Extent Cell Pool

      Disclosed is a method that provides a minimal constant search
time for a free cell in a multiple-extent cell pool and allows for
efficient expansion and contraction of the cell pool.

      Basic cell pools were historically managed as a set of free
cells and a set of in-use cells.  Locating a free cell was fast, and
expanding the cell pool was easy; however, pool contraction, if even
attempted, was very difficult.

      This difficulty in contracting a basic cell pool was reduced by
managing the pool in extents, with each extent containing a fixed
number of cells; once an extent contained only free cells, it could
be removed from the set of extents and its storage released.  The set
of extents could be variously managed as a linked list or an array of
full/empty indicators; the set of free cells within an extent could
variously be managed as a linked list or an array of free/in-use
indicators.  Locating a free cell now required a search of each
extent, and its performance was linear with respect to the number of
pool extents.  A small improvement in performance could be realized
by maintaining a "cursor", i.e., a pointer to the extent where a free
cell was last found, and starting the next search at that point;
however, determining that no free cell exists still required
traversing the entire set of pool extents.

      Suppose a set of control blocks is managed in pools of multiple
extents, and that any used cell can be freed at any time.  The
algorithm to locate a free cell could conceivably need to check each
pool extent for available cells; if no such extent is found (i.e.,
all pool extents are full), a new pool extent must be built and added
to the set of extents, and the first cell in the new extent returned
to the caller for its use.  The performance of this search algorithm
is linear with respect to t...