Generation isolation system and method for garbage collection

Details Generation isolation system and method for garbage collection Generation isolation system and method for garbage collection

1997-04-23

2000-08-01

Oberley, Alvin E.

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

707206, G06F 1200, G06F 1730

Patent

active

060980893

ABSTRACT:
Architectural support for generation isolation is provided through trapping of intergenerational pointer stores. Identification of pointer stores as intergenerational is performed by a store barrier responsive to an intergenerational pointer store trap matrix that is programmably encoded with store target object and store pointer data generation pairs to be trapped. The write barrier and intergenerational pointer store trap matrix provide a programmably-flexible definition of generation pairs to be trapped, affording a garbage collector implementer with support for a wide variety of generational garbage collection methods, including remembered set-based methods, card-marking type methods, write barrier based copying collector methods, etc., as well as combinations thereof and combinations including train algorithm type methods to managing mature portions of a generationally collected memory space. Pointer specific store instruction replacement allows implementations in accordance with this invention to provide an exact barrier to not only pointer stores, but to the specific intergenerational pointer stores of interest to a particular garbage collection method or combination of methods.

REFERENCES:
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4807120 (1989-02-01), Courts
patent: 4907151 (1990-03-01), Bartlett
patent: 4922414 (1990-05-01), Holloway et al.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5136706 (1992-08-01), Courts
patent: 5218698 (1993-06-01), Mandl
patent: 5293614 (1994-03-01), Ferguson et al.
patent: 5321834 (1994-06-01), Weiser et al.
patent: 5367685 (1994-11-01), Gosling
patent: 5463778 (1995-10-01), Johnson
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5590332 (1996-12-01), Baker
patent: 5687368 (1997-11-01), Nilsen
Richard Jones and Rafael Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Feb. 1997, John Wiley & Sons, entire work (previously supplied copy on reserve in the EIC library) and more particularly pp. 1-41 and 116-226 (copies enclosed).
A.L. Hosking et al.: "A Comparative Performance Evaluation of Write Barrier Implementations" ACM Sigplan Notices, vol. 27, No. 10, Oct. 1, 1992, pp. 92-109, XP000327291.
Kin-Man Chung and Herbert Yuen, "A `Tiny` Pascal Compiler, Part 1: The P-Code Interpreter," BYTE Publications, Inc., Sep. 1978, (14 pages).
Kin-Man Chung and Herbert Yuen, "A `Tiny` Pascal Compiler, Part 2: The P-Compiler," BYTE Publications, Inc., Oct. 1987, (10 pages).
Ken Thompson, "Regular Expression Search Algorithm," Programming Techniques, R. M. McClure, editor, vol. 22, No. 6, Communications of the ACM, Jun. 1968, pp. 419-422.
Kenneth A. Pier, "A Restrospective on the Dorado, A High-Performance Computer," Association for Computing Machinery, 1983, pp. 252-269.
Gene McDaniel, "An Analysis of a Mesa Instruction Set," Technical Report CSL-82-2, Xerox Corporation, Palo Alto, California, May 1982, pp. 1-17.
James G. Mitchell et al, "Mesa Language Manual," Technical Report CSL-79-3, Xerox Corporation, Palo Alto, California, 1979, 80 pages.
Urs Holzle, A Fast Write Barrier for Generational Garbage Collectors, OOPSLA '93 Garbage Collection Workshop, Oct. 1993, pp. 1-6.
David A. Moon, Architecture of the Symbolics 3600, IEEE, 1985, pp. 76-83.
Henry G. Baker, Jr., List Processing in Real Time on a Serial Computer, Comm. ACM, Apr. 1978, vol. 21, No. 4, pp. 280-294.
David Ungar, Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm, ACM Sigplan Notices, May 1984, vol. 19, No. 5, pp. 157-167.
Guy L. Steele, Jr., Multiprocessing Compactifying Garbage Collection, Comm. ACM, Sep. 1975, vol. 18, No. 9, pp. 495-508.
Paul R. Wilson and Thomas G. Moher, Design of the Opportunistic Garbage Collector, OOPSLA '89 Proceedings, Oct. 1989, pp. 23-35, Sep. 1992, pp. 396-418.
Mario Wolczko and Ifor Williams, Multi-level Garbage Collection in a High-Performance Persistent Object System, Proceedings of the Fifth International Workshop on Persistent Object Systems, Sep. 1992, pp. 396-418.
Richard L. Hudson and J. Eliot B. Moss, Incremental Collection of Mature Objects, International Workshop IWMM 92, Sep. 1992, pp. 388-403.
David A. Barrett, Thesis entitled: Improving the Performance of Conservative Generational Garbage Collection, Technical Report CU-CS-784-95, Sep. 1995, pp. 1-64.
Robert Courts, Improving Locality of Reference in a Garbage-Collecting Memory Management System, Communications of the ACM, Sep. 1988, vol. 31, No. 9, pp. 1128-1138.
David A. Moon, Garbage Collection in a Large Lisp System, 1984, pp. 235-246 .

Affiliated with

Also associated with

Rating

Generation isolation system and method for 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 Generation isolation system and method for garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation isolation system and method for garbage collection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-673662