Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-04-24
2007-04-24
Gaffin, Jeffrey (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
10305832
ABSTRACT:
A garbage collector that employs the train algorithm to manage a generation in a computer system's dynamically allocated heap maintains for each of the generation's cars a respective remembered set that identifies all locations where references to objects in that car have been found by scanning locations identified by the mutator as having been modified. To avoid some of the expense of remembered-set updating, the collector refrains from attempting to add to a remembered set any reference located in a car that will be collected during the next collection increment. Additionally, if no mutator operation will occur before a collection set of one or more cars will be collected, any reference located outside that collection set but referring to an object within the collection set is not recorded in a remembered set but is recorded instead in a scratch-pad list of entries that identify references to collection-set objects that need to be evacuated.
REFERENCES:
patent: 4724521 (1988-02-01), Carron et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5333318 (1994-07-01), Wolf
patent: 5392432 (1995-02-01), Engelstad et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5560003 (1996-09-01), Nilson et al.
patent: 5687370 (1997-11-01), Garst et al.
patent: 5801943 (1998-09-01), Nasburg
patent: 5845278 (1998-12-01), Kirsch et al.
patent: 5845298 (1998-12-01), O'Connor et al.
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5873104 (1999-02-01), Tremblay et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 5903900 (1999-05-01), Knippel et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 5960087 (1999-09-01), Tribble et al.
patent: 6021415 (2000-02-01), Cannon et al.
patent: 6047125 (2000-04-01), Agesen et al.
patent: 6049810 (2000-04-01), Schwartz et al.
patent: 6065020 (2000-05-01), Dussud
patent: 6098089 (2000-08-01), O'Connor et al.
patent: 6148309 (2000-11-01), Azagury et al.
patent: 6148310 (2000-11-01), Azagury et al.
patent: 6173294 (2001-01-01), Azagury et al.
patent: 6185581 (2001-02-01), Garthwaite
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6289358 (2001-09-01), Mattis et al.
patent: 6308185 (2001-10-01), Grarup et al.
patent: 6314436 (2001-11-01), Houldsworth
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6353838 (2002-03-01), Sauntry et al.
patent: 6381738 (2002-04-01), Choi et al.
patent: 6393439 (2002-05-01), Houldsworth et al.
patent: 6415302 (2002-07-01), Garthwaite et al.
patent: 6424977 (2002-07-01), Garthwaite
patent: 6434576 (2002-08-01), Garthwaite
patent: 6434577 (2002-08-01), Garthwaite
patent: 6442661 (2002-08-01), Dreszer
patent: 6449626 (2002-09-01), Garthwaite et al.
patent: 6496871 (2002-12-01), Jagannathan et al.
patent: 6529919 (2003-03-01), Agesen et al.
patent: 6567905 (2003-05-01), Otis
patent: 6757890 (2004-06-01), Wallman
patent: 6769004 (2004-07-01), Barrett
patent: 6799191 (2004-09-01), Agesen et al.
patent: 6820101 (2004-11-01), Wallman
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 6892212 (2005-05-01), Shuf et al.
patent: 6928460 (2005-08-01), Nagarajan et al.
patent: 6931423 (2005-08-01), Sexton et al.
patent: 6996590 (2006-02-01), Borman et al.
patent: 2002/0032719 (2002-03-01), Thomas et al.
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2002/0133533 (2002-09-01), Czajkowski et al.
patent: 2002/0138506 (2002-09-01), Shuf et al.
patent: 2003/0200392 (2003-10-01), Wright et al.
patent: 2004/0039759 (2004-02-01), Detlefs et al.
patent: 2004/0215914 (2004-10-01), Dussud
patent: 0 904 055 (1999-09-01), None
patent: 0 969 377 (2000-01-01), None
patent: WO0188713 (2001-11-01), None
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/.
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, Apr. 4, 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 Mangement '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.
Andew 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, M
Gaffin Jeffrey
Nguyen Cindy
Osha & Liang LLP
Sun Microsystems Inc.
LandOfFree
Avoiding remembered-set maintenance overhead for memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Avoiding remembered-set maintenance overhead for memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding remembered-set maintenance overhead for memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3770247