Anomalous Behavior of the Fifty-Percent Rule.
Abstract
This paper reports simulation data showing that, in dynamic memory allocation, the average free-to-allocated-block ratio can be considerably less than predicted by the fifty-percent rule. A new derivation is given, and it is shown that previous derivations make an implicit assumption that may be violated frequently. Based on the simulation data and on the derivation, it is hypothesized that the anomalous behavior results from the combined effects of systematic placement and the statistics of the release process. Additional simulations supported this hypothesis. Systematic placement, which refers to the natural convention of always allocating storage requests against the same end of the free block selected by the allocation strategy, tends to order blocks within contiguous groups according to their allocation time. The degree of anomalous behavior depends on the extent to which allocated blocks are released in the order of their allocation. For non-Markovian release processes the extent of the correlation between allocation order and release order varies inversely with the coefficient of variation of the memory residence time distribution. For values less than about.8, the free-to-allocated-block ratio can be considerably less than 1/2. For larger values, Knuth's estimate appears to be accurate provided that the average number of allocated blocks is high. Some practical implications are discussed briefly. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA031578
Entities
People
- John E. Shore
Organizations
- United States Naval Research Laboratory