Access Restriction

Author Shore, John E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Allocation ♦ Simulation ♦ Storage fragmentation ♦ First-fit ♦ Dynamic memory ♦ Fifty-percent rule
Abstract 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.
Description Affiliation: Naval Research Lab, Washington, DC (Shore, John E.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 11
Page Count 9
Starting Page 812
Ending Page 820

Open content in new tab

   Open content in new tab
Source: ACM Digital Library