( 2 of 2 ) |
United States Patent | 7,143,124 |
Garthwaite | November 28, 2006 |
A garbage collector employs the train algorithm to collect a heap generation incrementally, collecting "car sections" in a collection order. As it updates the "remembered sets" by which it keeps track of where references to objects in respective car sections are located, it also updates oldest- and youngest-car indicators for each car section. The oldest- and youngest-car indicators for a given car section specify limits in the collection sequence beyond which references to objects in the given car have not been found. The garbage collector uses these indicators to identify cars that contain no objects that are reachable except through a reference chain that includes the collection set for the current collection increment. It adds one or more such cars to the collection set, and it collects the thus-expanded collection set without processing the remembered sets associated with the added cars.
Inventors: | Garthwaite; Alexander T. (Beverly, MA) |
Assignee: |
Sun Microsystems, Inc.
(Santa Clara,
CA)
|
Appl. No.: | 10/313,878 |
Filed: | December 6, 2002 |
Current U.S. Class: | 1/1 ; 707/999.202; 707/999.206; 711/E12.012 |
Current International Class: | G06F 12/00 (20060101); G06F 17/30 (20060101) |
Field of Search: | 707/10,205,206,100-104.1 717/140,148,153,159 711/6,133,136,153,159,160 |
4724521 | February 1988 | Carron et al. |
4797810 | January 1989 | McEntee et al. |
4912629 | March 1990 | Shuler, Jr. |
4989134 | January 1991 | Shaw |
5088036 | February 1992 | Ellis et al. |
5333318 | July 1994 | Wolf |
5392432 | February 1995 | Engelstad et al. |
5485613 | January 1996 | Engelstad et al. |
5560003 | September 1996 | Nilsen et al. |
5687370 | November 1997 | Garst et al. |
5801943 | September 1998 | Nasburg |
5845276 | December 1998 | Emerson et al. |
5845298 | December 1998 | O'Connor et al. |
5857210 | January 1999 | Tremblay et al. |
5873104 | February 1999 | Tremblay et al. |
5873105 | February 1999 | Tremblay et al. |
5900001 | May 1999 | Wolczko et al. |
5903900 | May 1999 | Knippel et al. |
5930807 | July 1999 | Ebrahim et al. |
5953736 | September 1999 | O'Connor et al. |
5960087 | September 1999 | Tribble et al. |
5999974 | December 1999 | Ratcliff et al. |
6021415 | February 2000 | Cannon et al. |
6047125 | April 2000 | Agesen et al. |
6049390 | April 2000 | Notredame et al. |
6049810 | April 2000 | Schwartz et al. |
6065020 | May 2000 | Dussud |
6098089 | August 2000 | O'Connor et al. |
6148309 | November 2000 | Azagury et al. |
6148310 | November 2000 | Azagury et al. |
6173294 | January 2001 | Azagury et al. |
6185581 | February 2001 | Garthwaite |
6226653 | May 2001 | Alpern et al. |
6243720 | June 2001 | Munter et al. |
6260120 | July 2001 | Blumenau et al. |
6289358 | September 2001 | Mattis et al. |
6308185 | October 2001 | Grarup et al. |
6314436 | November 2001 | Houldsworth |
6321240 | November 2001 | Chilimbi et al. |
6353838 | March 2002 | Sauntry et al. |
6381738 | April 2002 | Choi et al. |
6393439 | May 2002 | Houldsworth et al. |
6415302 | July 2002 | Garthwaite et al. |
6424977 | July 2002 | Garthwaite |
6434576 | August 2002 | Garthwaite |
6434577 | August 2002 | Garthwaite |
6442661 | August 2002 | Dreszer |
6449626 | September 2002 | Garthwaite et al. |
6496871 | December 2002 | Koyama et al. |
6529919 | March 2003 | Agesen et al. |
6567905 | May 2003 | Otis |
6640278 | October 2003 | Nolan et al. |
6757890 | June 2004 | Wallman |
6769004 | July 2004 | Barrett |
6820101 | November 2004 | Wallman |
6826583 | November 2004 | Flood et al. |
6868488 | March 2005 | Garthwaite |
6892212 | May 2005 | Shuf et al. |
6928450 | August 2005 | Mogi et al. |
6931423 | August 2005 | Sexton et al. |
2002/0032719 | March 2002 | Thomas et al. |
2002/0095453 | July 2002 | Steensgaard |
2002/0133533 | September 2002 | Czajkowski et al. |
2002/0138506 | September 2002 | Shuf et al. |
2003/0088658 | May 2003 | Davies et al. |
2003/0200392 | October 2003 | Wright et al. |
2003/0217027 | November 2003 | Farber et al. |
2004/0010586 | January 2004 | Burton et al. |
2004/0039759 | February 2004 | Detlefs et al. |
2004/0215914 | October 2004 | Dussud |
0 904 055 | Sep., 1999 | EP | |||
0 969 377 | Jan., 2000 | EP | |||
WO0188713 | Nov., 2001 | WO | |||
Appleby, Karen: Garbage Collection for Prolog Based on WAM, Communication of the ACM, Jun. 1, 1998, vol. 31, Issue 6, pp. 719-741. cited by examiner . Robert Courts: Improving Locality of Reference in Garbage Collecting Memory Management System, Communication of the ACM, Sep. 1988, vol. 31, No. 9, pp. 1128-1138. cited by examiner . Jones and Lins, "Garbage Collection: Algorithms for Automatic Dynamic Memory Management," 1996, pp. 165-179, Wiley, New York. cited by other . Paul Wilson, "Uniprocessor Garbage Collection Techniques," Technical Report, University of Texas, 1994. cited by other . Hudson and Moss, "Incremental Collection of Mature Objects," Proceedings of International Workshop on Memory Management, 1992, Springer-Verlag. cited by other . Grarup and Seligmann, "Incremental Mature Garbage Collection," M.Sc. Thesis, Available at http://www.daimi.au.dk/.about.jacobse/Papers/. cited by other . 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/.about.jacobse/Papers/. cited by other . Clark and Mason, "Compacting Garbage Collection can be Fast and Simple," Software-Practice and Experience, Feb. 1996, pp. 177-194, vol. 26, No. 2. cited by other . Henry Baker, "List Processing in Real Time on a Serial Computer," Communications of the ACM 21, Apr. 4, 1978, pp. 280-294. cited by other . Appel, Ellis, and Li, "Real-time Concurrent Collection on Stock Multiprocessors," ACM SIGPLAN Notices, 1988. cited by other . 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. cited by other . Herlihy and Moss, "Lock-Free Garbage Collection for Multiprocessors," ACM SPAA, 1991, pp. 229-236. cited by other . Bacon, Attanasio, Lee, Rajan, and Smith, "Java without the Coffee Breaks: A Noninstrusive Multiprocessor Garbage Collector," SIGPLAN Conference on Programming Language Design and Implentation, Snowbird, Utah, Jun. 2001. cited by other . 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. cited by other . 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. cited by other . 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. cited by other . Wilson, Lam, and Moher, "Effective Static-Graph Reorganization to Improve Locality in Garbage Collected System," Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 1991, Toronto, Ontario, Canada. cited by other . 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. cited by other . Chilimbi and Larus, "Using Generational Garbage Collection to Implement Cache-Conscious Data Placement," International Symposium on Memory Management, Oct. 1998. cited by other . 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. cited by other . David Ungar, "Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm," ACM SIGPLAN Notices, Apr. 1984, pp. 157-167, vol. 19, No. 5. cited by other . Andrew W. Appel, "Simple Generational Garbage Collection and Fast Allocation," Software Practice and Experience, 1989, pp. 171-183, vol. 19, No. 2. cited by other . 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. cited by other . 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. cited by other . 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. cited by other . 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. cited by other . Patrick G. Sobalvarro, "A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers," Massachusetts Institute of Technology, AITR-1417, 1988. cited by other . U.S. Appl. No. 10/287,851, filed Nov. 5, 2002, Garthwaite et al. cited by other . Arora, et al., "Thread Scheduling for Multiprogrammed Multiprocessors", Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architecture, Jun. 1998. cited by other . Barrett, et al., "Using Lifetime Predictors to Improve Memory Allocation Performance", SIGPLAN'93 Conference on Programming Languages Design and Implementation vol. 28(6) of Notices, Jun. 1993, 187-196, ACM Press, Albuquerque, NM. cited by other . Blackburn & McKinley, "In or Out? Putting Write Barriers in Their Place", Jun. 20, 2002, Berlin. cited by other . Clark, "An Efficient List-Moving Algorithm Using Constant Workspace, vol. 19 No. 6", Communications of the ACM, Jun. 1976, 352-354. cited by other . Flood, et al., "Parallel Garbage Collection for Shared Memory Multiprocessors", USENIX JVM Conference, Apr. 2001. cited by other . Goldstein, et al., "Lazy Threads: Implementing a Fast Parallel Call, vol. 37, No. 1", Journal of Parallel and Distributed Computing, Aug. 1996, 5-20. cited by other . Hanson, "Fast Allocation and Deallocation of Memory Based on Object Lifetimes", Software Practice and Experience, Jan. 1990, 20(1):5-12. cited by other . Harris, "Dynamic Adaptive Pre-Tenuring", In Proceedings of the Int'l Symposium on Memory Management, Oct. 2000, 127-136. cited by other . Holzle, Urs, "A Fast Write Barrier for Generational Garbage Collectors", Workshop on Garbage Collection in Object Oriented Systems, Oct. 1993. cited by other . 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. cited by other . Hudson, et al., "A Language--Independent Garbage Collector Toolkit", Coins Technical Report, Sep. 1991. cited by other . Hudson, et al., "Training Distributed Garbage: The DMOS Collector", University of St. Andrews Tech Report, 1997, 1-26. cited by other . Hudson, et al., "Garbage Collecting the World: One Car at a Time", ACM SIGPLAN Notices 32, 1997, 162-175. cited by other . Hudson, et al., "Sapphire: Copying GC Without Stopping the World", Practice and Experience Special Issue, Date Unknown, JAVA/Grande/Iscope. cited by other . Liskov, et al., "Partitioned Garbage Collection of a Large Stable Heap", Proceedings of IWOOS, 1996, 117-121. cited by other . Moss, et al., "A Complete and Coarse-Grained Incremental Garbage Collection for Persisten Object Strores", Proceedings 7th Int'l Workshop on Persisten Object System, 1996, 1-13, Cape May, NJ. cited by other . Munro, et al., "Incremental Garbage Collection of a Persistent Object Store using PMOS", 3rd Int'l Workshop on Persistence and Java, 1998, 78-91, Tiburon, California. cited by other . Nettles, Scott, "Real-Time Replication Garbage Collection", Avionics Lab, Wright Research and Development Center, 1993, PDDI. cited by other . Papopoulos, "Hood: A User-Level Thread Library for Multiprogramming Multiprocessors, Thesis: The Uni. of TX", University of Texas, Aug. 1998, 1-71, Austin. cited by other . Roy, et al., "Garbage Collection in Object-Oriented Databases Using Transactional Cyclic Reference Counting", VLDB Journal--The International Journal on Very Large Da Bases, vol. 7, Issue 3, 1998, 179-193. cited by other . Shuf, et al., "Exploiting Profilic Types for Memory Management and Optimizations. ACM ISBN Sep. 2, 2001", POPL, Jan. 2002, Portland. cited by other . 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. cited by other . Ungar, et al., "Tenuring Policies for Generation-Based Storage Reclamation", ACM SIGPLAN Notices, 1988, 23(11)1-17. cited by other . Venners, "Garbage Collection, Inside the Java 2 Virtual Machine; Chapter 9", www.artima.com, Date Unknown, parts 1-18. cited by other . Wilson, "Uniprocessor Garbage Collection Techniques", Proceedings of Int'l Workshop on Memory Management, 1992, V. 637. cited by other . Withington, P.T., "How Real is "Real-Time" GC?", Symbolics, Inc., Oct. 6, 1991, Burlington, MA. cited by other . Zee, et al., "Write Barrier Removal by Static Analysis", OPPSLA '02, Nov. 2002. cited by other . Zorn, "Segregating Heap Objects by Reference Behavior and Lifetime", In 8th Int'l Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 1998, 12-32, San Jose, CA. cited by other . Zorn, Benjamin, "Barrier Methods for Garbage Collection", Dept. of Computer Science, Uni. of Colorado, Nov. 1990, 1-37, Boulder. cited by other . Azagury, et al., "Combining Card Marking With Remembered Sets: How to Save Scanning Time", ACM SIGPLAN Notices, Oct. 1998, V. 34(3), ACM Press, Vancouver, Canada. cited by other . Cheney, "A Nonrecursive List Compacting Algorithm, vol. 12, No. 11", Communications of the ACM, Nov. 1970, 677-678, Uni. Math. Lab., Cambridge, European Patent Office. cited by other . Cheng, et al., "Generational Stack Collection and Profile-Driven Pretenuring", SIGPLAN'98 Conference on Programming Languages Design and Implementation, Jun. 1998, 162-173M ACM Press, Montreal, Canada. cited by other . Lam, 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, Toronto, Canada. cited by other . Pirinen, Pekka, "Barrier Techniques for Incremental Tracing", Harlequin Limited, Date Unknown, 20-25, Cambridge, Great Britain. cited by other. |