Anomalous Behavior of the Fifty-Percent
Rule in Dynamic Memory Allocation

This paper reports simulation data showing
that, in dynamic memory allocation, the average 
free-to-allocated-block ratio can differ considerably
and in both directions from the predictions of 
the 50 percent rule.  A new derivation is given, and it
is shown that previous derivations make an assumption 
that may be violated frequently.  On the basis of the simulation
data and 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 support
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 approximately inversely with the coefficient 
of variation of the memory residence time distribution.
 The simulations show that allocation efficiency 
depends strongly on the residence time distribution; efficiency
decreases as the distribution's coefficient 
of variation increases.  Some practical implications are briefly discussed.

CACM November, 1977

Shore, J. E.

dynamic memory allocation, storage fragmentation,
fifty-percent rule, first-fit, simulation

3.73 4.32 4.34 4.35

CA771105 JB December 27, 1977  7:37 AM

2095	4	2911
2218	4	2911
2498	4	2911
2596	4	2911
2596	4	2911
2734	4	2911
2747	4	2911
2768	4	2911
2845	4	2911
2902	4	2911
2902	4	2911
2902	4	2911
2911	4	2911
2911	4	2911
2911	4	2911
2911	4	2911
2911	4	2911
2911	4	2911
2911	4	2911
2955	4	2911
2955	4	2911
2983	4	2911
3000	4	2911
972	4	2911
273	5	2911
1879	5	2911
2435	5	2911
2498	5	2911
2734	5	2911
2773	5	2911
2911	5	2911
2911	5	2911
2911	5	2911
2983	5	2911