Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2003-10-06
2008-08-12
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C707S793000
Reexamination Certificate
active
07412580
ABSTRACT:
A concurrent incremental garbage collector where tracking and summarization of modified references is concurrent with application operations. A card table is arranged with write barriers so that an application's modification of objects in memory cards are memorialized in the card table. The collector performs an atomic operation, e.g., a compare-and-swap (CAS), on the card table to detect modified or written to objects. Card table indicators of dirtied cards are reset or emptied and the corresponding dirtied cards are scanned for the modifications and the remembered sets updated. Another CAS is performed on the same card table and if any dirtied cards are indicated the collector preserves the card table with the dirtied indicators and operates on a distant card table. If the CAS succeeds no modifications were made and the collector operates on the next scheduled card table group.
REFERENCES:
patent: 5920876 (1999-07-01), Ungar et al.
patent: 6115782 (2000-09-01), Wolczko 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: 6308185 (2001-10-01), Grarup 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: 6453466 (2002-09-01), Eidt et al.
patent: 6457019 (2002-09-01), Sexton et al.
patent: 6490599 (2002-12-01), Kolodner et al.
patent: 6560619 (2003-05-01), Flood et al.
patent: 6826757 (2004-11-01), Steele et al.
patent: 6845437 (2005-01-01), Borman et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 2002/0065986 (2002-05-01), Jeffrey et al.
patent: 2004/0003014 (2004-01-01), Nagarajan et al.
patent: 2004/0162860 (2004-08-01), Detlefs
Appel, “Simple Generational Garbage Collection and Fast Allocation”, Software Practice and Experience, 19(2), 1989, 171-183.
Appel, et al., “Real-Time Concurrent Collection on Stock Multiprocessors”, ACM SIGPLAN Notices, 1988.
Bacon, et al., “Java without the Coffee Breaks: A nonintrusive Multiprocessor Garbage Collector”, SIGPLAN Conference on Programming Language Design and Implementation, Jun. 2001, Snowbird, UT.
Baker, “List Processing in Real Time on a Serial Computer”, Communications of the ACM 21, Apr. 1978, 280-294.
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 Funcional Programming, Aug. 1984, 108-113, Austin, TX.
Chilimbi, et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement”, International Symposium on Memory Management, Oct. 1998.
Clark, et al., “Compacting Garbage Collection can be Fast and Simple”, Software-Practice and Experience, vol. 26, No. 2, Feb. 1996, 177-194.
Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System”, Communications of the ACM, vol. 31, No. 9, Sep. 1988, 1128-1138.
Herlihy, et al., “Lock-Free Garbage Collection for Multiprocessors”, ACM SPAA, 1991, 229-236.
Holzle, Urs, “A Fast Write Barrier for Generational Garbage Collectors”, Workshop on Garbage Collection in Object Oriented Systems, Oct. 1993.
Hosking, et al., “Remembered Sets Can Also Play Cards”, OOPSLA/ECOOP Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1993.
Hosking, et al., “Protection Traps and Alternatives for Memory Management of an Object-Oriented Language”, Object Systems Laboratory, Dec. 1993, 1-14, Dept. of Comp. Sci., Amherst, MA.
Hudson, et al., “Adaptive Garbage Collection for Modula-3 and Small Talk”, OOPSLA.ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems, Oct. 27, 1990.
Hudson, et al., “Sapphire: Copying GC Without Stopping the World”, Java Grande/ISCOPE, 2001.
Jones and Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, 1996, 165-179, John Wiley and Sons, NY.
Lieberman, et al., “A Real-Time Garbage Collector Based on the Lifetimes of Objects”, Communications of the ACM, 1983, 26(6).
Moon, “Garbage Collection in a Large Lisp System”, Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Aug. 1984, 235-246, Austin, TX.
Nettles, Scott, “Real-Time Replication Garbage Collection”, Avionics Lab, Wright Research and Development Center, 1993, PDDI.
Sobalvarro, “A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers”, Department of Electrical Engineering and Computer Science at MIT, Sep. 1988, AITR-1417.
Stamos, “Static Grouping of Small Objects to Enhance Performance of a Paged Virtual Memory”, ACM Transactions on Computer Systems, vol. 2, No. 2, May 1984, 155-180.
Ungar, “Generation Scavenging: A Non-Disruptive High Performance Storage Reclaration Algorithm”, ACM SIGPLAN Notices, Apr. 1984, 19(5).
Withington, P.T., “How Real is “Real-Time” GC?”, Symbolics, Inc., Oct. 6, 1991, Burlington, MA.
Zorn, Benjamin, “Barrier Methods for Garbage Collection”, Dept. of Computer Science, Uni. of Colorado, Nov. 1990, 1-37, Boulder.
Hosking, et al., “A Comparative Performance Evaluation of Write Barrier Implementations”, OOPSLA; ACM Conference on Object-Oriented Systems, Languages and Applications, Oct. 1992, V. 27(10), ACM Press, Vancouver, Canada.
Lam, et al., “Object Type Directed Garbage Collection to Improve Locality”, Proceedings of the International Workshop on Memory Management, Sep. 1992, 404-425, St. Malo, France.
Pirinen, Pekka, “Barrier Techniques for Incremental Tracing”, Harlequin Limited, Date Unknown, 20-25, Cambridge, Great Britain.
Wilson, et al., “Effective Static-Graph Reorganization to Improve Locality in Garbage Collected Systems”, Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 1991, Canada.
Detlefs, et al., “Concurrent Remembered Set Refinement in Generational Garbage Collection”, Proceedings of the USENIX Java VM '02 Conference, Aug. 1-2, 2002, 14 pages, San Francisco, CA, USA.
Steffen Grarup and Jacob Seligmann, “Incremental Mature Garbage Collection”, M.Sc. Thesis, Aarhus University, Computer Science Department, Aug. 1993.
Richard L. Hudson and J. Eliot B. Moss, “Incremental Collection of Mature Objects”, Proceedings of the International Workshop on Memory Management 1992, Springer-Verlag.
Jacob Seligmann & Steffen Grarup, “Incremental Mature Garbage Collection Using The Train Algorithm”, European Conference on Object-Oriented Programming 1995 Proceedings.
Paul Wilson, “Uniprocessor Garbage Collection Techniques”, International Workshop on Memory Management, Spring-Verlag, 1992.
Osha & Liang LLP
Rutz Jared I
Sparks Donald
Sun Microsystems Inc.
LandOfFree
Concurrent incremental garbage collector with a card table... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrent incremental garbage collector with a card table..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrent incremental garbage collector with a card table... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4002076