Real-time concurrent collection on stock multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Real-time concurrent collection on stock multiprocessors

Full text

Pdf (1.21 MB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation table of contents

Atlanta, Georgia, United States

Pages: 11 - 20

Year of Publication: 1988

ISBN:0-89791-269-1

Also published in ...

Authors

A. W. Appel	Princeton Univ., Princeton, NJ
J. R. Ellis	Systems Research Center, Palo Alto, CA
K. Li	Princeton Univ., Princeton, NJ

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 48, Citation Count: 83

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/53990.53992 What is a DOI?

ABSTRACT

We've designed and implemented a copying garbage-collection algorithm that is efficient, real-time, concurrent, runs on commercial uniprocessors and shared-memory multiprocessors, and requires no change to compilers. The algorithm uses standard virtual-memory hardware to detect references to “from space” objects and to synchronize the collector and mutator threads. We've implemented and measured a prototype running on SRC's 5-processor Firefly. It will be straightforward to merge our techniques with generational collection. An incremental, non-concurrent version could be implemented easily on many versions of Unix.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Appel 87	Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
	Baker 78	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]
	Brooks 84	Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
	Cardelli 84	Luca Cardelli, Compiling a functional language, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.208-217, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802037]
	Gabriel 85	Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
	Halstead 84	Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
	Hickey 84	Tim Hickey , Jacques Cohen, Performance analysis of on-the-fly garbage collection, Communications of the ACM, v.27 n.11, p.1143-1154, Nov. 1984 [doi>10.1145/1968.358298]
	Li 86	Kai Li, Shared virtual memory on loosely coupled multiprocessors, 1986
	Lieberman 83	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
	Moon 84	David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
	North 87	S. C. North , J. H. Reppy, Concurrent garbage collection on stock hardware, Proc. of a conference on Functional programming languages and computer architecture, p.113-133, October 1987, Portland, Oregon, United States
	Rovner 85a	Paul Rovner. On Adding Garbage Collection and Runtime Types to a Strongly-Typed, Statically-Checked, Concurrent Language. Xerox PARC Report CSL-84-7, 1985.
	Rovner 85b	Paul Rovner, Roy Levin, and John Wick. On Extending Modula-2 For Building Large, Integrated Systems. Research Report 3, DEC Systems Research Center, 1985.
	Shaw 87	Robert A. Shaw. Improving Garbage Collector Performance in Virtual Memory. Technical Report CSL-TR-87-323, Computer Systems Laboratory, Stanford University, 1987.
	Thacker 87	Charles P. Thacker , Lawrence C. Stewart, Firefly: a multiprocessor workstation, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.164-172, October 1987, Palo Alto, California, United States
	Ungar 86	David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987

