The fifty percent rule revisited

Combinatorial reasoning is applied to the analysis of two kinds of dynamic storage allocation system to derive results about the degree and characteristics of memory fragmentation. The simple first-fit scheme with immediate replacement, discussed by Knuth, is analyzed further, providinginter alia a new derivation of the fifty percent rule. Next a system with garbage collections is considered, and the mean and variance of the number of holes following a garbage collection are determined, along with other results. The cell distributions resulting from these two idealized policies are contrasted.This research was supported in part by the National Science and Engineering Research Council of Canada under an operating grant.