ABSTRACT
Languages such as Java, ML, Scheme, and Haskell provide automatic storage management, that is, garbage collection. The two fundamental operations performed on a garbage-collected heap are "allocate" and "collect." Because the heap is in an inconsistent state during these operations, they must be performed atomically. Otherwise, a heap client might access the heap during a time when its fundamental invariants do not hold, corrupting the heap.Standard techniques for providing this atomicity guarantee have large latencies and other performance problems that impede their application in high-performance, interruptladen, thread-based systems applications. In particular, the standard techniques prevent thread schedulers from switching threads on VM page faults.We cast the space of possible implementations into a general taxonomy, and describe a new technique that provides a simple, low-overhead, low-latency interlock. We have implemented this technique in a version of SML/NJ, and, because of its applicability to thread-based systems, are currently implementing it in the scheduler of our raw-hardware SML-based kernel, ML/OS. Our technique can be extended to provide other atomic sequences besides storage allocation.
- Diwan+.Amer Diwan, Eliot Moss, and Richm:d Hudson. Compiler support for garbage collection in a statically typed language. Proceedings of the ACM SiGPLAN '92 Conference on Programming Language Design and Implementation (PLDI), pages 273-282. Google ScholarDigital Library
- Feeley.Marc Feeley Polling efficiently on stock hardware. in Proceedings of the 1993 A CTVI SIG. PLAN Conference on Functional Programruing and Computer Architecture~ Copenhagen, Denmark, June 1993, pp. 179--187. Google ScholarDigital Library
- Herlihy.P.M. Herlihy. Wait-free synchronization. A CM transactions on programming languages and systems, 13(1), January 1991. Google ScholarDigital Library
- JavaGC.James M. Stichnoth, Guei-Yuan Lueh, and Michat Cierniak. Support for garbage collection at every instruction in a Java compiler. Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation (PLDI), pages 118- 127, May, 1999. Google ScholarDigital Library
- LockFree.Andrew W. Appel. To the best of our knowledge, this very clever technique is due to Andrew Appel and remains unpublished. One of us (Shivers) saw Andrew sketch this approach out on a blackboard in the late eighties, point out the critical trivial-abort property, and state that it had been implemented and subsequently abandoned. But no description of the technique can be found in any of Appel's published works, and when pressed, he becomes evasive, claims poor memory, and denies any involvement with the covert manipulation of autonomous processor-states. We note without further comment his long-standing support by powerful Department of Defense agencies.Google Scholar
- ML/OS.The Flux OSKit: A substrate for kernel and language research. Bryan Ford, Godmax Back, Greg Benson, Jay Lepreau, Albert Lin and Olin Shivers. In Proceedings of the Sixteenth A CM Symposium on Operating Systems Principles (SOSP-16), October 1997, Saint-Malo, France. Google ScholarDigital Library
- ML-threads.J. Gregory Morrisett and Andrew Tolmach. Procs and Locks: A portable multiprocessing platform for Standard ML of New Jersey. In Proceedings o/the Fourth A CM $iG- PLAN Symposium on Principles and Practice of Parallel Programming, San Diego, May 1993. Google ScholarDigital Library
- Modula-3.Greg Nelson, editor. Systems Programming with Modula-3. Prentice HaIi, 199I, Englewood Cliffs, New Jersey. Google ScholarDigital Library
- MLRisc.Little has been published on Lal George's MLRisc code-generator compiler back-end. However, on-.line documen'~ation can be found at http://cm.bell-labs.com/cm/cs/ what /smln j/doc/MLRISC/index, html.Google Scholar
- Orbit.David Kranz. Orbit: An Optimizing Compiler for Scheme. Ph.D. dissertation, Yale University, February 1988. Research Report 632, Depaa'tment of Computer Science. A conferencelength version of this dissert~Ltion appears in SIGPLAN 86. Google ScholarDigital Library
- ParaCaml.Damien Doligez and Xavier Leroy. A concuxrent~ generational garbage collector for a multithreaded implementation of ML. Proceedings of POPL '93. Google ScholarDigital Library
- PCC.George C. Necula, Peter Lee. Safe kernel extensions without run-time checking. In Proceedings of the Second Symposium on Operating Systems Design and Implementation (OSDI '96), Seattle, Washington, October 1996. Google ScholarDigital Library
- PCLSR.Alan Bawden. "PCLSRing: Keeping process state modular." Unpublished memo, available via anonymous FTP as ftp://ftp, ai.mit. e du/pub / al an/pc 1 st. memo.Google Scholar
- Qua.Henry Massalin. Synthesis: An E.O~cient Implementation of Fundamental Operating $yste?n Services. Ph.D. dissertation, Columbia. University, 1992. Google ScholarDigital Library
- RTC-GC.Andrew W. Appel, John R Ellis, and Kai Li. Real-time concurrent collection on stock: multiprocessors. In Proceed~ings of the $IG- PLAN '88 Conference on Programming Language Design and implementation, June 1988. Google ScholarDigital Library
- SML/NJ.Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Third International symposium on Programming Lan. guage Implementation and Logic Program.- ming, LNCS 528, pages 1-13, Martin Wirsing, editor, August 1991. Springex-Verlag, New York.Google Scholar
- Spur.Mark Hill, et al. Design decisions in Spur. COMPUTER, 19(11):8-22, November 1986. Google ScholarDigital Library
- T.Jonathan A. Rees and Norman I. Adams iv. T: A dialect of Lisp or, Lambda: The ultimate software tool. In Conference Record of the 198~ A CM Symposium on LISP and Functional Programming, pages 114-122, August 1982. Google ScholarDigital Library
- Unimutex.Brian N. Bershad, David D. Redell and John R. Ellis. Fast mutual-exclusion for uniprocessots. In Proceedings of the Fifth Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS V), October, 1992. ACM Press, SIGARCH Computer Architecture News 20 (Special Issue October 1992), SIGOPS Operating System Review 26 (Special Issue October 1992), and SIGPLAN Notices 27(9). Google ScholarDigital Library
- Wilson.Paul R. Wilson. Uniprocessor garbage collection techniques. In International Workshop on Memory Management, St. Malo, France, September 1992. (Proceedings published as Springer-Verlag Lecture Notes in Computer Science, no. 637). Also available at url ftp://ftp, cs.utexas, edu/pub/ gsxbage/gcsurvey, ps Google ScholarDigital Library
Index Terms
- Atomic heap transactions and fine-grain interrupts
Recommendations
Atomic heap transactions and fine-grain interrupts
Languages such as Java, ML, Scheme, and Haskell provide automatic storage management, that is, garbage collection. The two fundamental operations performed on a garbage-collected heap are "allocate" and "collect." Because the heap is in an inconsistent ...
Atomic garbage collection: managing a stable heap
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of dataModern database systems use transactions to achieve a high degree of fault-tolerance. Many modern programming languages and systems provide garbage collected heap storage, which frees the programmer from the job of explicitly deallocating storage. In ...
Atomic garbage collection: managing a stable heap
Modern database systems use transactions to achieve a high degree of fault-tolerance. Many modern programming languages and systems provide garbage collected heap storage, which frees the programmer from the job of explicitly deallocating storage. In ...
Comments