Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-08-15
2006-08-15
Alam, Shahid (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S173000, C711S209000
Reexamination Certificate
active
07092978
ABSTRACT:
A copying-type garbage collector operates in multiple concurrent threads. Each thread evacuates potentially reachable objects from the from space to the to space in a depth-first manner: if a thread has evacuated an object containing references to any from-space objects, it evacuates all of that object's descendants before it evacuates any other reachable objects. To keep track of descendants that must be evacuated before non-descendants can be, the thread places objects containing references to non-evacuated objects into a linked list maintained by pointers that it installs in the from-space locations from which the objects on the list were evacuated. Additionally, it divides the to space into local-allocation buffers (“LABs”) to which respective threads exclusively evacuate objects, and each thread maintains a LAB stack representing all the LABs it has filled that still contain references to unevacuated from-space objects. When a thread has completed evacuating the descendants of evacuees in all of its LABs, it “steals” work from other threads. It may do so, for instance, by processing a reference in an object belonging to another thread's list, by transferring to its own list one or more objects from another thread's list, or by transferring to its own LAB stack one or more LABs from another thread's LAB stack.
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
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: 6823351 (2004-11-01), Flood et al.
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: WO 01/88713 (2001-11-01), None
Harris, Timothy L., Dynamic adaptive pre-tenuring, Oct. 2000, ACM SIGPLAN, 1-10.
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 a 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 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, 1998.
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.
Arora, Blumofe, and Plaxton, “Thread Scheduling for Multiprogrammed Multiprocessors,” Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, Jun. 1998.
Douglas W. Clark, “An Efficient List-Moving Algorithm Using Constant Workspace,” Communications of the ACM, Jun. 1976, pp. 352-354, vol. 19, No. 6.
C. J. Cheney, “A Nonrecursive List Compacting Algorithm,” Communications of the ACM, Nov. 1970, pp. 677-678, vol. 13, No. 11.
Goldstein, Schauser, and Culler, “Lazy Threads: Implementing a Fast parallel Call,” Journal of Parallel and Distributed Computing, Aug. 1996, pp. 5-20, vol. 37, No. 1.
Hudson, et al., “Sapphire: Copying GC Without Stopping the World”, Java Grande/ISCOPE, 2001.
Nettles, Scott, “Real-Time Replication Garbage Collection”, Avionics Lab, Wright Research and Development Center, 1993, PDDI.
Lam, et
Alam Shahid
Fleurantin Jean Bolte
Kudirka & Jobse LLP
Sun Microsystems Inc.
LandOfFree
Space-efficient, depth-first parallel copying collection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Space-efficient, depth-first parallel copying collection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-efficient, depth-first parallel copying collection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3682360