Browse Prior Art Database

Dynamic Storage Allocation Scheme

IP.com Disclosure Number: IPCOM000106202D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Related People

Armbruster, CE: AUTHOR [+2]

Abstract

A storage allocation algorithm with delayed coalescence of dynamically determined common block sizes is disclosed.

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

Dynamic Storage Allocation Scheme

      A storage allocation algorithm with delayed coalescence of
dynamically determined common block sizes is disclosed.

      In an environment where the requested block sizes tend to be
repeated, a scheme can be developed to take advantage of this.  In
this scheme, blocks of commonly used sizes are dynamically created
and kept around longer to facilitate future storage requests.  This
is done with delayed coalescence.

      During allocation of needed space, the algorithm searches the
unused space for a block that is an exact fit.  Each block it
examines that is not an exact fit is compared to the saved best fit
information (which is updated if necessary).  Best fit criteria is
the smallest black that is be enough to satisfy the request.  If an
exact fit is found, that block is marked used and returned to the
requestor.  If an exhaustive search of the free space available list
did not produce an exact fit, then a test is made to see if a best
fit block was found.  If so it is split in two; one part being marked
for used for the requestor and the other going back to the free space
available list.  In the event that the request has still not been
satisfied, a single pass is made through the free space available
list which coalesces all of the adjacent free storage spaces.  Then
the above search is tried one more time before a no space available
indication would be returned to the requester.

      During de-alloca...