Fast fits: New methods for dynamic storage allocation (summary of paper to be published in ACM transactions on computer systems)

Abstract

The classical methods for implementing dynamic storage allocation can be summarized thus: First Fit and Best Fit The available blocks of storage are linked together in address order. Storage is allocated from the first available block of sufficient length, or from a block with the minimum excess length. Storage can be allocated or released in multiples of two words. In the long run, if numerous pieces of storage of more-or-less random lengths are allocated and released at more-or-less random intervals, the storage becomes fragmented, and a number of uselessly small blocks develop, particularly near the beginning of the list. Although these fragments usually comprise a small proportion of the storage (typically around 10 per cent), a lot of time can be wasted chaining through them.