A concurrent, generational garbage collector for a multithreaded implementation of ML

ABSTRACT

This paper presents the design and implementation of a “quasi real-time” garbage collector for Concurrent Caml Light, an implementation of ML with threads. This two-generation system combines a fast, asynchronous copying collector on the young generation with a non-disruptive concurrent marking collector on the old generation. This design crucially relies on the ML compile-time distinction between mutable and immutable objects.

References

1. 1.A. W. Appel. Compiling with continuations. Cambridge University Press, 1992.
2. 2.A. W. Appel, J. R. Ellis, and K. Li. Real-time concurrent collection on stock multiprocessors. SIG- PLAN Notices, 23(7):11-23, 1988.
3. 3.A. W. Appel and K. Li. Virtual memory primitives for user programs. Technical Report CS-TR-276- 90, Princeton University, 1990.
4. 4.H. G. Baker. List processing in real time on a serial computer. Commun. A CM, 21(4):280-294, 1978.
5. 5.M. Ben-Ari. Algorithms for on-the-fly garbage collection. A CM Trans. Prog. Lang. Syst., 6(3):333- 344, 1984.
6. 6.B. Berthomieu. Implementing CCS: the LCS experiment. Technical report 89425, LAAS, Dec. 1989.
7. 7.H. J. Boehm, A. J. Demers, and S. Shenker. Mostly parallel garbage collection. SIGPLAN Notices, 26(6):157-164, 1991.
8. 8.R. A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Lisp and Functional Programming 198~, pages 256-262. ACM Press, 1984.
9. 9.E. C. Cooper and R. P. Draves. C threads. Technical report CMU-CS-88-154, Carnegie Mellon University, 1988.
10. 10.G. Cousineau, P.-L. Curien, and M. Mauny. The categorical abstract machine. Sczence of Computer Programming, 8(2):173-202, 1987.
11. 11.E. W. Dijkstra, L. Lamport, A. :I. Martin, C. S. Sholten, and E. F. M. Steffens. On-the-fly garbage collection: an exercice in cooperation. Commun. ACM, 21(11):966-975, 1978.
12. 12.R. H. Halstead. Implementation of Multilisp: Lisp on a multiprocessor. In Lisp and Functional Programming 1984, pages 9-17. ACM Press, 1984.
13. 13.T. Hickey and :I. Cohen. Performance analysis of on-the-fly garbage collection. Commun. A CM, 27(11):1143-1154, 1984.
14. 14.H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In Foundations of Computer Science 1977, pages 120-131. IEEE Computer Society Press, 1977.
15. 15.X. Leroy. The ZINC experiment: an economical implementation of the ML language. Technical report 117, INRIA, 1990.
16. 16.X. Leroy and M. Mauny. The Caml Light system, version 0.5 documentation and user's guide. Technical report L-5, INRIA, 1992.
17. 17.R. Milner, M. Tofte, and R. Harper. The definition of Standard ML. The MIT Press, 1990.
18. 18.D.A. Moon. Garbage collection in a large Lisp system. In Lisp and Functional Programming 198~, pages 235-246. ACM Press, 1984.
19. 19.:I. G. Morriset and A. Tolmach. A portable multiprocessor interface for Standard ML of New Jersey. Technical report CMU-CS-92-155, Carnegie Mellon University, 1992.
20. 20.S. C. North and :I. H. Reppy. Concurrent garbage collection on stock hardware. In Functional Programming Languages and Computer Architecture 1987, volume 242 of Lecture Notes in Computer Science, pages 113-133. Springer-Verlag, 1987.
21. 21.L. C. Paulson. ML for the working programmer. Cambridge University Press, 1991.
22. 22.J. H. Reppy. CML: a higher-order concurrent language. SIGPLAN Notices, 6(26):294-305, 1991.
23. 23.G. L. Steele Jr. Multiprocessing compactifying garbage collection. Commun. A CM, 18(9):495- 508, 1975.
24. 24.D. Ungar. Generation scavenging: a nondisruptive high performance storage reclamation algorithm. In Software Engineering Symposium on Practical Software Development Environmenls, pages 157-167. ACM Press, 1984.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

        • Concurrent programming structures

      • Language types