Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-04-10
2004-04-13
Kim, Hong (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S205000, C711S206000
Reexamination Certificate
active
06721865
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to efficient use of computer memory in carrying out program instructions, and specifically to methods and apparatus for garbage collection, i.e., for automatic reclamation of unused memory.
BACKGROUND OF THE INVENTION
Programming languages such as Java relieve the programmer of the burden of explicit memory management through the use of automatic garbage collection (GC) techniques that are applied “behind the scenes.” When a data object is created, space for the object is allocated in the heap. Unused data objects, which are no longer reachable by the running program via any path of pointer traversals, are considered “garbage.” GC automatically reclaims computer storage assigned to such objects, in order to free the storage for reuse. This makes programming in garbage-collected languages significantly easier than in C or C++, for example, in which the programmer must include an explicit “free” statement in order to reclaim memory. GC allows many run-time errors to be avoided and naturally supports modular programming.
A variety of different GC techniques are known in the art. In mark-sweep garbage collectors, garbage collection is implemented in two successive stages. In a first stage, an object graph is created, tracing the interrelation of objects starting from specified roots and traversing all connected objects in the heap. Objects that are reachable on this graph are considered live objects. Any other object is considered garbage and can be collected. The live objects are marked in some way so as to distinguish between live objects and garbage. In a second stage, the memory is swept, and all memory space occupied by unmarked objects (garbage) is reclaimed, so that it is free to be reallocated. During the sweep stage, the marked objects are unmarked, in preparation for the next GC cycle.
In “concurrent” GC, the execution of application program threads that may update and change the object graph goes on concurrently with the marking and sweeping operations carried out by a collector thread. For this reason, threads of the running program are referred to as “mutators,” since they mutate, or change, the object graph. Although the concurrent approach avoids processor inactivity during GC, the running program may change the object graph even during the very steps of tracing out reachable data objects by the collector. As a result, there is a risk that the collector may miss marking a live object, and the live object will then be reclaimed during the sweep phase of the collector. In order to avoid this possibility, synchronization between the mutator and collector threads is essential.
“On-the-fly” concurrent GC schemes use implicit synchronization between the mutator and collector threads in order to allow the threads to run concurrently without having to stop for synchronization. This type of GC was first described by Dijkstra et al., in “On-the-Fly Garbage Collection: An Exercise in Cooperation,” published in
Communications of the ACM
21:11 (1978), pages 966-975, which is incorporated herein by reference. Reachable objects are marked by assigning a different “color” attribute to each object, with “white” indicating unmarked objects, and “black” indicating marked objects. At the beginning of a GC cycle, all objects are white. Whenever a mutator uses a white object, it marks the object “gray.” When the collector encounters a gray object, it knows that while the object is alive, its direct descendants in the pointer graph may not yet have been marked (i.e., some may still be white). On the other hand, when an object is marked black, all of its direct descendants are necessarily marked as well, either gray or black. During the mark/trace phase, the collector traces the graph of live objects, and in doing so changes the color of all gray objects to black and their descendants to gray, continuing until no untraced gray objects remain. After all of the live objects have been traced, the collector then sweeps: white objects are reclaimed and appended to the list of free memory, while black objects are changed to white in preparation for the next collection cycle.
Dijkstra's approach, while conceptually valuable, has inherent inefficiencies that have prevented it from being widely implemented in practice. Doligez and associates have attempted to overcome these limitations by adding a fourth color: “blue.” During the sweep phase, the collector marks white objects as blue, to distinguish them as free. This approach is described by Doligez and Leroy, in “A Concurrent Generational Garbage Collector for a Multithreaded Implementation of ML,” published in
Proceedings of the
20
th Symposium on Principles of Programming Languages
(1993), pages 113-123; and by Doligez and Gonthier, in “Portable Unobtrusive Garbage Collection for Multi-Processor Systems,” published in the
Conference Record of the Twenty
-
first Annual ACM Symposium on Principles of Programming Languages
(1994), pages 70-83. Both of these publications are incorporated herein by reference.
Marking free memory as blue frees the collector from having to trace the list of free memory, but it obligates the mutators to properly color all new objects that they allocate (i.e., objects they create from free memory). The proper color for allocation depends on the stage of the collection cycle currently being executed by the collector thread. While no GC is taking place and at the start of the collection cycle, the proper color is white. At a transition point for each mutator during the mark/trace phase of the collector (the point at which the collector has marked the mutator's local stack), the proper allocation color becomes black. During the sweep phase of the collector, the color for allocation can be white, gray or black, depending on the address of the object being created relative to the progress of the collector in sweeping the heap.
The collector uses a handshaking protocol to synchronize the mutators with its state, so that the mutators use the correct coloring. Proper execution of the protocol is critical: if a newly-allocated object is colored white at the wrong time, it will be incorrectly collected. If it is incorrectly colored black, before its immediate descendants have been marked, the descendants may be incorrectly collected. This problem can be alleviated by extending the period during which the mutators color objects gray, since neither gray objects nor their descendants are collected in any given GC cycle. This solution, however, runs counter to the primary goal of GC, which is to free unused memory.
One alternative solution to the problem of synchronizing the mutators with the collector is to switch the meaning of the colors “black” and “white” from one GC cycle to the next. An approach of this sort is described by Hudak and Keller, in “Garbage Collection and Task Deletion in Distributed Applicative Processing Systems,” published in the
ACM Symposium on Lisp and Functional Programming
(1982), pages 168-178, which is incorporated herein by reference. This approach, however, is designed to work in a specific parallel processing system, in which the role of the program stack is taken over by a “marking-tree” of tasks. It does not appear to be of general applicability in on-the-fly GC for use with Java and other common software environments.
SUMMARY OF THE INVENTION
Preferred embodiments of the present invention provide a method for on-the-fly GC in which objects are colored before they are created, thus relieving the mutators of a major part of the burden of object coloring. This technique is referred to hereinafter as “pre-coloring.” Preferably, the mutators pre-color blocks of memory while preparing them for allocation, as a batch operation, instead of coloring objects singly as they are created as in methods known in the art. Periodically, the collector checks the memory that is prepared for allocation to ensure that it has the proper allocation color. Thus, the coloring overhead is borne primarily by the collector, and the sp
Darby & Darby
International Business Machines - Corporation
Kim Hong
LandOfFree
Elimination of coloring during object creation for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Elimination of coloring during object creation for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elimination of coloring during object creation for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198575