Write barrier system and method including pointer-specific instr

Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Virtual machine memory addressing

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

711165, 395507, 395570, G06F 1200

Patent

active

059537361

ABSTRACT:
A pointer-specific instruction variant replacement mechanism facilitates an exact write barrier, i.e., a write barrier specific to pointer stores and transparent to non-pointer stores. Pointer store specific instruction replacement allows some implementations to provide an exact barrier specific to the particular set of intergenerational pointer stores that are of interest to a particular garbage collection method or combination of methods. The exact identification of pointer stores herein does not require tags encoded in-line with collected memory storage and does not require non-standard word sizes to support such tags. In one embodiment, a non-quick to quick translator cache provides pointer specific store instruction replacement. In another, self modifying code provides pointer specific store instruction replacement. An exemplary write barrier provided in accordance with the pointer-specific instruction variant replacement mechanism of this invention affords a garbage collector implementer with support for a wide variety of garbage collection methods, including remembered set-based methods, card-marking type methods, write barrier based copying collector methods, mark-sweep methods, etc., as well as combinations thereof and combinations including train algorithm type methods to managing mature portions of a generationally collected memory space. Such a write barrier can eliminate non-pointer stores from the set of stores that are evaluated against, for example, an intergenerational pointer store trap matrix or a garbage collection page mask to determine whether or not to trap. Such a write barrier can also eliminate entries associated with non-pointer stores from remembered set or card table stores for collection time scanning of modified portions of a collected generational space.

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), Barlett
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
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.
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. 1991, pp. 388-403.
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).
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.
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. 1978, (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, Calfornia, 1979, 80 pages.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Write barrier system and method including pointer-specific instr does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Write barrier system and method including pointer-specific instr, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Write barrier system and method including pointer-specific instr will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-1520795

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.