Remembered-set scrubbing to remove stale entries in an...

Details Remembered-set scrubbing to remove stale entries in an... Remembered-set scrubbing to remove stale entries in an...

2006-07-04

2006-07-04

Robinson, Greta (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07072918

ABSTRACT:
A computer system, method and software for detecting and purging stale entries from remembered sets associated with incrementally collectible regions used in an incremental garbage collection technique like the Trains algorithm is described. Stale entries are detected by a number of techniques, and then purged, eliminated, or scrubbed. These techniques make use of the summarized information about regions such as cards or incrementally collectible regions that indicate age of allocation, time a region was last scanned, last time an entry was inserted into a remembered set, as well as how far forward or backward objects in a given region refer in a generation.

REFERENCES:
patent: 4695949 (1987-09-01), Thatte et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5987628 (1999-11-01), Von Bokern 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: 6339779 (2002-01-01), Houldsworth
patent: 6363403 (2002-03-01), Roy et al.
patent: 6415302 (2002-07-01), Garthwaite et al.
patent: 6421690 (2002-07-01), Kirk, III
patent: 6424977 (2002-07-01), Garthwaite
patent: 6434576 (2002-08-01), Garthwaite
patent: 6434577 (2002-08-01), Garthwaite
patent: 6449626 (2002-09-01), Garthwaite et al.
patent: 6529919 (2003-03-01), Agesen et al.
patent: 6567905 (2003-05-01), Otis
patent: 6574720 (2003-06-01), Hopeman et al.
patent: 6581077 (2003-06-01), Sokolov et al.
patent: 6594702 (2003-07-01), Fischer et al.
patent: 6654773 (2003-11-01), Hills
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: WO01 88713 (2001-11-01), None
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.
Arora, et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architecture, Jun. 1998.
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, “An Efficient List-Moving Algorithm Using Constant Workspace, vol. 19 No. 6”, Communications of the ACM, Jun. 1976, 352-354.
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.
Goldstein, et al., “Lazy Threads: Implementing a Fast Parallel Call, vol. 37, No. 1”, Journal of Parallel and Distributed Computing, Aug. 1996, 5-20.
Grarup, et al., “Incremental Mature Garbage Collection”, M.Sc.Thesis @ http://www.daimi.aau.dk/jacobse/Papers, Aug. 1993.
Harris, “Dynamic Adaptive Pre-Tenuring”, In Proceedings of the Int'l Symposium on Memory Management, Oct. 2000, 127-136.
Herlihy, et al., “Lock-Free Garbage Collection for Multiprocessors”, ACM SPAA, 1991, 229-236.
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., “Incremental Collection of Mature Objects”, Proceedings of the Int'l Workshop on Memory Management, 1992, pp. 1-16, Springer-Verlag.
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.
Wilson, “Uniprocessor Garbage Collection Techniques”, Technical Report, University of Texas, 1994.
Cheney, “A Nonrecursive List Compacting Algorithm, vol. 13, No. 11”, Communications of the ACM, Nov. 1970, 677-678, Uni. Math. Lab., Cambridge, European Patent Office.
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.
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.
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.
Seligmann, et al., “Incremental Mature Garbage Collection, In the European Conference on Object-Oriented Programming”, M.Sc.Thesis @ http://www.daimi.aau.dk/jacobse/Papers/, 1995.
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).

Affiliated with

Also associated with

Rating

Remembered-set scrubbing to remove stale entries in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Remembered-set scrubbing to remove stale entries in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remembered-set scrubbing to remove stale entries in an... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3554760