A study of concurrent real-time garbage collectors

ABSTRACT

Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors also offer much better scalability over incremental collectors. The main problem with concurrent real-time collectors is their complexity. The first concurrent real-time garbage collector that can support fine synchronization, STOPLESS, has recently been presented by Pizlo et al. In this paper, we propose two additional (and different) algorithms for concurrent real-time garbage collection: CLOVER and CHICKEN. Both collectors obtain reduced complexity over the first collector STOPLESS, but need to trade a benefit for it. We study the algorithmic strengths and weaknesses of CLOVER and CHICKEN and compare them to STOPLESS. Finally, we have implemented all three collectors on the Bartok compiler and runtime for C# and we present measurements to compare their efficiency and responsiveness.

REFERENCES

• 1: Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 5: Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.104-117, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 7: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 8: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 9: Cliff Click , Gil Tene , Michael Wolf, The pauseless GC algorithm, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064988]
• 10: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 11: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 12: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 13: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Tamar Domani , Elliot K. Kolodner , Ethan Lewis , Eliot E. Salant , Katherine Barabash , Itai Lahan , Yossi Levanoni , Erez Petrank , Igor Yanorer, Implementing an on-the-fly garbage collector for Java, Proceedings of the 2nd international symposium on Memory management, p.155-166, October 15-16, 2000, Minneapolis, Minnesota, United States
• 15: ECMA. Standard ECMA-335, Common Language Infrastructure (CLI), 4th edition edition, June 2006. http://www.ecmainternational. org/.
• 16: Roger Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, 1998.
• 17: M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992 [doi>10.1109/71.139204]
• 18: Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376810]
• 19: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 20: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 21: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 22: Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006 [doi>10.1145/1111596.1111597]
• 23: Matthias Meyer, A true hardware read barrier, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133959]
• 24: Yoav Ossia , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Avi Owshanko, A parallel, incremental and concurrent GC for servers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 25: Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296927]
• 26: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, Proceedings of the 2nd international symposium on Memory management, p.143-154, October 15-16, 2000, Minneapolis, Minnesota, United States
• 27: Sven Gestegård Robertz and Roger Henriksson. Time-triggered garbage collection - robust and adaptive real-time GC scheduling for embedded systems. LCTES 2003.
• 28: Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 29: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Algorithms, Measurement, Performance, Reliability

Keywords:
concurrent garbage collection, garbage collection, lock-free computation, memory management, real-time