|
 ABSTRACT
We describe and prove the correctness of a new concurrent mark-and-sweep garbage collection algorithm. This algorithm derives from the classical on-the-fly algorithm from Dijkstra et al. [9]. A distinguishing feature of our algorithm is that it supports multiprocessor environments where the registers of running processes are not readily accessible, without imposing any overhead on the elementary operations of loading a register or reading or initializing a field. Furthermore our collector never blocks running mutator processes except possibly on requests for free memory; in particular, updating a field or creating or marking or sweeping a heap object does not involve system-dependent synchronization primitives such as locks. We also provide support for process creation and deletion, and for managing an extensible heap of variable-sized objects.
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.
| |
1
|
|
 |
2
|
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
CYPRESS. BiCMOS/CMOS data book. Cypress Semiconductor, 1991.
|
| |
9
|
|
| |
10
|
|
| |
11
|
HERLIHY, M., AND Moss, J. E. S. Non-blocking garbage collection for multiprocessors. Technical report CRL 90/9, DEC Cambridge Research Lab., 1990.
|
| |
12
|
|
| |
13
|
|
| |
14
|
KUNG, H. T., AND SONG, S. W. An efficient parallel garbage collection system and its correctness proof. In Foundations of Computer Science 1977 (1977), IEEE Computer Society Press, pp. 120-131.
|
| |
15
|
LAMPORT, L. Garbage collection with multiple processes" an exercise in parallelism. In Proc. IEEE Conf. Parallel Processing (1976), pp. 50-54.
|
| |
16
|
LAMPORT, L. The temporal logic of actions. Research report 79, DEC Systems Research Center, 1991.
|
| |
17
|
LEROY, X., AND MAUNY, M. The Canal Light system, version 0.5 -- documentation and user's guide. Technical report L-5, INRIA, 1992.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
CITED BY 42
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sara Porat , Marina Biberstein , Larry Koved , Bilha Mendelson, Automatic detection of immutable fields in Java, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.10, November 13-16, 2000, Mississauga, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
|
|
|
|
|
|
Yoav Ossia , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Avi Owshanko, A parallel, incremental and concurrent GC for servers, ACM SIGPLAN Notices, v.37 n.5, May 2002
|
|
|
|
|
|
|
|
|
Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005
|
|
|
|
|
|
|
|
|
Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the JavaTM Virtual Machine Research and Technology Symposium on JavaTM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
|
|
|
Katherine Barabash , Niv Buchbinder , Tamar Domani , Elliot K. Kolodner , Yoav Ossia , Shlomit S. Pinter , Janice Shepherd , Ron Sivan , Victor Umansky, Mostly accurate stack scanning, Proceedings of the JavaTM Virtual Machine Research and Technology Symposium on JavaTM Virtual Machine Research and Technology Symposium, p.19-19, April 23-24, 2001, Monterey, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
|
|
|
|
|
|
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
|
|
|
Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.4