Filip Pizlo
Erez Petrank
ABSTRACT
We present Stopless: a concurrent real-time garbage collector suitable for modern multiprocessors running parallel multithreaded applications. Creating a garbage-collected environment that supports real-time on modern platforms is notoriously hard,especially if real-time implies lock-freedom. Known real-time collectors either restrict the real-time guarantees to uniprocessors only, rely on special hardware, or just give up supporting atomic operations (which are crucial for lock-free software). Stopless is the first collector that provides real-time responsiveness while preserving lock-freedom, supporting atomic operations, controlling fragmentation by compaction, and supporting modern parallel platforms. Stopless is adequate for modern languages such as C# or Java. It was implemented on top of the Bartok compiler and runtime for C# and measurements demonstrate high responsiveness (a factor of a 100 better than previously published systems), virtually no pause times, good mutator utilization, and acceptable overheads.
- Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein. An efficient parallel heap compaction algorithm. In OOPSLA 2004. Google Scholar
Digital Library
- Matthew Arnold and Barbara G. Ryder. A framework for reducing the cost of instrumented code. In PLDI 2001. Google ScholarDigital Library
- David F. Bacon, Perry Cheng, and V.T. Rajan. A real--time garbage collecor with low overhead and consistent utilization. In POPL 2003. Google ScholarDigital Library
- Henry G. Baker. List processing in real--time on a serial computer. CACM, 21(4):280--94, 1978. Google ScholarDigital Library
- Katherine Barabash, Ori Ben--Yitzhak, Irit Goft, Elliot K. Kolodner, Victor Leikehman, Yoav Ossia, Avi Owshanko, and Erez Petrank. A parallel, incremental, mostly concurrent garbage collector for servers. ACM TOPLAS,27(6):1097--1146, November 2005. Google ScholarDigital Library
- Stephen M. Blackburn and Tony Hosking. Barriers: Friend or foe? In ISMM 2004. Google ScholarDigital Library
- Guy E. Blelloch and Perry Cheng. On bounding time and space for multiprocessor garbage collection. In PLDI 1999. Google ScholarDigital Library
- Hans--Juergen Boehm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157--164, 1991. Google ScholarDigital Library
- Rodney A. Brooks. Trading data space for reduced time and code space in real--time garbage collection on stock hardware. In LFP 1984. Google ScholarDigital Library
- Perry Cheng and Guy Blelloch. A parallel, real--time garbage collector. In PLDI, June 2001. Google ScholarDigital Library
- Cliff Click, Gil Tene, and Michael Wolf. The pauseless GC algorithm. In VEE 2005. Google ScholarDigital Library
- Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. CACM, 21(11):965--975, November 1978. Google ScholarDigital Library
- Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In POPL 1994. Google ScholarDigital Library
- Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi--threaded implementation of ML. In POPL 1993. Google ScholarDigital Library
- Tamar Domani, Elliot Kolodner, and Erez Petrank. A generational on--the--fly garbage collector for Java. In PLDI 2000. Google ScholarDigital Library
- Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Elliot E. Salant, Katherine Barabash, Itai Lahan, Erez Petrank, Igor Yanover, and Yossi Levanoni. Implementing an on--the--fly garbage collector for Java. In ISMM 2000. Google ScholarDigital Library
- Timothy L. Harris, Keir Fraser, and Ian A. Pratt. A practical multi--word compare--and--swap operation. In DISC 2002. Google ScholarDigital Library
- Roger Henriksson. Predictable automatic memory management for embedded systems. In OOPSLA '97 Workshop on Garbage Collection and Memory Management.Google Scholar
- Roger Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.Google Scholar
- Maurice Herlihy and J. Eliot B Moss. Lock--free garbage collection for multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 3(3), May 1992. Google ScholarDigital Library
- Richard L. Hudson and J. Eliot B. Moss. Sapphire: Copying GC without stopping the world. In Joint ACM Java Grande -- ISCOPE 2001 Conference, CA, June 2001. Google ScholarDigital Library
- Richard E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, July 1996. With a chapter on Distributed Garbage Collection by R. Lins.Google ScholarDigital Library
- Haim Kermany and Erez Petrank. The Compressor: Concurrent, incremental and parallel compaction. In PLDI 2006. Google ScholarDigital Library
- Yossi Levanoni and Erez Petrank. An on--the--fly reference counting garbage collector for Java. In OOPSLA 2001. Google ScholarDigital Library
- Henry Massalin and Calton Pu. A lock--free multiprocessor os kernel. SIGOPS Oper. Syst. Rev., 26(2):8, 1992. Google ScholarCross Ref
- Matthias Meyer. A true hardware read barrier. In J. Eliot B. Moss, editor, ISMM'06 2006. Google ScholarDigital Library
- Scott M. Nettles and James W. O'Toole. Real--time replication--based garbage collection. In PLDI 1993. Google ScholarDigital Library
- Yoav Ossia, Ori Ben--Yitzhak, Irit Goft, Elliot K. Kolodner, Victor Leikehman, and Avi Owshanko. A parallel, incremental and concurrent GC for servers. In PLDI 2002. Google ScholarDigital Library
- Tony Printezis and David Detlefs. A generational mostly--concurrent garbage collector. In ISMM 2000. Google ScholarDigital Library
- Sven Robertz. Applying priorities to memory allocation. In ISMM 2002. Google ScholarDigital Library
- Sven Gestegård Robertz and Roger Henriksson. Time--triggered garbage collection -- robust and adaptive real--time GC scheduling for embedded systems. In LCTES 2003.Google Scholar
- Daniel Spoonhower, Joshua Auerbach, David F. Bacon, Perry Cheng, and David Grove. Eventrons: A safe programming construct for high--frequency hard real--time applications. In PLDI 2006. Google ScholarDigital Library
- Guy L. Steele. Multiprocessing compactifying garbage collection. CACM, 18(9):495--508, September 1975. Google ScholarDigital Library
Index Terms
- Stopless: a real-time garbage collector for multiprocessors
Recommendations
A study of concurrent real-time garbage collectors
PLDI '08Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors ...
Concurrent, parallel, real-time garbage-collection
ISMM '10: Proceedings of the 2010 international symposium on Memory managementWith the current developments in CPU implementations, it becomes obvious that ever more parallel multicore systems will be used even in embedded controllers that require real-time guarantees. When garbage collection is used in these systems, parallel ...
A study of concurrent real-time garbage collectors
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationConcurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors ...
Comments