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