Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-12-12
2006-12-12
Gaffin, Jeffrey (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
07149762
ABSTRACT:
In incremental garbage collectors based on the Train algorithm a futile condition may exist where the collector never finishes collecting an old train. The present invention provides an expanded collection set of a younger car with an object referenced from another train. That reference will be found by scanning the remembered sets of other car. If no such younger car is found, then a younger car with an external reference may be added to the collection set. One of these other cars is added to the collection set and, if there are no other changes, the collection will reduce the volume in the train being collected and therefore break the futile situation.
REFERENCES:
patent: 4724521 (1988-02-01), Carron et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5333318 (1994-07-01), Wolf
patent: 5392432 (1995-02-01), Engelstad et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5560003 (1996-09-01), Nilson et al.
patent: 5687370 (1997-11-01), Garst et al.
patent: 5801943 (1998-09-01), Nasburg
patent: 5845276 (1998-12-01), Kirsch et al.
patent: 5845298 (1998-12-01), O'Connor et al.
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5873104 (1999-02-01), Tremblay et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 5903900 (1999-05-01), Knippel et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 5960087 (1999-09-01), Tribble et al.
patent: 5999974 (1999-12-01), Ratcliff et al.
patent: 6021415 (2000-02-01), Cannon et al.
patent: 6047125 (2000-04-01), Agesen et al.
patent: 6049390 (2000-04-01), Notredame et al.
patent: 6049810 (2000-04-01), Schwartz et al.
patent: 6065020 (2000-05-01), Dussud
patent: 6098089 (2000-08-01), O'Connor 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: 6226653 (2001-05-01), Alpern et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6260120 (2001-07-01), Blumenau et al.
patent: 6289358 (2001-09-01), Mattis et al.
patent: 6308185 (2001-10-01), Grarup et al.
patent: 6314436 (2001-11-01), Houldsworth
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6353838 (2002-03-01), Sauntry et al.
patent: 6381738 (2002-04-01), Choi et al.
patent: 6393439 (2002-05-01), Houldsworth et al.
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: 6442661 (2002-08-01), Dreszer
patent: 6449626 (2002-09-01), Garthwaite et al.
patent: 6496871 (2002-12-01), Jagannathan et al.
patent: 6529919 (2003-03-01), Agesen et al.
patent: 6567905 (2003-05-01), Otis
patent: 6640278 (2003-10-01), Nolan et al.
patent: 6757890 (2004-06-01), Wallman
patent: 6769004 (2004-07-01), Barrett
patent: 6820101 (2004-11-01), Wallman
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 6892212 (2005-05-01), Shuf et al.
patent: 6928450 (2005-08-01), Nagarajan et al.
patent: 6931423 (2005-08-01), Sexton et al.
patent: 2002/0032719 (2002-03-01), Thomas et al.
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2002/0133533 (2002-09-01), Czajkowski et al.
patent: 2002/0138506 (2002-09-01), Shuf et al.
patent: 2003/0088658 (2003-05-01), Davies et al.
patent: 2003/0200392 (2003-10-01), Wright et al.
patent: 2003/0217027 (2003-11-01), Farber et al.
patent: 2004/0010586 (2004-01-01), Burton et al.
patent: 2004/0039759 (2004-02-01), Detlefs et al.
patent: 2004/0215914 (2004-10-01), Dussud
patent: 0 904 055 (1999-09-01), None
patent: 0 969 377 (2000-01-01), None
patent: WO0188713 (2001-11-01), None
Grarup et al., “Incremental Mature Garbage Collection” Aarhus University, Aug. 1993.
Printezis et al., “Visualizing the Train Gargage Collector”, Sun Microsystems Inc., ISMM '02, Jun. 20-21, 2002.
Hudson et al., “Training Distributed Garbage: The DMOS Collector”,echnical Report, University of St. Andrews, 1997.
Seligmann et al., “Incremental Mature Garbage Collection Using the Train Algorithm”, Aarhus University, 1995.
U.S. Appl. No. 10/287,851, filed Nov. 5, 2002, Garthwaite et al.
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.
Appleby, Karen, “Garbage Collection for Prolog Based on WAM, vol. 31, Issue 6”, Communication of the ACM, Jun. 1, 1998, 719-741.
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.
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.
Blackburn & McKinley, “In or Out? Putting Write Barriers in Their Place”, Jun. 20, 2002, Berlin.
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. 1966, 177-194.
Courts, “Improving Locality of Refernece in a Garbage-Collecting Memory Management System”, Communications of the ACM, vol. 31, No. 9, Sep. 1988, 1128-1138.
Flood, et al., “Parallel Garbage Collection for Shared Memory Multiprocessors”, USENIX JVM Conference, Apr. 2001.
Goldstein, et al., “Lazy Threads: Implementing a Fast Parallel Cal, 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.
Hanson, “Fast Allocation and Deallocation of Memory Based on Object Lifetimes”, Software Practice and Experience, Jan. 1990, 20(1):5-12.
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.
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 Garage 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., “A Language—Indepen
Gaffin Jeffrey
Hicks Michael J.
Osha•Liang LLP
Sun Microsystems Inc.
LandOfFree
Handling futile collections in the train algorithm through... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Handling futile collections in the train algorithm through..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Handling futile collections in the train algorithm through... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3718463