Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-07
2001-09-11
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06289360
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to garbage collection for computer memory management and, in particular, to a concurrent garbage collection algorithm.
REFERENCES
Many of the prior art techniques mentioned in the next section are discussed in greater detail in the following publications:
[1] Edsgar W. Dijkstra, Leslie Lamport, A. J. Scholten, E. F. Scholten, E. F. Steffens, On-the-fly Garbage Collection: An Exercise in Cooperation,
Communications of the ACM
, November, 1978.
[2] Paul Hudak, Robert M. Keller, Garbage Collection and Task Deletion in Distributed Systems,
ACM Symposium on Lisp and Functional Programming
, pp. 168-178, Pittsburgh, Pa, August 1982.
[3] Damien Doligez, Xavier Leroy, A concurrent generational garbage collector for a multithreaded implementation of ML,
Proc
. 20
th Symp. Principles of Programming Languages
, 1993, pp. 113-123.
[4] Damien Doligez, Georges Gonthier, Portable Unobtrusive Garbage Collection for Multi-Processor Systems,
Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages
, January, 1994.
[5] Leslie Lamport, Garbage Collection with Multiple Processes: An Exercise in Parallelism, 1978.
[6] Leslie Lamport, How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs,
IEEE Transactions on Computers
, C-28(9): 690-691, September 1979.
BACKGROUND OF THE INVENTION
Within the context of computer memory management, garbage collection relates to the automatic reclamation of computer storage. When data objects such as arrays, records and other data structures are created, space for the object is allocated in the heap. The term “object” is used herein to denote generally any piece of memory. When the object is no longer needed, its space must be freed in order that the heap does not become saturated with objects that are no longer required for the computation. Computer programming languages such as Pascal or C, typically require the programmer to attend to reclamation of heap storage manually. The programmer must keep track of information that allows him to determine when an object can be safely discarded. This manual heap maintenance is feasible, although prone to errors.
The continuing need to avoid such errors has rendered systems and languages supporting garbage collected heaps very attractive. Developing software in such environments is much faster because garbage collection eliminates a large class of programmer errors, both in the design and implementation stages. Furthermore, in programming languages such as Java from Sun Microsystems, which is emerging as a standard Internet tool and a platform-independent implementation vehicle, there is no explicit de-allocation by the programmer and therefore use of these languages mandates a good garbage collection algorithm.
The garbage collector's task is to locate data objects that are not longer required, and to reclaim their space in memory for use by the running program. In mark-sweep garbage collectors, garbage collection is implemented in two successive stages. In a first stage, the object graph described by the interrelation of objects starting from the roots and traversing all connected objects in the heap, is traced so as to identify live objects. An object is considered live if it is reachable either directly from the roots or from some other live object. Any other object is considered garbage and can be collected. The roots include global state (e.g. global variables) and the local state of each thread (e.g. the thread's stack and its local variables on that stack). 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, all the memory space occupied by unmarked objects (garbage) is reclaimed and the marked objects are unmarked, in preparation for the next garbage collection cycle.
In so-called “concurrent” garbage collectors, the execution of the program which updates and changes the object graph is concurrent with the marking and sweeping operations carried out by the collector. Whilst this avoids processor inactivity during garbage collection, the running program may change the object graph during the very act of tracing out reachable data objects by the collector. For this reason, the running program is referred to as the mutator since it mutates or changes the object graph. As a result, there exists the risk that the collector may miss marking a live object and the live object may then be subsequently reclaimed by the collector. In order to avoid this possibility, synchronization between the mutator and collector threads is essential.
An important consideration with regard to concurrent collectors is their degree of conservatism with respect to changes made by the mutator during garbage collection. Thus, an object may have been marked as live by the garbage collector and subsequently made unreachable by the mutator. Such an object constitutes floating garbage which is not reclaimed during the current garbage collection cycle. It will, however, be collected during the next cycle since it will be identified as garbage at the beginning of the next collection.
Floating garbage clogs up the heap unnecessarily and thus is undesirable. Whilst a certain amount of floating garbage may be tolerated and, indeed, is inevitable since no garbage collector can be completely efficient, the reverse can under no circumstances be tolerated. That is to say, reachable objects must never be marked as unreachable by the tracer since their space would then be erroneously collected, causing possibly catastrophic effects on the application program. This asymmetry inclines garbage collectors towards being naturally conservative since it always better not to reclaim garbage than to reclaim it erroneously. This conservatism impacts on the manner in which conflicts between mutator allocation and garbage collector sweep are resolved.
The question arises as to how to mark an object newly allocated by the mutator, especially during the sweep phase of garbage collection, which collects unmarked objects and resets the mark of marked objects. During the sweep phase, an object which is allocated in those locations of the heap that have not yet been swept in the current sweep cycle, must be allocated as marked, so that the sweep will not collect them. Objects which are allocated in an area which has already been swept must be allocated as unmarked in order that they be unmarked for the start of the next collection. This requires synchronization, be it implicit or explicit, between the sweep process and the allocation procedure, lest an object be subsequently reclaimed whilst still alive.
A sub-class of concurrent garbage collectors are so-called “on the fly” garbage collectors first introduced by Dijkstra et al. [1]. In this type of garbage collector, the manner in which reachable objects are marked is by assigning a different color attribute to distinguish between reachable and unreachable objects. This approach has been adopted in both concurrent and “on the fly” garbage collectors, a four-color marking conventionally being used. A “white” color indicates that an object is unmarked. A “gray” color indicates that an object is marked, but that its direct descendants may not yet be marked (i.e. some may be white). A “black” color indicates that an object is marked and that all its direct descendants are marked (either gray or black). Finally, a “blue” color indicates that the object is free. Use of a fourth color to distinguish free objects avoids the need for the garbage collector to trace these objects, and thus saves time. In such a scheme, “gray” or “black” objects are also referred to as “shaded” objects. At the start of the cycle all objects are white. During tracing, the color of live objects progresses from white to gray to black. After tracing, the collector then sweeps: white objects are colored blue and appended to the free list; shaded objects are changed to white in prepa
Kolodner Elliot K.
Lewis Ethan
Black Thomas
Browdy and Neimark
International Business Machines - Corporation
Mills John G.
LandOfFree
Method and system for eliminating synchronization between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for eliminating synchronization between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for eliminating synchronization between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500225