Garbage collection for embedded systems

ABSTRACT

Security concerns on embedded devices like cellular phones make Java an extremely attractive technology for providing third-party and user-downloadable functionality. However, garbage collectors have typically required several times the maximum live data set size (which is the minimum possible heap size) in order to run well. In addition, the size of the virtual machine (ROM) image and the size of the collector's data structures (metadata) have not been a concern for server- or workstation-oriented collectors.We have implemented two different collectors specifically designed to operate well on small embedded devices. We have also developed a number of algorithmic improvements and compression techniques that allow us to eliminate almost all of the per-object overhead that the virtual machine and the garbage collector require. We describe these optimizations and present measurements of the Java embedded benchmarks (EEMBC) of our implementations on both an IA32 laptop and an ARM-based PDA.For applications with low to moderate allocation rates, our optimized collector running on the ARM is able to achieve 85% of peak performance with only 1.05 to 1.3 times the absolute minimum heap size. For applications with high allocation rates, the collector achieves 85% of peak performance with 1.75 to 2.5 times the minimum heap size. The collector code takes up 40 KB of ROM, and collector metadata overhead has been almost completely eliminated, consuming only 0.4% of the heap.

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, ACM SIGPLAN Notices, v.38 n.7, July 2003
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
• 3: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 4: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 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: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 7: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 8: Daniel G. Bobrow , Daniel L. Murphy, A note on the efficiency of a LISP computation in a paged machine, Communications of the ACM, v.11 n.8, p.558, Aug. 1968 [doi>10.1145/363567.363581]
• 9: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 10: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 11: G. Chen , R. Shetty , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , M. Wolczko, Tuning garbage collection for reducing memory system energy in an embedded java environment, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.27-55, November 2002 [doi>10.1145/581888.581892]
• 12: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 13: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
• 14: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 15: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 16: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 17: Culler, D. E., Hill, J., Buonadonna, P., Szewczyk, R., and Woo, A. A network-centric approach to embedded software for tiny devices.
• 18: Steven M. Donahue , Matthew P. Hampton , Morgan Deters , Jonathan M. Nye , Ron Cytron , Krishna M. Kavi, Storage Allocation for Real-Time, Embedded Systems, Proceedings of the First International Workshop on Embedded Software, p.131-147, October 08-10, 2001
• 19: Embedded Microprocessor Benchmark Consortium. Java GrinderBench version 1.0. www.eembc.org, 2004.
• 20: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 21: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 22: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 23: Henriksson, R. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.
• 24: IBM Corporation. Websphere micro environment. www.ibm.com/software/wireless/wme, 2004.
• 25: Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, 1997
• 26: Jones, R., and Lins, R. Garbage Collection. John Wiley and Sons, 1996.
• 27: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 28: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 29: Patrik Persson, Live memory analysis for garbage collection in embedded systems, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.45-54, May 05-05, 1999, Atlanta, Georgia, United States
• 30: Tobias Ritzau , Peter Fritzson, Decreasing Memory Overhead in Hard Real-Time Garbage Collection, Proceedings of the Second International Conference on Embedded Software, p.213-226, October 07-09, 2002
• 31: Douglas T. Ross, The AED free storage package, Communications of the ACM, v.10 n.8, p.481-492, Aug. 1967 [doi>10.1145/363534.363546]
• 32: Saunders, R. A. The LISP system for the Q-32 computer. In The Programming Language LISP: Its Operation and Applications, E. C. Berkeley and D. G. Bobrow, Eds. MIT Press, Cambridge, Massachussetts, 1964, pp. 220--238.
• 33: 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]
• 34: 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]
• 35: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 36: Robert Virding, A Garbage Collector for the Concurrent Real-Time Language Erlang, Proceedings of the International Workshop on Memory Management, p.343-354, September 27-29, 1995
• 37: Wilson, G., Ostrem, J., and Bey, C. Palm OS Programmer's Companion, vol. 1. Palm Source, Inc., 2003. Document no. 3004-008.

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Memory management (garbage collection)
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
compaction, fragmentation, mark-and-sweep, tracing