On-the-fly garbage collector

Details On-the-fly garbage collector On-the-fly garbage collector

1998-10-07

2001-11-13

Black, Thomas G. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06317756

ABSTRACT:

FIELD OF THE INVENTION
The present invention is in the general field of memory management and concerns more specifically garbage collection (GC) for computer languages and computer systems.
LIST OF REFERENCES
1. Mordechai Ben-Ari. On-the-fly garbage collection: New algorithms inspired by program proofs. In M. Nielsen and E. M. Schmidt, editors,
Automata, languages and programming
. Ninth colloquium (Aarhus, Denmark) pages 14-22, New York, Jul. 12-16, 1982. Springer-Verlag.
2. Mordechai Ben-Ari. Algorithms for on-the-fly garbage collection.
ACM Transactions on Programming Languages and Systems,
6(3):333-344, July 1984.
3. Alan Demers, Mark Weiser, Barry Hayes, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the
Seventeenth Annual ACM Symposium on Principles of Programming Languages
, ACM SIGPLAN Notices, January 1990. ACM Press,pages 261-269.
4. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. In
Lecture Notes in Computer Science
, No. 46, Springer-Verlag, New York, 1976.
5. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation.
Communications of the ACM,
21 (11): 965-975, November 1978.
6. D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-first Annual ACM Symposium on
Principles of Programming Languages
, ACM SIGPLAN Notices. ACM Press, 1994, pages 113-123.
7. D. Doligez and X. Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the
Twentieth Annual ACM Symposium on Principles of Programming Languages
, ACM SIGPLAN Notices. ACM Press, January 1993.
8. David Gries. An exercise in proving parallel programs correct.
Communications of the ACM,
20(12):921-930, December 1977.
9. P. Hudak, R. M. Keller. Garbage Collection and Task Deletion in Distributed Systems. In
ACM Symposium on Lisp and Functional Programming
, pp. 168-178, Pittsburgh, Pa., August 1982.
10. R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley \& Sons, July 1996.
11. H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In
IEEE Symposium on Foundations of Computer Science
, pages 120-131. IEEE Press, 1977.
12. L. Lamport. Garbage collection with multiple processes: an exercise in parallelism. In Proceedings of the 1976
International Conference on Parallel Processing
, pages 50-54, 1976.
13. H. Lieberman and C. E. Hewitt. A Real Time Garbage Collector Based on the Lifetimes of Objects.
Communications of the ACM,
26(6), pages 419-429, 1983.
14. Guy L. Steele. Multiprocessing compactifying garbage collection.
Communications of the ACM,
18(9):495-508, September 1975.
15. Guy L. Steele. Corrigendum: Multiprocessing compactifying garbage collection.
Communications of the ACM,
19(6):354, June 1976.
BACKGROUND OF THE INVENTION
Garbage collectors free the space held by unreachable (dead) objects so that this space can be reused in future allocations.
An on-the-fly garbage collector, i.e., a collector that reclaims unused space in parallel to the running program without stopping it for the collection is a fascinating theoretical idea with important benefits in practice. In particular, in many server platforms the actual operation of stopping all parallel threads in order to do a garbage collection task is a high cost time consuming operation. The reason is that the threads cannot be stopped at any point and thus there is a relatively long wait until the last (of many) threads reaches a point where it may stop.
The study of on-the-fly garbage collectors was initiated by Steeles and Dijkstra et. al. [14, 15, 4] and was continued in a series of many papers (see for example [5,8,1,2,11 and 12] culminating in the Doligez-Gonthier-Leroy (DGL) collector [6,7].
The specified collectors are of the so called mark and sweep collector type. In these type of collectors, there is normally a first step, in which the live objects in the heap are marked and there is a second step in which the unmarked objects are “swept”, i.e., reclaimed for future use.
The trace of live objects is done with a 3-color scheme: Objects are white if they have not been traced, they are marked gray if they have been traced but their immediate children have not been traced yet, and they are marked black if they have been traced and their immediate children have been traced as well. The trace proceeds step by step by taking a gray object, marking it black and marking gray all its white children.
The fact that the collector works “on-the-fly” makes its life harder. Thus, while it is scanning the heap, the reachability graph is changed by the user program concurrently. If the collector uses this naive search, it may miss some live items. If, for example, (see
FIG. 1
) the user program moves a white node (
1
) from being reference by a gray object (
2
) (i.e., whose children (
3
and
4
) have not yet been traced) to being referenced by a black object (
5
) (whose sons (
6
,
7
) will not be traced any more), then the white object (
1
) (and its sons, if any) may not be traced.
To solve this problem and let the collector spot all live objects during the trace, the program threads help the collector through a write barrier. During the time that the collector performs the tracing of the heap, whenever a pointer is modified from pointing to an object A into pointing to object B, either A or B are marked gray by the modifier thread (by the embodiment of
FIG. 1
object (
1
) is marked gray either when the connection to (
5
) is created or when reference from (
2
) is erased). Choosing which of the objects to mark is up to the specific algorithm. In some algorithms both A and B may be marked gray. This operation of the program is sometimes called the “write barrier” or the “update protocol”.
Another issue is how to color newly allocated objects during the collection. A solution to the latter problem is sometimes called the “create protocol”.
The specific details of an on-the-fly algorithm are well documented in the literature and therefore will not be expounded upon herein.
Turning now to generational garbage collection, the idea was introduced by Lieberman and Hewitt [13]. Generational garbage collectors rely on the assumption that many objects die young. The heap is partitioned into two parts: the young generation and the old generation. New objects are allocated in the young generation which is collected frequently. (See
FIG. 2
)
Young objects that survive several collections are “promoted” to the older generation. Since the young generation is kept small, most collections are fast and do not stall the application for too long, giving rise to the following advantages:
1. Most collections are fast and efficient: they concentrate on the young part where a high percentage of garbage is normally found.
2. The young generation is frequently collected and therefore can be frequently reused.
3. The collector uses a smaller working set since most collections only scan a small part of the young generation.
4. The specified advantages give rise to an overall system behavior with less paging: the collector traces through less pages and the program keeps a small working set since the heap is reused.
Traditionally, generational collections partition the heap into the generations in a physical sense. Namely, to promote an object from the young generation to the old generation, the object has to be moved from the young part of the heap to the old part of the heap. Reverting for a moment to on-the-fly collectors it is not recommended to move objects in the heap (by the collector) concurrently with the run of the program since a given object may be used by the program whilst being

Affiliated with

Also associated with

Rating

On-the-fly garbage collector does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with On-the-fly garbage collector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-the-fly garbage collector will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2606956