Tax-and-spend: democratic scheduling for real-time garbage collection

ABSTRACT

Real-time Garbage Collection (RTGC) has recently advanced to the point where it is being used in production for financial trading, military command-and-control, and telecommunications. However, among potential users of RTGC, there is enormous diversity in both application requirements and deployment environments.

Previously described RTGCs tend to work well in a narrow band of possible environments, leading to fragile systems and limiting adoption of real-time garbage collection technology.

This paper introduces a collector scheduling methodology called tax-and-spend and the collector design revisions needed to support it. Tax-and-spend provides a general mechanism which works well across a variety of application, machine, and operating system configurations. Tax-and-spend subsumes the predominant pre-existing RTGC scheduling techniques. It allows different policies to be applied in different contexts depending on the needs of the application. Virtual machines can co-exist compositionally on a single machine.

We describe the implementation of our system, Metronome-TS, as an extension of the Metronome collector in IBM's Real-time J9 virtual machine product, and we evaluate it running on an 8-way SMP blade with a real-time Linux kernel. Compared to the state-of-the-art Metronome system on which it is based, implemented in the identical infrastructure, it achieves almost 3x shorter latencies, comparable utilization at a 2.5x shorter time window, and mean throughput improvements of 10-20%.

REFERENCES

• 1: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 2: Auerbach, J., Bacon, D. F., Bömers, F., and Cheng, P. Real-time music synthesis in Java using the Metronome garbage collector. In Proc. International Computer Music Conference (Copenhagen, Demmark, 2007), Lecture Notes in Computer Science.
• 3: Joshua Auerbach , David F. Bacon , Daniel T. Iercan , Christoph M. Kirsch , V. T. Rajan , Harald Roeck , Rainer Trummer, Java takes flight: time-portable real-time programming with exotasks, ACM SIGPLAN Notices, v.42 n.7, July 2007
• 4: Joshua Auerbach , David F. Bacon , Bob Blainey , Perry Cheng , Michael Dawson , Mike Fulton , David Grove , Darren Hart , Mark Stoodley, Design and implementation of a comprehensive real-time java virtual machine, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289927.1289967]
• 5: Bacon, D. F., Cheng, P., Frampton, D., Grove, D., Hauswirth, M., and Rajan, V. On-line visualization and analysis of real-time systems with TuningFork (demonstration). In Compiler Construction (Vienna, Austria, Mar. 2006), vol. 3923 of Lecture Notes in Computer Science, Springer-Verlag, pp. 96--100.
• 6: David F. Bacon , Perry Cheng , David Grove , Martin T. Vechev, Syncopation: generational real-time garbage collection in the metronome, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 7: 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
• 8: 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]
• 9: BEA. BEA WebLogic real time: Predictable mission-critical performance for java - today. Technical white paper available at http://www.bea.com, Jan. 2006.
• 10: Buyya, R., Abramson, D., Giddy, J., and Stockinger, H. Economic models for resource management and scheduling in grid computing, 2002.
• 11: Perry Cheng , Guy Blelloch , Robert Harper, Scalable real-time parallel garbage collection for symmetric multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 2001
• 12: 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
• 13: Cliff Click , Gil Tene , Michael Wolf, The pauseless GC algorithm, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064988]
• 14: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 15: Henriksson, R. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.
• 16: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• 17: Brian D. Marsh , Michael L. Scott , Thomas J. LeBlanc , Evangelos P. Markatos, First-class user-level threads, ACM SIGOPS Operating Systems Review, v.25 n.5, p.110-121, Oct. 1991
• 18: McCloskey, B., Bacon, D. F., Cheng, P., and Grove, D. Staccato: A parallel and concurrent real-time compacting garbage collector for multiprocessors. Tech. rep., IBM Research, Apr. 2008.
• 19: Scott Nettles , James O'Toole, Real-time replication garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.217-226, June 21-25, 1993, Albuquerque, New Mexico, United States
• 20: Filip Pizlo , Erez Petrank , Bjarne Steensgaard, A study of concurrent real-time garbage collectors, ACM SIGPLAN Notices, v.43 n.6, June 2008
• 21: Filip Pizlo , Jan Vitek, An Emprical Evaluation of Memory Management Alternatives for Real-Time Java, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.35-46, December 05-08, 2006 [doi>10.1109/RTSS.2006.9]
• 22: Prasad, V., Cohen, W., Eigler, F. C., Hunt, M., Keniston, J., and Chen, B. Locating system problems using dynamic instrumentation. In OSL '05: Proceedings of the Linux Symposium (2005), vol. 2, pp. 49--64.
• 23: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 24: 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]
• 25: Michael Stonebraker , Robert Devine , Marcel Kornacker , Witold Litwin , Avi Pfeffer , Adam Sah , Carl Staelin, An economic paradigm for query processing and data migration in mariposa, Proceedings of the third international conference on on Parallel and distributed information systems, p.58-68, October 1994, Autin, Texas, United States
• 26: TuningFork Visualization Platform. tuningforkvp.sourceforge.net.
• 27: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

General Terms:
Experimentation, Languages, Performance

Keywords:
garbage collection, java, jvm, real time