Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-04-15
2009-11-10
Jalil, Neveen Abel (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C711S170000, C711S132000, C716S030000
Reexamination Certificate
active
07617264
ABSTRACT:
A garbage collector that operates in multiple threads divides a generation of a garbage-collected heap into heap sections, with which it associates respective remembered sets of locations where references to objects in those heap sections have been found. When such a heap section comes up for collection, each of a plurality of parallel garbage-collector threads that is processing its remembered set maintains a separate “popularity”—indicating count map, which includes an entry for each of a set of segments into which the collector has divided that heap section. The thread increments an entry in its count map each time it finds a reference to an object in the associated segment. If an object is located in a segment for which the associated count-map entry has exceeded a threshold, the thread evacuates the object in a manner different from that in which it evacuates objects not thus been found to be popular.
REFERENCES:
patent: 5848423 (1998-12-01), Ebrahim 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: 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: 6449626 (2002-09-01), Garthwaite et al.
patent: 6529919 (2003-03-01), Agesen et al.
patent: 6574720 (2003-06-01), Hopeman et al.
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 7058670 (2006-06-01), Garthwaite
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2003/0212719 (2003-11-01), Yasuda et al.
patent: 2005/0015417 (2005-01-01), Lewis
patent: 0188713 (2001-11-01), None
Jones and Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, 1996, pp. 167-181, John Wiley and Sons, NY.
Ellis, J. R., Li, K., and Appel, A. W., Real-Time Concurrent Collection on Stock Multiprocessors, Systems Research Center, Feb. 14, 1988, pp. 1-20.
Appel, A. W., Simple Generational Garbage Collection and Fast Allocation, Department of Computer Science, Princeton University, 1988, pp. 1-14.
Arora, N. S., Blumofe, R., D., and Plaxton, C., G., Thread Scheduling for Multiprogrammed Multiprocessors, Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, Jun. 1998, pp. 1-23.
Bacon, D., F., et al., Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector, Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, Jun. 2001, pp. 1-11.
Baker, H., G., Jr., List Processing in Real Time on a Serial Computer, Communications of the ACM 21, 4, Apr. 1978, pp. 280-294.
Brooks, R., A., 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, 1984, pp. 256-262.
Cheney, C. J., A Nonrecursive List Compacting Algorithm, Communications of ACM, Nov. 1970, Csambridge, England, pp. 677-678.
Chilimbi, T., M., and Larus, J., R., Using Generational Garbage Collection to Implement Cache-Conscious Data Placement, International Symposium on Management, Oct. 1998, pp. 1-11.
Clark, D., W., An Efficient List-Moving Algorithm Using Constant Workspace, Communications of the ACM, Jun. 1976, vol. 19, No. 6, pp. 352-354.
Clarke, C., L, A., and Mason, D., V., Compacting Garbage Collection can be Fast and Simple, Practice and Experience, vol. 26, No. 2, Feb. 1996, pp. 177-194.
Courts, R., Improving Locality of Reference in a Garbage-Collecting Memory Management System, Communications of the ACM, vol. 31, No. 9, Sep. 1988, pp. 1128-1138.
Goldstein, S., C., Schauser, K., E,. and Culler, D., E., Lazy Threads: Implenting a Fast Parallel Call, Journal of Parallel and Distributed Computing, 1996, pp. 5-20.
Grarup, S. and Seligmann, J., Incremental Mature Garbage Collection, Aug. 1993, pp. 1-189.
Harris, T., L., Dynamic adaptive pre-tenuring, ISMM '00, Minneapolis, MN, 2000, pp. 127-136.
Herlihy, M., P., and Moss, J., E., B., Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, vol. 3, No. 3, May 1992, pp. 304-311, presented at ACM SPAA 1991.
Hosking, A., L. And Hudson, R., L., Remembered sets can also play cards, ACM OOPSLA '93 Workshop on Memory Management and Garbage Collection, 1993, pp. 1-7.
Hosking, A., L., Moss, J., E., B., and Stefanovic, D., A Comparative Performance Evaluation of Write Barrier Implementations, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Vancouver, Canada, Oct. 1992, pp. 1-14.
Hosking, A., L. and Moss, J., E., B., Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the 14th ACM Symposium on Operating Systems Principles, Dec. 1993, pp. 1-13.
Hudson, R., L. and Moss, J., E., B., Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, 1992, pp. 1-15.
Hudson, R., L. and Moss, J., E., B., Sapphire: Copying GC Without Stopping the World, Java Grande/ISCOPE, Palo Alto, CA, USA, 2001, pp. 1-10.
Lieberman, H., and Hewitt, C., A Real-Time Garbage Collector Based on the Lifetimes of Objects, Communications of the ACM, 1983, pp. 1-18.
Moon, D., A., Garbage Collection in a Large Lisp System, Communications of the ACM, Austin, Texas, 1984, pp. 235-246.
Nettles, S. and O'Toole, J., Real-Time Replication Garbage Collection, SIGPLAN Conference on Programming Language Design and Implementation, 1993, pp. 217-226.
Sobalvarro, P., G., A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers, Department of Electrical Engineering and Computer Science at MIT, Sep. 1988, pp. 1-68.
Stamos, J., W., Static Grouping of Small Objects to Enhance Performance of a Paged Virtual Memory, ACM Transactions on Computer Systems, vol., 2, No. 2, May 1984, pp. 155-180.
Ungar, D., Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm, ACM Sigplan Notices, 1984, pp. 157-167.
Wilson, P., R., Lam, M., S., and Moher, T., G., Effective “Static-graph” Reorganization to Improve Locality in Garbage-Colleceted Systems, Proceedings of the ACM SIGPLAN '91 Conference on Programming Language design and Implementation, Canada, Jun. 26-28, 1991, pp. 177-191.
Wilson, R, R., Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, 1992, pp. 1-32.
Hudson, R. And Diwan, A., Adaptive Garbage Collection for Modula-3 and Smalltalk, OOPSLA/ECOOPp '90, Workshop on Garbage Collection in Object-Oriented Systems, Oct. 27, 1990, pp. 1-5.
Lam, M., S., Wilson, P., R., and Moher, T., G., Object Type Garbage Collection to Improve Locality, Proceedings of the International Workshop on Memory Management, St. Malo, France, 1992, pp. 404-425.
Abel Jalil Neveen
Hoffler Raheem
Osha • Liang LLP
Sun Microsystems Inc.
LandOfFree
Parallel remembered-set processing respecting popular-object... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel remembered-set processing respecting popular-object..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel remembered-set processing respecting popular-object... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4137521