Static determination of allocation rates to support real-time garbage collection

ABSTRACT

While it is generally accepted that garbage-collected languages offer advantages over languages in which objects must be explicitly deallocated, real-time developers are leery of the adverse effects a garbage collector might have on real-time performance. Semiautomatic approaches based on regions have been proposed, but incorrect usage could cause unbounded storage leaks or program failure. Moreover, correct usage cannot be guaranteed at compile time. Recently, real-time garbage collectors have been developed that provide a guaranteed fraction of the CPU to the application, and the correct operation of those collectors has been proven, subject only to the specification of certain statistics related to the type and rate of objects allocated by the application. However, unless those statistics are provided or estimated appropriately, the collector may fail to collect dead storage at a rate sufficient to pace the application's need for storage. Overspecification of those statistics is safe but leaves the application with less than its possible share of the CPU, which may prevent the application from meeting its deadlines.In this paper we present a static analysis to bound conservatively an application's allocation rate. The analysis is based on a data flow framework that requires interprocedural evaluation. We present the framework and results from analyzing some Java benchmarks. Because static analysis is necessarily conservative, we also present measurements of our benchmarks' actual allocation rates.Our work is a necessary step toward making real-time garbage collectors attractive to the hard-real-time community. By guaranteeing a bound on statistics provided to a real-time collector, we can guarantee the operation of the collector for a given application.

REFERENCES

• 1: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, 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: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: Dante J. Cannarozzi , Michael P. Plezbert , Ron K. Cytron, Contaminated garbage collection, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.264-273, June 18-21, 2000, Vancouver, British Columbia, Canada
• 5: Lisa Carnahan and Marcus Ruark. Requirements for real-time extensions for the java platform (final draft). Technical report, NIST, 1999.
• 6: 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
• 7: Martin R. Linenweber. A study in Java bytecode engineering with PCESjava. Master's thesis, Washington University in St. Louis, 2003.
• 8: Tobias Mann and Ron K. Cytron. Automatic Determination of Factors for Real-Time Garbage Collection. In Washington University technical report #WUCS-04-45, St. Louis, Missouri, 2004.
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: Kelvin Nilsen. Issues in the design and implementation of real-time Java. Java Developer's Journal, 1(1):44, 1996.
• 11: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 12: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, ACM SIGPLAN Notices, v.36 n.5, p.104-113, May 2001
• 13: Fridtjof Siebert, Eliminating external fragmentation in a non-moving garbage collector for Java, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.9-17, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354883]
• 14: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 15: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 16: Paul R. Wilson. Uniprocessor garbage collection techniques (Long Version). Submitted to ACM Computing Surveys, 1994.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Languages, Measurement

Keywords:
allocation rate, real-time garbage collection, static analysis