Access Restriction

Author Davies, D. Julia. M.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Garbage collection ♦ Simulations ♦ Fifty percent rule ♦ Dynamic storage allocation ♦ Memory fragmentation
Abstract Some programming languages and computer systems use dynamic memory allocation with garbage collection. It would be useful to understand how the utilization of memory depends on the stochastic parameters describing the size and life distributions of the cells. We consider a class of dynamic storage allocation systems which use a first-fit strategy to allocate cells and perform noncompacting garbage collections to recover free memory space when memory becomes fully occupied. A formula is derived for the expected number of holes (available cells) in memory immediately following a garbage collection which specializes to an analogue of Knuth's 'Fifty Percent' rule for nongarbage-collection systems. Simulations confirm the rule for exponentially distributed cell lifetimes. Other lifetime distributions are discussed. The memory-size requirements for noncompacting garbage collection are also analyzed.
Description Affiliation: Univ. of Western Ont., London, Ont., Canada (Davies, D. Julia. M.)
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 27
Issue Number 8
Page Count 7
Starting Page 819
Ending Page 825

Open content in new tab

   Open content in new tab
Source: ACM Digital Library