Garbage collection for virtual memory computer systems

ABSTRACT

In list processing there is typically a growing demand for space during program execution. This paper examines the practical implications of this growth within a virtual memory computer system, proposes two new garbage collection techniques for virtual memory systems, and compares them with traditional methods by discussion and by simulation.

REFERENCES

• 1: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 2: IBM System/360 Model 67 Functional Characteristics. Form A27-2719. IBM, Kingston, N.Y. 1967.
• 3: Baecker, H.D. Implementing the ALGOL 68 heap, BIT Nordisk Tidskrift for Informationsbehandling 10, 4 (1970), 405-414.
• 4: Niklaus Wirth , C. A. R. Hoare, A contribution to the development of ALGOL, Communications of the ACM, v.9 n.6, p.413-432, June 1966 [doi>10.1145/365696.365702]
• 5: Bauer, H.R., et al. ALGOL WLanguage Description CS110, Computer Science Dept., Stanford U., Stanford, Calif., 1968.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: Richard C. Singleton, Algorithm 347: an efficient algorithm for sorting with minimal storage [M1], Communications of the ACM, v.12 n.3, p.185-186, March 1969 [doi>10.1145/362875.362901]
• 8: B. Randell, A note on storage fragmentation and program segmentation, Communications of the ACM, v.12 n.7, p.365-ff., July 1969 [doi>10.1145/363156.363158]
• 9: GEMINI Computer Systems: Principles of Operation. Computer Operations Inc., Costa Mesa, Calif. 1970.
• 10: Welch, J.S. ZORCH. Computer Applications Inc., Washington, D.C., May 1970.
• 11: H. D. Baecker, Mapped list structure, Communications of the ACM, v.6 n.8, p.435-438, Aug. 1963 [doi>10.1145/366707.367528]
• 12: Turski, W.M. (Ed.) Efficient Production of Large Programs. Computation Centre of the Polish Academy of Sciences, Panstwowe Wydawnictiwo Naukowe, Warsaw, Poland, 1971.

INDEX TERMS

Keywords:
garbage collection, list processing, page tables, paging, segmentation, virtual memory