Live memory analysis for garbage collection in embedded systems

ABSTRACT

Real-time garbage collection is essential if object-oriented languages (in particular, Java) are to become predictable enough for real-time embedded systems. Although techniques for hard real-time garbage collection exist, they are based on estimations of the maximum amount of referenced (live) memory. Such estimations may be difficult to derive manually for complex programs.We present techniques for predicting the maximum amount of live memory in object-oriented languages with inheritance and virtual methods. Annotations are used to bound recursively defined data structures. The annotations may also be used for timing analysis of code traversing annotated structures.A prototype live memory analysis tool has been developed. The tool interactively provides predictions of the maximum amount of live memory referenced from an arbitrary reference or block in an object-oriented program.

REFERENCES

• 1: P. Altenbernd. On the False Path Problem in Hard Real-Time Programs. Proceedings of the 8th Euromicro Workshop on Real-Time Systems, 1996.
• 2: E. Bjarnason. Interactive Tool Support .for Domain-Specific Languages. Licentiate Thesis, Department of Computer Science, Lund University, December 1997.
• 3: Elizabeth Bjarnason , Görel Hedin , Klas Nilsson, Interactive language development for embedded systems, Nordic Journal of Computing, v.6 n.1, p.36-54, Spring 1999
• 4: 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]
• 5: Andreas Ermedahl , Jan Gustafsson, Deriving Annotations for Tight Calculation of Execution Time, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1298-1307, August 26-29, 1997
• 6: William Foote, Real-Time Extensions to the Java Platform A Progress Report, Proceedings of the Fourth International Workshop on Object-Oriented Real-Time Dependable Systems, p.42, January 27-29, 1999
• 7: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 8: G. Hedin. Reference Attributed Grammars. In D. Parigot and M. Mernik (editors): Proceedings o.f WAGA '99, Second Workshop on Attribute Grammars and their Applications, pages 153-172. Amsterdam, The Netherlands, March 1999. INRIA Rocquencourt.
• 9: Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
• 10: R. Henriksson. Scheduling Garbage Collection in Embedded Systems. Ph. D. Thesis, Department of Computer Science, Lund University, September 1998. http ://www. cs.lth.se/-roger/thesis.html
• 11: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• 12: S.-S. Lim, Y. H. Bae, G. T. Jang, B.-D. Rhee, S. L. Min, C. Y. Park, H. Shin, K. Park, and C. S. Kim. An Accurate Worst CaseTiming Analysis Technique for RISC Processors. Proceedings of the IEEE Real-Time Systems Symposium, December 1996.
• 13: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 14: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• 15: Thomas Lundqvist , Per Stenström, Integrating Path and Timing Analysis Using Instruction-Level Simulation Techniques, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.1-15, June 01, 1998
• 16: Bertrand Meyer, Applying "Design by Contract", Computer, v.25 n.10, p.40-51, October 1992 [doi>10.1109/2.161279 ]
• 17: Kelvin Nilsen, Reliable real-time garbage collection of C++, Computing Systems, v.7 n.4, p.467-504, Fall 1994
• 18: P. Persson and G. Hedin. Interactive Execution Time Predictions using Reference Attributed Grammars. In D. Parigot and M. Mernik (editors): Proceedings of WAGA '99, Second Workshop on Attribute Grammars and their Applications, pages 173-184. Amsterdam, The Netherlands, March 1999. INRIA Rocquencourt.
• 19: Real-Time JavaTM Working Group. http ://www. newmonics, com/webroot/rtjwg, html
• 20: A. C. Shaw, Reasoning About Time in Higher-Level Language Software, IEEE Transactions on Software Engineering, v.15 n.7, p.875-889, July 1989 [doi>10.1109/32.29487 ]
• 21: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 22: V. Sundaresan, C. Razafimahefa, R. Vall@e-Rai, and L. Hendren. Practical Virtual Method Call Resolution for Java. Sable Technical Report No. 1998-7, McGill University, Canada, 1998.
• 23: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-31, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237725]
• 24: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Experimentation, Reliability, Theory