Mostly concurrent compaction in a garbage collection system

Details Mostly concurrent compaction in a garbage collection system Mostly concurrent compaction in a garbage collection system

1999-06-10

2001-06-19

Amsbury, Wayne (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06249793

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
Computer programming systems typically allow programs to allocate data structures on demand, according to the control flow of the program. For example, a mouse click might cause a spreadsheet program to allocate memory for a new bar chart. Such data structures are referred to as “dynamic” data structures, since it is impossible to determine statically how much memory they will require, or for how long they will use any particular memory portion. To support such dynamic data structures, operating systems and/or programming language run-time systems provide mechanisms for dynamically allocating memory. In some systems, management of dynamically allocated memory is left entirely to the programmer. For example, in the C programming language, the malloc function allocates memory, and the free( ) function makes it available for reuse. In C++ the “new” and “delete” operators have the same effect. Both of these languages typically require the program to explicitly deallocate dynamically allocated memory. This approach requires the programmer to indicate what memory to deallocate and when to deallocate it. In complicated programs, it is very difficult for the programmer to do this correctly. Incorrect deallocation of memory may result in a “memory leak” when a portion of memory is not deallocated before the program over-writes the last pointer to it. When this occurs, the memory cannot be deallocated. In addition, a “pointer smash” may result when a program frees a portion of memory while that memory is still in use by another part of the program.
Because of such problems, many modern programming languages include run-time environments in which an independent software component reclaims memory that is no longer in use. The reclaimed memory may then be reallocated as needed. Such run-time components are known as “garbage collectors”. While a garbage collector relieves the programmer of the task of explicitly deallocating memory, executing the garbage collector can have a detrimental effect on system “latency”, by halting the program. In some existing systems, execution of the garbage collector often results in the program being halted for undesirable or unacceptable periods of time. This is a particular problem for programs that are interactive applications, since such halting is directly perceived by the user.
A number of garbage collection algorithms have been proposed and tried over the years. Three commonly used approaches are “reference counting”, “mark and sweep”, and “copying”. Reference counting garbage collectors maintain a counter for each allocated memory object. In this document, a memory object refers to a portion of memory with a well-defined type, size, and structure, e.g. variables of struct type in C, variables of record type in Pascal, or instances in the Java™ programming environment. Java is a trademark or registered trademark of Sun Microsystems, Inc. in the United States and other countries. The value of the counter reflects the number of existing references to the memory object. When the reference counter for a memory object drops to zero, the memory may be returned to a free pool for subsequent reuse. Reference counting provides some relief from performance degradation by imposing a steady overhead based on reference modifications. However, basic reference counting fails to detect circular references (also referred to as “reference cycles”). For example, where a reference A points to reference B, and B points to reference A, but nothing else points to either A or B, neither A nor B will be freed even though they could be. In addition, reference counts must be accessed atomically in a multi-threaded environment, thus introducing substantial overhead associated with each reference count modification.
The “mark and sweep” approach to garbage collection involves distinct steps of 1) marking memory objects that are referenced by existing variables, and 2) “sweeping” everything that is not marked into a free-list. For example, in an execution environment where memory objects are dynamically allocated from a memory heap, marking may be accomplished by finding every object that is currently reachable from the set of currently existing global and local variables, which are referred to as the “root” variables. Such marking involves initially marking everything in the root set, then marking all memory objects referred to by the roots, and continuing recursively until each object reachable from the roots is marked. The sweep phase then returns all unmarked memory objects to the free list. A simple mark and sweep garbage collector must suspend the executing program while it performs both the marking and sweeping phases.
Traditional “copying” garbage collectors also operate by stopping the program during garbage collection. In such systems the heap is divided into two parts, a “current” part and a “new” part. The garbage collector copies all currently referenced memory objects from the current part of the heap into the new part, thus making the current part into contiguous free space. The new part is then made current. While stop and copy provides good compaction each time it runs, it effectively requires twice the memory of other systems. It also suspends program execution for relatively long periods, which is not acceptable in many cases.
The inability to operate concurrently with program execution often results in unacceptable program delays. Accordingly, some attempts have been made to shorten the time during which the program must be stalled. In what is referred to as a “generational” garbage collector, the memory heap is divided into a “young generation” of recently allocated objects, and a much larger “old generation” of older allocated objects. Because the objects in the young generation are more likely to be collectable than those in the old generation, periodic collection of the young generation reclaims significant amounts of memory storage. Because only a relatively small portion of the memory heap is examined, the program is suspended for a much shorter time than is the case where the whole memory heap is garbage collected at once. However, at some point, the larger old generation of allocated objects must inevitably be garbage collected, potentially causing the program to be paused for long periods.
In “mostly parallel” mark and sweep collection schemes, the basic mark and sweep algorithm is modified such that the program is stopped initially only while those objects directly reachable from the roots are marked. The program is then restarted and the objects indirectly reachable from the roots are marked concurrently with program execution. Such a concurrent marking phase is not guaranteed to mark all reachable objects. For example, a situation may arise where an object Obj
1
originally contains a pointer to an object Obj
3
, and an object Obj
2
contains a pointer to an object Obj
4
. At a first point in time, the marking process reaches and marks Obj
1
. The marking process then discovers the pointer to Obj
3
, and recursively marks that object. Before the marking process reaches Obj
2
, however, the program could potentially swap the pointers in Obj
1
and Obj
2
, such that Obj
1
points to the unmarked object Obj
4
and Obj
2
points to the marked object Obj
3
. When the marking process eventually reaches Obj
2
, it will find that it points to an object that is already marked (Obj
3
), and do no further work. The reachable object Obj
4
would not be marked.
To avoid this problem, the mostly parallel scheme arranges to keep track of all reference variables that have been modified since the beginning of the current marking phase. These “dirty” variables hold references that might have been missed by the original marking phase. Thus, when the concurrent marking phase has finished, the program is again suspended, and marking is redone from the roots as well as from any other objects that have

Affiliated with

Also associated with

Rating

Mostly concurrent compaction in a garbage collection system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mostly concurrent compaction in a garbage collection system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mostly concurrent compaction in a garbage collection system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2510322