CITED BY 83

	Benjamin Zorn, Comparing mark-and sweep and stop-and-copy garbage collection, Proceedings of the 1990 ACM conference on LISP and functional programming, p.87-98, June 27-29, 1990, Nice, France
	Kelvin D. Nilsen , William J. Schmidt, Cost-effective object space management for hardware-assisted real-time garbage collection, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.338-354, Dec. 1992
	Simon L. Peyton Jones , Jon Salkild, The spineless tagless G-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.184-201, September 11-13, 1989, Imperial College, London, United Kingdom
	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
	Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, ACM SIGPLAN Notices, v.36 n.11, p.367-380, 11/01/2001
	O. Kaser , S. Pawagi , C. R. Ramakrishnan , I. V. Ramakrishnan , R. C. Sekar, Fast parallel implementation of lazy languages—the EQUALS experience, ACM SIGPLAN Lisp Pointers, v.V n.1, p.335-344, Jan. 1992
	David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.92-103, May 2001
	K. Li , J. F. Naughton , J. S. Plank, Low-Latency, Concurrent Checkpointing for Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.874-879, August 1994
	Eric Cooper , Scott Nettles , Indira Subramanian, Improving the performance of SML garbage collection using application-specific virtual memory management, ACM SIGPLAN Lisp Pointers, v.V n.1, p.43-52, Jan. 1992
	Laurent Amsaleg , Michael J. Franklin , Olivier Gruber, Garbage collection for a client-server persistent object store, ACM Transactions on Computer Systems (TOCS), v.17 n.3, p.153-201, Aug. 1999
	Ralph E. Johnson, Reducing the latency of a real-time garbage collector, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.46-58, March 1992
	Olin Shivers , James W. Clark , Roland McGrath, Atomic heap transactions and fine-grain interrupts, ACM SIGPLAN Notices, v.34 n.9, p.48-59, Sept. 1999
	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France
	Lorenz Huelsbergen , Phil Winterbottom, Very concurrent mark-&-sweep garbage collection without fine-grain synchronization, ACM SIGPLAN Notices, v.34 n.3, p.166-175, March 1999
	William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, ACM SIGPLAN Notices, v.29 n.11, p.76-85, Nov. 1994
	James O'Toole , Scott Nettles, Concurrent replicating garbage collection, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.34-42, July-Sept. 1994
	Jeffrey S. Chase , Henry M. Levy , Edward D. Lazowska , Miche Baker-Harvey, Lightweight shared objects in a 64-bit operating system, ACM SIGPLAN Notices, v.27 n.10, p.397-413, Oct. 1992
	Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States
	Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.34 n.5, p.104-117, May 1999
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States
	Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
	Per-Åke Larson , Murali Krishnan, Memory allocation for long-running server applications, ACM SIGPLAN Notices, v.34 n.3, p.176-185, March 1999
	Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, ACM SIGPLAN Notices, v.27 n.9, p.175-186, Sept. 1992
	Daniel M. Yellin , Robert E. Strom, INC: a language for incremental computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.211-236, April 1991
	Niels Christian Juul , Eric Jul, Garbage collection in object oriented systems (workshop session), Proceedings of the European conference on Object-oriented programming addendum : systems, languages, and applications: systems, languages, and applications, p.35-41, October 1990, Ottawa, Canada
	Ravi Sharma , Mary Lou Soffa, Parallel generational garbage collection, ACM SIGPLAN Notices, v.26 n.11, p.16-32, Nov. 1991
	James R. Larus , Brad Richards , Guhan Viswanathan, LCM: memory system support for parallel language implementation, ACM SIGPLAN Notices, v.29 n.11, p.208-218, Nov. 1994
	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
	K. Li , J. F. Naughton , J. S. Plank, Real-time, concurrent checkpoint for parallel programs, ACM SIGPLAN Notices, v.25 n.3, p.79-88, Mar. 1990
	Chandramohan A. Thekkath , Henry M. Levy, Hardware and software support for efficient exception handling, ACM SIGPLAN Notices, v.29 n.11, p.110-119, Nov. 1994
	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
	Toshio Endo , Kenjiro Taura, Reducing pause time of conservative collectors, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
	Pekka P. Pirinen, Barrier techniques for incremental tracing, ACM SIGPLAN Notices, v.34 n.3, p.20-25, March 1999
	Thomas E. Anderson , Henry M. Levy , Brian N. Bershad , Edward D. Lazowska, The interaction of architecture and operating system design, ACM SIGPLAN Notices, v.26 n.4, p.108-120, Apr. 1991
	Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, ACM SIGPLAN Notices, v.26 n.4, p.96-107, Apr. 1991
	Lennart Augustsson , Thomas Johnsson, Parallel graph reduction with the (v , G)-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.202-213, September 11-13, 1989, Imperial College, London, United Kingdom
	John H. Reppy, CML: A higher concurrent language, ACM SIGPLAN Notices, v.26 n.6, p.293-305, June 1991
	Sven Gestegard Robertz , Roger Henriksson, Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003
	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
	Katherine Barabash , Yoav Ossia , Erez Petrank, Mostly concurrent garbage collection revisited, ACM SIGPLAN Notices, v.38 n.11, November 2003
	James O'Toole , Scott Nettles , David Gifford, Concurrent compacting garbage collection of a persistent heap, ACM SIGOPS Operating Systems Review, v.27 n.5, p.161-174, Dec. 1993
	Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States
	Suresh Jagannathan , Jim Philbin, A foundation for an efficient multi-threaded scheme system, ACM SIGPLAN Lisp Pointers, v.V n.1, p.345-357, Jan. 1992
	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, ACM SIGPLAN Notices, v.35 n.9, p.257-267, Sept. 2000
	Venkata K. Pingali , Sally A. McKee , Wilson C. Hseih , John B. Carter, Computation regrouping: restructuring programs for temporal data cache locality, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Venkata K. Pingali , Sally A. McKee , Wilson C. Hsieh , John B. Carter, Restructuring computations for temporal data cache locality, International Journal of Parallel Programming, v.31 n.4, p.305-338, August 2003
	Adam Wick , Matthew Flatt, Memory accounting without partitions, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Yoav Ossia , Ori Ben-Yitzhak , Marc Segal, Mostly concurrent compaction for mark-sweep GC, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Stephen W. Keckler , Andrew Chang , Whay S. Lee , Sandeep Chatterjee , William J. Dally, Concurrent Event Handling through Multithreading, IEEE Transactions on Computers, v.48 n.9, p.903-916, September 1999
	A. Imai , E. Tick, Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1030-1040, September 1993
	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
	Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, ACM SIGPLAN Notices, v.40 n.6, June 2005
	David F. Bacon , Perry Cheng , David Grove , Martin T. Vechev, Syncopation: generational real-time garbage collection in the metronome, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006
	Henry G. Baker, CONS should not CONS its arguments, or, a lazy alloc is a smart alloc, ACM SIGPLAN Notices, v.27 n.3, p.24-34, March 1992
	Michal Wegiel , Chandra Krintz, The mapping collector: virtual memory support for generational, parallel, and concurrent compaction, ACM SIGOPS Operating Systems Review, v.42 n.2, March 2008
	Antony L. Hosking, Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Martin T. Vechev , Eran Yahav , David F. Bacon, Correctness-preserving derivation of concurrent garbage collection algorithms, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Hyeonjoong Cho , Chewoo Na , Binoy Ravindran , E. Douglas Jensen, On scheduling garbage collector in dynamic real-time systems with statistical timing assurances, Real-Time Systems, v.36 n.1-2, p.23-46, July 2007
	Paulo Ferreira , Marc Shapiro, Garbage collection and DSM consistency, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.17-es, November 14-17, 1994, Monterey, California
	David S. Wise , Brian Heck , Caleb Hess , Willie Hunt , Eric Ost, Research Demonstration of a Hardware Reference-Counting Heap, Lisp and Symbolic Computation, v.10 n.2, p.159-181, July 1997
	Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991
	Paul R. Wilson, Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware, ACM SIGARCH Computer Architecture News, v.19 n.4, p.6-13, June 1991
	Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992
	Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989
	Owen Kaser , C. R. Ramakrishnan , I. V. Ramakrishnan , R. C. Sekar, EQUALS – a fast parallel implementation of a lazy language, Journal of Functional Programming, v.7 n.2, p.183-217, March 1997
	Phil McGachey , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Vijay Menon , Bratin Saha , Tatiana Shpeisman, Concurrent GC leveraging transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	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
	Kenneth R. Anderson, Courage in profiles, ACM SIGPLAN Lisp Pointers, v.VIII n.1, p.11-29, Jan.-April 1995
	Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, ACM SIGARCH Computer Architecture News, v.36 n.3, p.115-126, June 2008
	Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove , Ben Biron , Charlie Gracie , Bill McCloskey , Aleksandar Micic , Ryan Sciampacone, Tax-and-spend: democratic scheduling for real-time garbage collection, Proceedings of the 7th ACM international conference on Embedded software, October 19-24, 2008, Atlanta, GA, USA
	Gabriel Kliot , Erez Petrank , Bjarne Steensgaard, A lock-free, concurrent, and incremental stack scanning for garbage collectors, Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 11-13, 2009, Washington, DC, USA
	Gary H. Sockut , Balakrishna R. Iyer, Online reorganization of databases, ACM Computing Surveys (CSUR), v.41 n.3, p.1-136, July 2009