Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-13
2002-05-21
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06393440
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the general field of memory management and concerns more specifically automatic memory management or garbage collection (GC).
BACKGROUND OF THE INVENTION
Garbage collectors free the space that can no longer be used by a program so that this space can be reused for future allocations. In many systems, the unit of space allocated by a program and freed by the collector is called an object. A so-called “concurrent” garbage collector represents a general class of collectors in which the mutators continue to work while the collector is active. Note, however, that there may be a point during the GC cycle where all the mutator threads need to be stopped at once. An on-the-fly collector based on the original article by Dijkstra et al. [Edsgar W. Dijkstra, Leslie Lamport, A. J. Scholten, E. F. Scholten, E. F. Steffens, On-the-fly Garbage Collection: An Exercise in Cooperation, November, 1978,
Communications of the ACM]
does not have a synchronization point where all threads are stopped at once. Doligez and Gonthier [Damien Doligez, Georges Gonthier, Portable Unobstrusive Garbage Collection for Multiprocessor Systems, January, 1994,
Conference Record of the Twenty
-
first Annual ACM Symposium on Principles of Programming Languages]
described a more advanced and more efficient on-the-fly algorithm.
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, on 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. Additionally, stopping all program threads during garbage collection does not take advantage of all available processors.
On-the-fly garbage collectors are well known in the literature. On-the-fly collectors generally use mark\sweep whereas concurrent collectors may also use other garbage collection techniques e.g. copying. In the mark\sweep type of collectors, there is normally a first step, in which the live memory 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 normally (although not necessarily) 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 yet been traced, 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 user program threads change the reachability graph concurrently. If the collector uses this naive scheme, it may miss some live items. If, for example, (see
FIG. 1
) the user program moves a white node (
1
) from being referenced 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 use of a write barrier. During the garbage collecting cycle, 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 depends on the specific algorithm or the stage of the algorithm. Sometimes, algorithms may mark both A and B gray and sometimes only A or only B. This operation of the program is sometimes called the. “write barrier” or the “update protocol”.
In a typical scenario, more than one program thread (referred to also as mutator thread) and the collector thread run simultaneously, meaning that the update (graying) of the objects is executed also during collection. Thus, not only do the mutators gray objects in parallel one with the other, but they also gray objects in parallel with the collector during trace. Collector, in this context, signifies one or more collector threads.
This manner of operation may create race conditions between mutators, and/or between the collector and the mutators, which is obviously undesired. Race conditions may occur for example in the following scenario. Marking an object gray by the mutators and the handling of gray objects by the collector may occur concurrently. This may create a race condition if there is a need to keep track of the gray objects.
In a multiprocessor environment, previous implementations have either required frequent explicit synchronization between the collector and the mutators in order to keep track of the gray objects (e.g. using a single mark buffer), or have been inefficient and required repeated scans of the heap (or a data structure proportional to the size of the heap) until there are no more gray objects. The first option slows down the mutators and the second option slows down the collector, delaying the collection of garbage.
Turning to the specified second solution of repeatedly scanning the heap to find the gray objects, it requires little synchronization between the mutator threads and the collector thread. However, not only is scanning the heap multiple times inefficient, but it may require bringing every page of the heap into memory, which may be very costly time-wise. This problem may be ameloriated by using a color bitmap (as described in “Garbage Collection” by Richard Jones and Rafael Lins, pp. 87-88) to hold the color representation of objects. However, this still requires multiple scans of the color bitmap, whose size is proportional to the size of the heap, until no grays remain, hence it suffers from the same inefficiency drawback.
In accordance with an alternative approach, queuing gray objects in a mark buffer will eliminate the need for multiple scans by keeping track of all remaining gray objects, i.e., those that still need to be traced by the collector. However, having multiple writing threads to the same mark buffer requires synchronization, which as specified before gives rise to an undesired slow down.
There is accordingly a need in the art to provide for a novel technique which enables to carry out tracing of memory objects, with little or no explicit synchronization. The proposed approach is also useful for other applications which employ multiple writers and single reader.
SUMMARY OF THE INVENTION
In the context of the invention, reference to a memory object should not be construed to any specific data type or size. Object should be construed in a broad manner including any area of memory which is returned in response to an allocation request by a program thread.
Reference to colors of memory objects is provided for illustrative purposes only, indicating corresponding state associated with the memory object.
Thread should be construed in a broad manner including “process”.
Whilst, for simplicity, the invention is described with reference to an on-the-fly garbage collection application, those versed in the art will readily appreciate that the invention is by no means bound by this example. Thus, by another non-limiting embodiment, the garbage collection technique of the invention is used with concurrent garbage collection algorithm. It should be further noted that the use of the invention is not necessarily bound to the so called “mark and sweep” algorithm.
In accordance with the br
Kolodner Elliot K.
Salant Eliot
Black Thomas
Browdy and Neimark
Coby Frantz
International Business Machines - Corporation
LandOfFree
Data structure for keeping track of objects remaining to be... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure for keeping track of objects remaining to be..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for keeping track of objects remaining to be... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2898090