Faisal Aslam
ABSTRACT
The ability of tiny embedded devices to run large and feature-rich Java programs is typically constrained by the amount of memory installed on those devices. Furthermore, the useful operation of such devices in a wireless sensor application is limited by their battery life. We propose a garbage collection (GC) scheme called Offline GC which alleviates both these limitations. Our approach defies the current practice in which an object may be deallocated only if it is unreachable. Offline GC allows freeing an object that is still reachable but is guaranteed not to be used again in the program. Furthermore, it may deallocate an object inside a function, a loop or a block where it is last used, even if that object is assigned to a global field. This leads to a larger amount of memory available to a program.
Based on an inter-procedural and field-sensitive data flow analysis we identify, during program compilation, the point at which an object can safely be deallocated at runtime. We have designed three algorithms for the purpose of making these offline deallocation decisions. Our implementation of Offline GC indicates a significant reduction in the amount of RAM and the number of CPU cycles needed to run a variety of benchmark programs. Offline GC is shown to increase the average amount of RAM available to a program by up to 82% compared to a typical online garbage collector. Furthermore, the number of CPU cycles consumed in freeing the memory is reduced by up to 94% when Offline GC is used.
Supplemental Material
- ETH Zurich. The Sensor Network Museum. http://www.snm.ethz.ch/Main/HomePage, {Last Accessed: 15.08.2011}.Google Scholar
- Niels Brouwers, Koen Langendoen, and Peter Corke. Darjeeling, a Feature-Rich VM for the Resource Poor. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys '09, pages 169--182, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- Faisal Aslam, Luminous Fennell, Christian Schindelhauer, Peter Thiemann, Gidon Ernst, Elmar Haussmann, Stefan Rührup, and Zastash Afzal Uzmi. Optimized Java Binary and Virtual Machine for Tiny Motes. In Distributed Computing in Sensor Systems (DCOSS), volume 6131, chapter 2, pages 15--30. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. Google ScholarDigital Library
- Janice J. Heiss. Sentilla's Pervasive Computing -- The Universe Is the Computer. 2008 JavaOne Conference.Google Scholar
- Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, September 1996. Google ScholarDigital Library
- Sigmund Cherem and Radu Rugina. Uniqueness Inference for Compile-Time Object Deallocation. In Proceedings of the 6th international symposium on Memory management, ISMM '07, pages 117--128, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- Samuel Guyer, Kathryn McKinley, and Daniel Frampton. Free-Me: A Static Analysis for Automatic Individual Object Reclamation. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '06, pages 364--375, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- Elvira Albert, Samir Genaim, and Miguel Gomez-Zamalloa. Heap Space Analysis for Java Bytecode. In Proceedings of the 6th International Symposium on Memory Management, ISMM '07, pages 105--116, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. Escape Analysis for Java. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '99, pages 1--19, New York, NY, USA, 1999. ACM. Google ScholarDigital Library
- Bruno Blanchet. Escape Analysis for Java#8482;: Theory and Practice. ACM Transactions on Programming Languages and Systems (TOPLAS), 25:713--775, November 2003. Google ScholarDigital Library
- Tim Lindholm and Frank Yellin. Java Virtual Machine Specification. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 1999. Google ScholarDigital Library
- Source code. GCBench and GCOld benchmarks. http://www.cs.cmu.edu/~spoons/gc/benchmarks.html, {Last Accessed: 15.08.2011}.Google Scholar
- Omprakash Gnawali, Rodrigo Fonseca, Kyle Jamieson, David Moss, and Philip Levis. Collection Tree Protocol. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys '09, pages 1--14. ACM, 2009. Google ScholarDigital Library
- Ian Chakeres and Charles Perkins. Dynamic MANET On-demand (DYMO) Routing. IETF (work in progress), 2010.Google Scholar
- David Bacon, Perry Cheng, and David Grove. Garbage Collection for Embedded Systems. In Proceedings of the 4th ACM International Conference on Embedded Software, EM-SOFT '04, pages 125--136, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- Kumar Shiv, Kingsum Chow, Yanping Wang, and Dmitry Petrochenko. SPECjvm2008 Performance Characterization. In Proceedings of the 2009 SPEC Benchmark Workshop on Computer Performance Evaluation and Benchmarking, pages 17--35, Berlin, Heidelberg, 2009. Springer-Verlag. Google ScholarDigital Library
- Daniel Spoonhower, Guy Blelloch, and Robert Harper. Using Page Residency to Balance Tradeoffs in Tracing Garbage Collection. In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments, VEE '05, pages 57--67, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- Crossbow Technology. Wireless Sensor Networks. http://www.xbow.com, {Last Accessed: 15.02.2011}.Google Scholar
- Ben Lawrence Titzer, Daniel Lee, and Jens Palsberg. Avrora: Scalable Sensor Network Simulation with Precise Timing. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, IPSN '05, Piscataway, NJ, USA, 2005. IEEE Press. Google ScholarDigital Library
- Luminous Fennell. Garbage Collection for TakaTuka, Bachelors Thesis. University of Freiburg, Germany, 2010.Google Scholar
- Jeffrey Barth. Shifting Garbage Collection Overhead to Compile Time. Communications of the ACM (CACM), 20:513--518, July 1977. Google ScholarDigital Library
- Pramod Joisha. Overlooking Roots: A Framework for Making Nondeferred Reference-Counting Garbage Collection Fast. In Proceedings of the 6th International Symposium on Memory Management, ISMM '07, pages 141--158, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- Wolfram Schulte. Deriving Residual Reference Count Garbage Collectors. In Symposium on Programming Language Implementation and Logic Programming (PLILP), pages 102--116. Springer-Verlag, 1994. Google ScholarDigital Library
- Ran Shaham, Eran Yahav, Elliot Kolodner, and Mooly Sagiv. Establishing Local Temporal Heap Safety Properties with Applications to Compile-Time Memory Management. In Static Analysis, volume 2694 of Lecture Notes in Computer Science, pages 483--503. Springer Berlin/Heidelberg, 2003. Google ScholarDigital Library
- Ole Agesen, David Detlefs, and J. Eliot Moss. Garbage collection and local variable type-precision and liveness in Java virtual machines. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI '98, pages 269--279, New York, NY, USA, 1998. ACM. Google ScholarDigital Library
- Sigmund Cherem and Radu Rugina. Compile-Time Deallocation of Individual Objects. In Proceedings of the 5th International Symposium on Memory Management, ISMM '06, pages 138--149, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- Dan Grossman, Greg Morrisett, Trevor Jim, Michael Hicks, Yanling Wang, and James Cheney. Region-Based Memory Management in Cyclone. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, PLDI '02, pages 282--293, New York, NY, USA, 2002. ACM. Google ScholarDigital Library
- Neil Jones and Steven Muchnick. Flow Analysis and Optimization of LISP-like Structures. In Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '79, pages 244--256, New York, NY, USA, 1979. ACM. Google ScholarDigital Library
- Alexandru Stefan, Florin Craciun, and Wei-Ngan Chin. A Flow-Sensitive Region Inference for CLI. In Proceedings of the 6th Asian Symposium on Programming Languages and Systems, APLAS '08, pages 19--35, Berlin, Heidelberg, 2008. Springer-Verlag. Google ScholarDigital Library
- Sigmund Cherem and Radu Rugina. Region Analysis and Transformation for Java Programs. In Proceedings of the 4th International Symposium on Memory Management, ISMM '04, pages 85--96, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- David Gay and Alex Aiken. Memory Management with Explicit Regions. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI '98, pages 313--323, New York, NY, USA, 1998. ACM. Google ScholarDigital Library
Index Terms
- Offline GC: trashing reachable objects on tiny devices
Recommendations
A parallel, incremental and concurrent GC for servers
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementationMultithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for "server-oriented" GC include: ensuring short pause times on a multi-gigabyte heap, while minimizing ...
A parallel, incremental and concurrent GC for servers
Multithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for "server-oriented" GC include: ensuring short pause times on a multi-gigabyte heap, while minimizing ...
Mostly concurrent compaction for mark-sweep GC
ISMM '04: Proceedings of the 4th international symposium on Memory managementA memory manager that does not move objects may suffer from memory <i>fragmentation</i>. <i>Compaction</i> is an efficient, and sometimes inevitable, mechanism for reducing fragmentation. A Mark-Sweep garbage collector must occasionally execute a ...
Comments