Richard L. Hudson
J. Eliot B. Moss
ABSTRACT
Many concurrent garbage collection (GC) algorithms have been devised, but few have been implemented and evaluated, particularly for the Java programming language. Sapphire is an algorithm we have devised for concurrent copying GC. Sapphire stresses minimizing the amount of time any given application thread may need to block to support the collector. In particular, Sapphire is intended to work well in the presence of a large number of application threads, on small- to medium-scale shared memory multiprocessors. A specific problem that Sapphire addresses is not stopping all threads while thread stacks are adjusted to account for copied objects (in GC parlance, the “flip” to the new copies).
Sapphire extends previous algorithms, and is most closely related to replicating copying collection, a GC technique in which application threads observe and update primarily the old copies of objects [13]. The key innovations of Sapphire are: (1) the ability to “flip” one thread at a time (changing the thread's view from the old copies of objects to the new copies), as opposed to needing to stop all threads and flip them at the same time; and (2) avoiding a read barrier.
- 1.A. W. Appel, J. R. Ellis, and K. Li. Realtime concurrent collection on stock multiprocessors. In Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 11-20, Atlanta, Georgia, June 1988. ACM SIGPLAN Notices 23, 7 (July 1988). Google Scholar
Digital Library
- 2.D. E Bacon, R. Konuru, C. Murthy, and M. Serrano. Thin locks: Featherweight synchronization for Java. In 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 258-268, Montreal, Quebec, June 1998. ACM Press. Google ScholarDigital Library
- 3.H. G. Baker. List processing in real time on a serial computer. Communications of the ACM, 21 (4):280--294, Apr. 1978. Google ScholarDigital Library
- 4.Y. Bekkers and J. Cohen, editors. International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, St. Malo, France, Sept. 1992. Springer-Verlag. Google ScholarDigital Library
- 5.R. A. Brooks. Trading data space for reduced time and code space in real time garbage collection on stock hardware. In Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, pages 256-262. ACM, 1984. Google ScholarDigital Library
- 6.P. Cheng, R. Harper, and P. Lee. Generational stack collection and profile-driven pretenuring. In 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 162-173, Montreal, Quebec, June 1998. ACM Press. Google ScholarDigital Library
- 7.D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-First ACM Symposium on Principles of Programming Languages, Portland, Oregon, Jan. 1994. Google ScholarDigital Library
- 8.D. Doligez and X. Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, pages 113-123. ACM Press, Jan. 1993. Google ScholarDigital Library
- 9.R. L. Hudson and J. E. B. Moss. Incremental collection of mature objects. In Bekkers and Cohen {4}, pages 388-403. Google Scholar
- 10.L. Huelsbergen and J. R. Larus. A concurrent copying garbage collector for languages that distinguish (ira)mutable data. In Fourth Annual ACM Symposium on Principles and Practice of Parallel Programming, volume 28(7) of ACM SIGPLAN Notices, pages 73-82, San Diego, CA, May 1993. ACM Press. Google ScholarDigital Library
- 11.R. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley and Sons, 1996. Google ScholarDigital Library
- 12.T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1997. Google ScholarDigital Library
- 13.S. M. Nettles, J. W. O'Toole, D. Pierce, and N. Haines. Replication-based incremental copying collection. In Bekkers and Cohen {4}.Google Scholar
- 14.W. Pugh. Fixing the Java memory model. In ACMJava Grande Conference, June 1999. Google ScholarDigital Library
- 15.W. Pugh. Semantics of multithreaded java. Available as www.cs.umd.edu/'pugh/java/memoryModel/semantics.pdf Oct. 24 2000.Google Scholar
Index Terms
- Sapphire: copying GC without stopping the world
Recommendations
Transactional Sapphire: Lessons in High-Performance, On-the-fly Garbage Collection
Constructing a high-performance garbage collector is hard. Constructing a fully concurrent ‘on-the-fly’ compacting collector is much more so. We describe our experience of implementing the Sapphire algorithm as the first on-the-fly, parallel, replication ...
Carbothermal reduction growth of ZnO nanostructures on sapphire-comparisons between graphite and activated charcoal powders
Zinc oxide (ZnO) nanostructures were grown by the vapour phase transport (VPT) method on a-plane sapphire substrates via carbothermal reduction of ZnO powders with various carbon powders. Specifically, graphite powder and activated charcoal powder (of ...
Growth mechanism of iron nanoparticles on (0001) sapphire wafers
Laser ablation of a high purity (99.7%) iron target was used to accomplish the depositions of iron nanoparticles on the (0001) face of single crystal sapphire wafers. The nanoparticles were characterized in situ by means of X-ray photoelectron ...
Comments