Hierarchical real-time garbage collection

ABSTRACT

Memory management is a critical issue for correctness and performance in real-time embedded systems. Recent work on real-time garbage collectors has shown that it is possible to provide guarantees on worst-case pause times and minimum mutator utilization time. This paper presents a new hierarchical real-time garbage collection algorithm for mixed-priority and mixed-criticality environments. With hierarchical garbage collection, real-time programmers can partition the heap into a number of heaplets and for each partition choose to run a separate collector with a schedule that matches the allocation behavior and footprint of the real-time task using it. This approach lowers worst-case response times of real-time applications by 26%, while almost doubling mutator utilization -- all with only minimal changes to the application code.

References

1. Laurent Amsaleg, Olivier Gruber, and Michael Franklin. Efficient incremental garbage collection for workstation-server database systems. In Proceedings of the International Conference on Very Large Data Bases, pages 42--53. Morgan Kaufmann, 1995.
2. Chris Andreae, Yvonne Coady, Celina Gibbs, James Noble, Jan Vitek, and Tian Zhao. Scoped Types and Aspects for Real-Time Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 124--147, Nantes, France, July 2006. Springer.
3. Austin Armbuster, Jason Baker, Antonio Cunei, David Holmes, Chapman Flack, Filip Pizlo, Edward Pla, Marek Prochazka, and Jan Vitek. A Real-time Java virtual machine with applications in avionics. ACM Transactions in Embedded Computing Systems (TECS), to appear.
4. David F. Bacon, Perry Chang, and V.T. Ra jan. A real-time garbage collector with low overhead and consistent utilization. In Conference Record of the ACM Symposium on Principles of Programming Languages, pages 285--298, New Orleans, Louisiana, January 2003.
5. H. G. Baker. List processing in real time on a serial computer. Communications of the ACM, 21(4):280--294, April 1978.
6. Peter B. Bishop. Computer Systems with a Very Large Address Space and Garbage Collection. PhD thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1977.
7. Greg Bollella, James Gosling, Benjamin Brosgol, Peter Dibble, Steve Furr, and Mark Turnbull. The Real-Time Specification for Java. Addison-Wesley, June 2000.
8. Perry Cheng and Guy Blelloch. A parallel, real-time garbage collector. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 125--136, Snowbird, Utah, June 2001.
9. Paulo Ferreira and Marc Shapiro. Garbage collection and DSM consistency. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, pages 229--241, Monterey, California, November 1994.
10. Roger Henriksson. Scheduling Garbage Colection in Embedded Systems. PhD thesis, Lund University, July 1998.
11. Richard L. Hudson and J. Eliot B. Moss. Incremental collection of mature ob jects. In Proceedings of the International Workshop on Memory Management, pages 388--403. Springer-Verlag, 1992.
12. Richard Jones and Andy C. King. A fast analysis for thread-local garbage collection with dynamic class loading. In Proceedings of the 5th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM), pages 129--138, Budapest, Hungary, October 2005.
13. Niels Christian Juul and Eric Jul. Comprehensive and robust garbage collection in a distributed system. In Proceedings of the International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science, pages 103--115, 1995.
14. Arvind S. Krishna, Douglas C. Schmidt, and Raymond Klefstad. Enhancing Real-Time CORBA via Real-Time Java Features. In 24th International Conference on Distributed Computing Systems (ICDCS 2004), pages 66--73, Hachio ji, Tokyo, Japan, March 2004.
15. Bernard Lang, Christian Queinnec, and José M. Piquer. Garbage collecting the world. In Conference Record of the ACM SIGPLAN Symposium on Principles of Programming Languages, pages 39--50, Albuquerque, New Mexico, January 1992.
16. Umesh Maheshwari and Barbara Liskov. Collecting cyclic distributed garbage by controlled migration. Distributed Computing, 10(2):79--86, 1997.
17. Umesh Maheshwari and Barbara Liskov. Partitioned garbage collection of a large ob ject store. In Proceedings of the ACM International Conference on Management of Data, pages 313--323, June 1997.
18. J. Eliot B. Moss, David S. Munro, and Richard L. Hudson. PMOS: A complete and coarse-grained incremental garbage collector for persistent ob ject stores. In Proceedings of the Seventh International Workshop on Persistent Object Systems, pages 140--150. Morgan Kaufmann, 1997.
19. Pekka Pirinen. Barrier techniques for incremental tracing. In Proceedings of the ACM International Symposium on Memory Management, pages 20--25. ACM, March 1999.
20. Filip Pizlo, Jason Fox, David Holmes, and Jan Vitek. Real-time Java scoped memory: design patterns and semantics. In Proceedings of the IEEE International Symposium on Object-oriented Real-Time Distributed Computing (ISORC'04), Vienna, Austria, May 2004.
21. Filip Pizlo and Jan Vitek. An empirical evalutation of memory management alternatives for Real-Time Java. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS), December 2006.
22. William J. Schmidt and Kelvin D. Nilsen. Performance of a hardware-assisted real-time garbage collector. In Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 76--85, San Jose, California, October 1994.
23. Fridtjof Siebert. Real-time garbage collection in multi-threaded systems on a single processor. In Proceedings of the 20th IEEE Real-Time Systems Symposium (RTSS), pages 277--278, Phoenix, Arizona, December 1999.
24. Voon-Fee Yong, Jeffrey F. Naughton, and Jie-Bing Yu. Storage reclamation and reorganization in client-server persistent ob ject stores. In Proceedings of the International Conference on Data Engineering, pages 120--131. IEEE Computer Society, 1994.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Embedded systems

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Embedded software

      • Real-time systems software