Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
2004-11-23
2009-12-29
An, Meng-Ai (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
C718S105000, C718S001000, C711S133000, C711S135000, C711S159000, C711S160000, C711S170000, C707S793000
Reexamination Certificate
active
07640544
ABSTRACT:
A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.
REFERENCES:
patent: 4482956 (1984-11-01), Tallman
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5241673 (1993-08-01), Schelvis
patent: 5274804 (1993-12-01), Jackson et al.
patent: 5355483 (1994-10-01), Serlet
patent: 5410722 (1995-04-01), Cornaby
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5577246 (1996-11-01), Priddy et al.
patent: 5692185 (1997-11-01), Nilsen et al.
patent: 5692193 (1997-11-01), Jagannathan et al.
patent: 5819255 (1998-10-01), Celis et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5893121 (1999-04-01), Ebrahim et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5950205 (1999-09-01), Aviani, Jr.
patent: 6047125 (2000-04-01), Agesen et al.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6052699 (2000-04-01), Huelsbergen et al.
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6192517 (2001-02-01), Agesen et al.
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6240422 (2001-05-01), Atkins et al.
patent: 6249793 (2001-06-01), Printezis et al.
patent: 6253215 (2001-06-01), Agesen et al.
patent: 6286016 (2001-09-01), Heller et al.
patent: 6289360 (2001-09-01), Kolodner et al.
patent: 6289369 (2001-09-01), Sundaresan
patent: 6304949 (2001-10-01), Houlsdworth
patent: 6314436 (2001-11-01), Houldsworth
patent: 6314478 (2001-11-01), Etcheverry
patent: 6317756 (2001-11-01), Kolodner et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6338073 (2002-01-01), Houldsworth et al.
patent: 6341293 (2002-01-01), Hennessey
patent: 6374339 (2002-04-01), Iivonen
patent: 6377984 (2002-04-01), Najork et al.
patent: 6381735 (2002-04-01), Hunt
patent: 6411964 (2002-06-01), Iyer et al.
patent: 6415302 (2002-07-01), Garthwaite et al.
patent: 6427154 (2002-07-01), Kolodner et al.
patent: 6434575 (2002-08-01), Berry et al.
patent: 6480862 (2002-11-01), Gall
patent: 6493730 (2002-12-01), Lewis et al.
patent: 6526422 (2003-02-01), Flood et al.
patent: 6542911 (2003-04-01), Chakraborty et al.
patent: 6560619 (2003-05-01), Flood et al.
patent: 6571260 (2003-05-01), Morris
patent: 6618737 (2003-09-01), Aridor et al.
patent: 6651101 (2003-11-01), Gai et al.
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6763452 (2004-07-01), Hohensee et al.
patent: 2001/0000821 (2001-05-01), Kolodner et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2001/0049726 (2001-12-01), Comeau et al.
patent: 2002/0038301 (2002-03-01), Aridor et al.
patent: 2002/0052926 (2002-05-01), Bush et al.
patent: 2002/0073103 (2002-06-01), Bottomley et al.
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2003/0005025 (2003-01-01), Shavit et al.
patent: 2003/0005029 (2003-01-01), Shavit et al.
patent: 2004/0088702 (2004-05-01), Garthwaite et al.
Eleftherios D. Polychronopoulos and Theodore S. Papatheodorou; Scheduling User-Level Threads on Distributed Shared-Memory Multiprocessors; P. Amestoy et al. (Eds.): Euro-PAR'99, LNCS 1685, pp. 358-368, 1999.
Robert D. Blumofe ; Cilk: An Efficient Multithreaded Runtime System; PPOPP '95 Santa Clara, CA USA; 1995 ACM; pp. 207-216.
Matteo Frigo, Charles E. Leiserson, Keith H. Randall ;the Implementation of the Cilk-5 Multithreaded Language; ACM 1998; pp. 212-223.
Appel, “Simple Generational Garbage Collection and Fast Allocation”, Software Practice and Experience, 19(2), 1989, 171-183.
Arora, et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, Dept. of Computer Science, Uni. of Texas, 1998, Austin.
Bibolet, et al., “Asynchronous Service Routine Invocation with Safely Serialized Work Queue”, IBM Tech. Disclosure Bulletin, vol. 25, No. 8, Jan. 1983, IBM Corp.
Blelloch, et al., “On Bounding Time and Space for Multiprocessor Garbage Collection”, Computer Science Department, Carnegie Mellon University, Date Unknown.
Blumofe, “Scheduling Multithreaded Computations by Work Stealing”, University of Texas, 1998, Austin.
Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System”, Communications of the ACM, vol. 31, No. 9, Sep. 1988, 1128-1138.
Craig, et al., “nanoPortean: Scalable System Software for a Gigabit Active Router”, IEEE INFOCOM 2001, 2001, 51-59.
Demers,E T al., “Combining Generational and Conservative Garbage Collection: Framework and Implementations”, In Conf. Rec. of 17th Annual ACM Symposium, Jan. 1990, 261-269, ACM Notices.
Hickey, et al., “Performance Analysis of On-the-Fly Garbage Collection”, Communication of the ACM, vol. 27, No. 11, Nov. 1984, 1143-1154.
Holzle, Urs, “A Fast Write Barrier for Generational Garbage Collectors”, Workshop on Garbage Collection in Object Oriented Systems, Oct. 1993.
Jones and Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, 1996, 165-179, John Wiley and Sons, NY.
Lamport, Leslie, “Proving the Correctness of Multiprocess Programs”, IEEE Transaction of Software Engineering, vol.. SE-3. No. 2, Mar. 1977, 125-143.
Massalin, et al., “A Lock-Free Multiprocessor OS Kernel, Dept. Of Computer Science”, Columbia University Technical Report No. CUCS-005-91, Jun. 19, 1991.
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.
Patel, et al., “A Model Completion Queue Mechanisms Using the Virtual Interface API”, IEEE, 2000, 280-288.
Rudalics, “Distributed Copying Garbage Collection”, ACM, 1986, 364-372.
Washabaugh, et al., “Incremental Garbage Collection of Concurrent Objects”, IEEE, 1990, 21-30.
Youn, et al., “A Multithreaded Architecture for the Efficient Execution of Vector Computations within a Loop using”, IEEE, 1996, 343-350.
Ichiyoshi, Et Al., “A Shared-Memory Parallel Extension of Klic and its Garbage Collection”, FGCS '94 Workshop on Parallel Logic Programming, Dec 15-16, 1994, 113-126, Tokyo, Japan.
Chuang, et al., “Real-Time Deques, Multihead Turing Machines and Purely Functional Programming.”, ACM, 1993, pp. 289-298.
Baker, Henry G. “List Processing in Real Time on a Serial Computer”, ACM, 1978, pp. 280-294.
Cohen, et al., “Performance Analysis of On-The-Fly Garbage Collection”, ACM, 1994, pp. 1143-1154.
Hudak, et al., “Garbage Collection and Task Deletion in Distributed Applicative Processing Systems”, ACM Symposium on Lisp and Functional Programming, 1982, pp. 168-178.
Boehm Hans, “Simple Garbage Collector Safety”, ACM 1996, pp. 92-94.
Chase, et al., “Analysis of Pointer and Structures”, ACM, 1990, pp. 298-306.
Aditya, et al., Garbage Collection for Strongly-Typed Languages using Run-time Type Reconstruction, ACM, 1994, pp. 16-20.
Cohen Jacques, Garbage Collection of Linked Data Structures, ACM, 1981, pp. 345-355.
Nobuyuki Ichiyoshi and Masao Morita, “A Shared-memory parallel extension of KLIX and its garbage collection.
Agesen Ole
Detlefs David L.
Flood Christine H.
Shavit Nir N.
Zhang Xiaolan
Al Kawsar Abdullah
An Meng-Ai
Osha • Liang LLP
Sun Microsystems Inc.
LandOfFree
Work stealing queues for parallel garbage 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 Work stealing queues for parallel garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Work stealing queues for parallel garbage collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4068963