Lock-free, parallel remembered sets

Details Lock-free, parallel remembered sets Lock-free, parallel remembered sets

2005-11-15

2005-11-15

Rones, Charles (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06965905

ABSTRACT:
A multi-threaded garbage collector operates in increments and maintains, for each of a plurality of car sections in which it has divided a portion of the heap, a respective remembered set of the locations at which it has found references to objects in those car sections. It stores the remembered sets in respective hash tables, whose contents it updates in a scanning operation, executed concurrently by multiple threads, in which it finds references and records their locations in the appropriate tables. Occasionally, one of the threads replaces the hash table for a given car section. Rather than wait for the replacement operation to be completed, a thread that has an entry to be made into that car section's remembered set accesses the old table to find out whether the entry has already been made. If so, no new entry is necessary. Otherwise, it places an entry into the old table and sometimes places an insertion record containing that entry into a linked list associated with that car section. When the reclaiming thread has finished transferring information from the old table to the new table, it transfers information from the linked list of insertion records into the new table, too. In this way, the replacement process is not a bottleneck to other threads' performing update operations.

REFERENCES:
patent: 6185581 (2001-02-01), Garthwaite
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6363403 (2002-03-01), Roy et al.
patent: 6381738 (2002-04-01), Choi et al.
patent: 6424977 (2002-07-01), Garthwaite
patent: 6490599 (2002-12-01), Kolodner et al.
patent: 6826757 (2004-11-01), Steele et al.
patent: 6845437 (2005-01-01), Borman et al.
patent: 6868488 (2005-03-01), Garthwaite
Jones and Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management,” 1996, pp. 165-179, Wiley, New York.
Paul Wilson, “Uniprocessor Garbage Collection Techniques,” Technical Report, University of Texas, 1994.
Hudson and Moss, “Incremental Collection of Mature Objects,” Proceedings of International Workshop on Memory Management, 1992, Springer-Verlag.
Grarup and Seligmann, “Incremental Mature Garbage Collection,” M.Sc. Thesis, Available at http://www.daimi.au.dk/˜jacobse/Papers/, 1995.
Seligmann and Grarup, “Incremental Mature Garbage Collection Using the Train Algorithm,” Proceedings of ECOOP '95, Ninth European Conference on Object-Oriented Programming, 1995, http://www.daimi.au.dk/˜ jacobse/Papers/.
Clark and Mason, “Compacting Garbage Collection can be Fast and Simple,” Software-Practice and Experience, Feb. 1996, pp. 177-194, vol. 26, No. 2.
Henry Baker, “List Processing in Real Time on a Serial Computer,” Communications of the ACM 21, 4, Apr. 1978, pp. 280-294.
Appel, Ellis and Li; “Real-time Concurrent Collection on Stock Multiprocessors,” ACM SIGPLAN Notices, 1988.
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, pp. 108-113, Aug. 1984, Austin, Texas.
Herlihy and Moss, “Lock-Free Garbage Collection for Multiprocessors,” ACM SPAA, 1991, pp. 229-236.
Bacon, Attanasio, Lee, Rajan, and Smith, “Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector,” SIGPLAN Conference on Programming Language Design and Implementation, Snowbird, Utah, Jun. 2001.
James Stamos, “Static Grouping of Small Objects to Enhance Performance of a Paged Virtual Memory,” ACM Transactions on Computer Systems, vol. 2, No. 2, pp. 155-180, May 1984.
David A. Moon, “Garbage Collection in a Large Lisp System,” Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Austin, Texas, Aug. 1984, pp. 235-246.
Robert Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System,” Communications of the ACM, Sep. 1988, pp. 1128-1138, vol. 31, No. 9.
Wilson, Lam and Moher, “Effective Static-Graph Reorganization to Improve Locality in Garbage Collected Systems,” Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 1991, Toronto, Ontario, Canada.
Lam, Wilson, and Moher, “Object Type Directed Garbage Collection to Improve Locality,” Proceedings of the International Workshop on Memory Management '92, St. Malo, France, Sep. 1992, pp. 404-425.
Chilimbi and Larus, “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement,” International Symposium on Memory Management, Oct. 1998.
Lieberman and Hewitt, “A real-time garbage collector based on the lifetimes of objects,” Communications of the ACM, 1983, pp. 419-429, vol. 26, No. 6.
David Ungar, “Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm,” ACM SIGPLAN Notices, Apr. 1984, pp. 157-167, vol. 19, No. 5.
Andrew W. Appel, “Simple Generational Garbage Collection and Fast Allocation,” Software Practice and Experience, 1989, pp. 171-183, vol. 19, No. 2.
Hudson and Diwan, “Adaptive Garbage Collection for Modula-3 and Smalltalk,” in OOPSLA/ECOOP Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1990, Edited by Eric Jul and Niels-Cristial Juul.
Hudson and Hosking, “Remembered sets can also play cards,” in OOPSLA/ECOOP Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1993, Edited by Moss, Wilson, and Zorn.
Hosking and Moss, “Protection traps and alternatives for memory management of an object-oriented language,” ACM Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles, Dec. 1993, pp. 106-119, vol. 27, No. 5.
Hosking, Moss, and Stefanovic, “A Comparative Performance Evaluation of Write Barrier Implementation,” in OOPSLA ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Oct. 1992, pp. 92-109, vol 27, No. 10, ACM SIGPLAN Notices, Vancouver, BC, ACM Press.
Patrick G. Sobalvarro, “A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers,” Massachusetts Institute of Technology, AITR-1417, 1988.

Affiliated with

Also associated with

Rating

Lock-free, parallel remembered sets does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lock-free, parallel remembered sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free, parallel remembered sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3454620