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 , Michael J. Franklin , Olivier Gruber, Efficient Incremental Garbage Collection for Client-Server Object Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.42-53, September 11-15, 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 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
• 5: 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]
• 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, The Real-Time Specification for Java, Computer, v.33 n.6, p.47-54, June 2000 [doi>10.1109/2.846318]
• 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: Paulo Ferreira , Marc Shapiro, Garbage collection and DSM consistency, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.17-es, November 14-17, 1994, Monterey, California
• 10: Roger Henriksson. Scheduling Garbage Colection in Embedded Systems. PhD thesis, Lund University, July 1998.
• 11: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 12: Richard Jones , Andy C. King, A Fast Analysis for Thread-Local Garbage Collection with Dynamic Class Loading, Proceedings of the Fifth IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'05), p.129-138, September 30-October 01, 2005 [doi>10.1109/SCAM.2005.1]
• 13: Niels Christian Juul , Eric Jul, Comprehensive and Robust Garbage Collection in a Distributed System, Proceedings of the International Workshop on Memory Management, p.103-115, September 17-19, 1992
• 14: Arvind S. Krishna , Douglas C. Schmidt , Raymond Klefstad, Enhancing Real-Time CORBA via Real-Time Java Features, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.66-73, March 24-26, 2004
• 15: Bernard Lang , Christian Queinnec , José Piquer, Garbage collecting the world, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-50, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143176]
• 16: Umesh Maheshwari and Barbara Liskov. Collecting cyclic distributed garbage by controlled migration. Distributed Computing, 10(2):79--86, 1997.
• 17: Umesh Maheshwari , Barbara Liskov, Partitioned garbage collection of a large object store, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.313-323, May 11-15, 1997, Tucson, Arizona, United States
• 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 P. Pirinen, Barrier techniques for incremental tracing, Proceedings of the 1st international symposium on Memory management, p.20-25, October 17-19, 1998, Vancouver, British Columbia, Canada
• 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 , Jan Vitek, An Emprical Evaluation of Memory Management Alternatives for Real-Time Java, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.35-46, December 05-08, 2006 [doi>10.1109/RTSS.2006.9]
• 22: William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.76-85, October 05-07, 1994, San Jose, California, United States
• 23: F. Siebert, Real-Time Garbage Collection in Multi-Threaded Systems on a Single Processor, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.277, December 01-03, 1999
• 24: Voon-Fee Yong , Jeffrey F. Naughton , Jie-Bing Yu, Storage Reclamation and Reorganization in Client-Server Persistent Object Stores, Proceedings of the Tenth International Conference on Data Engineering, p.120-131, February 14-18, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Experimentation, Languages

Keywords:
Java memory management, real time systems