Allocation-phase aware thread scheduling policies to improve garbage collection performance

ABSTRACT

Past studies have shown that objects are created and then die in phases. Thus, one way to sustain good garbage collection efficiency is to have a large enough heap to allow many allocation phases to complete and most of the objects to die before invoking garbage collection. However, such an operating environment is hard to maintain in large multithreaded applications because most typical time-sharing schedulers are not allocation-phase cognizant; i.e., they often schedule threads in a way that prevents them from completing their allocation phases quickly. Thus, when garbage collection is invoked, most allocation phases have yet to be completed, resulting in poor collection efficiency. We introduce two new scheduling strategies, LARF (lower allocation rate first) and MQRR (memory-quantum round robin) designed to be allocation-phase aware by assigning higher execution priority to threads in computation-oriented phases. The simulation results show thatallthe reductions of the garbage collection time in a generational collector can range from 0%-27% when compare to a round robin scheduler. The reductions of the overall execution time and the average thread turnaround time range from -0.1%-3% and -0.1%-13%, respectively.

REFERENCES

• 1: J. Aas. Understanding the Linux 2.6.8.1 Scheduler. On--line article, 2006. http://josh.trancesoftware.com/linux/linux cpu scheduler.pdf.
• 2: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 3: 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
• 4: Henry G. Baker, Infant mortality and generational garbage collection, ACM SIGPLAN Notices, v.28 n.4, p.55-57, April 1993 [doi>10.1145/152739.152747]
• 5: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 6: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
• 7: William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, ACM SIGPLAN Notices, v.32 n.5, p.97-108, May 1997
• 8: Chris Grzegorczyk , Sunil Soman , Chandra Krintz , Rich Wolski, Isla Vista Heap Sizing: Using Feedback to Avoid Paging, Proceedings of the International Symposium on Code Generation and Optimization, p.325-340, March 11-14, 2007 [doi>10.1109/CGO.2007.20]
• 9: Matthias Hauswirth , Peter F. Sweeney , Amer Diwan , Michael Hind, Vertical profiling: understanding the behavior of object-priented applications, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 10: Matthew Hertz , Emery D. Berger, Quantifying the performance of garbage collection vs. explicit memory management, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 11: Matthew Hertz , Stephen M Blackburn , J Eliot B Moss , Kathryn S. McKinley , Darko Stefanović, Error-free garbage collection traces: how to cheat and not get caught, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 12: H. Hibino, K. Kourai, and S. Shiba. Difference of Degradation Schemes among Operating Systems: Experimental Analysis for Web Application Servers. In Workshop on Dependable Software, Tools and Methods, Yokohama, Japan, July 2005. http://www.csg.is.titech.ac.jp/paper/hibinodsn2005.pdf.
• 13: Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 14: JBoss. Jboss Application Server. Product Literature, Last Retrieved: June 2007. http://www.jboss.org/products/jbossas.
• 15: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 16: Lime Wire, LLC. Lime Wire. Web Document, 2007. http://www.limewire.org.
• 17: Microsoft. About the Common Language Runtime (CLR). http://www.gotdotnet.com/team/clr/about clr.aspx.
• 18: Girija J. Narlikar, Scheduling threads for low space requirement and good locality, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.83-95, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305629]
• 19: James Philbin , Jan Edler , Otto J. Anshus , Craig C. Douglas , Kai Li, Thread scheduling for cache locality, ACM SIGOPS Operating Systems Review, v.30 n.5, p.60-71, Dec. 1996
• 20: Robert Allen Shaw, Empirical analysis of a LISP system, Stanford University, Stanford, CA, 1988
• 21: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, EELRU: simple and effective adaptive page replacement, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.122-133, May 01-04, 1999, Atlanta, Georgia, United States
• 22: Standard Performance Evaluation Corporation. SPECjbb2000, 2000. http://www.spec.org/osg/jbb2000/docs/whitepaper.html.
• 23: Standard Performance Evaluation Corporation. SPECjAppServer2004 User's Guide. On--Line User's Guide, 2004. http://www.spec.org/osg/jAppServer2004/docs/UserGuide.html.
• 24: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.370-381, November 01-05, 1999, Denver, Colorado, United States
• 25: Sun Microsystems. ECPERF. http://java.sun.com/developer/earlyAccess/j2ee/ecperf/download.html.
• 26: Sun Microsystems. Performance Documentation for the Java HotSpot VM. On--Line Documentation, Last Retrieved: June 2007. http://java.sun.com/docs/hotspot/.
• 27: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 28: P. R. Wilson, Opportunistic garbage collection, ACM SIGPLAN Notices, v.23 n.12, p.98-102, Dec. 1988 [doi>10.1145/57669.57679]
• 29: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 30: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
• 31: F. Xian, W. Srisa--an, C. Jia, and H. Jiang. AS--GC: An Efficient Generational Garbage Collector for Java Application Servers. In Proceedings of the 21st European Conference on Object--Oriented Programming (ECOOP), pages 126--150, Berlin, Germany, July 2007.
• 32: Feng Xian , Witawas Srisa-an , Hong Jiang, Investigating throughput degradation behavior of Java application servers: a view from inside a virtual machine, Proceedings of the 4th international symposium on Principles and practice of programming in Java, August 30-September 01, 2006, Mannheim, Germany [doi>10.1145/1168054.1168061]
• 33: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington

INDEX TERMS

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

General Terms:
Experimentation, Languages, Performance

Keywords:
garbage collection, thread scheduling