Memory occupancy patterns in garbage collection systems

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.

REFERENCES

• 1: Betteridge, T. An analytical storage allocation model. Acta Inf. (1974), 101-122.
• 2: Davies, D.J.M. The fifty-percent rule revisited. BIT 20 (1980), 279- 288.
• 3: Feller, W. An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed. John Wiley & Sons, Inc,, New York, 1968.
• 4: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Mood, A.M The distribution theory of runs. Ann. Math. Stat. 11 (1940), 367-392.
• 7: J. M. Robson, An Estimate of the Store Size Necessary for Dynamic Storage Allocation, Journal of the ACM (JACM), v.18 n.3, p.416-423, July 1971 [doi>10.1145/321650.321658]
• 8: John E. Shore, Anomalous behavior of the fifty-percent rule in dynamic memory allocation, Communications of the ACM, v.20 n.11, p.812-820, Nov. 1977 [doi>10.1145/359863.359880]
• 9: Reeves, C.M. Free store distribution under random fit placement: Part I. Comput. J. 22, 4 (1979), 346-351.
• 10: Reeves, C.M. Free store distribution under random fit placement: Part 2. Comput. J. 23 4 (1980), 298-306.
• 11: Reeves, C.M. Free store distribituion under random fit placement: Part 3. Comput. J. 26, 1 (1983), 25-35.
• 12: Davies, D.J.M. A note on sparsely filled dynamically allocated memory. Comput. J. 25, 1 (1982), 159.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Design, Performance, Theory

Keywords:
dynamic storage allocation, fifty percent rule, garbage collection, memory fragmentation, simulations