Incremental heap expansion in a real-time garbage collector

Details Incremental heap expansion in a real-time garbage collector Incremental heap expansion in a real-time garbage collector

1998-06-09

2001-09-04

Alam, Hosain T. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C711S170000

Reexamination Certificate

active

06286016

ABSTRACT:

BACKGROUND
A. Field of the Invention
The present invention relates to data processing systems and, more particularly, to dynamically expanding and contracting the heap in a real-time data processing system with automatic memory management garbage collection.
B. Description of the Related Art
The performance of computer systems depends in large part on the efficiency of their memory management. For example, the manner in which memory is allocated and deallocated to a procedure in a computer system can significantly affect the overall performance of the system. Computer programs typically comprise a number of procedures containing instructions for performing a discrete unit of functionality. It is common for many programs to run on a computer system, with each program containing many procedures. Thus if memory allocation and deallocation occurs inefficiently, the overall performance of the system can be greatly affected. Likewise, efficient memory allocation and deallocation can greatly improve the overall performance of the system.
Many computer programs are object oriented and perform their processing by using a number of objects. An “object” is a combination of data and behavior, and at some point during an object's lifetime, the object typically is created in memory and resides in the “heap,” the memory space used by an active procedure. When an object resides in the heap, it may be referenced by using a pointer. A “pointer” is a relatively small amount of information, such as a memory address, that is used to access the object. Objects may internally use pointers to refer to other objects. Sometimes, an object becomes unreachable and can no longer be accessed either directly or indirectly. Objects can become unreachable, for example, when a procedure completes and the object is no longer used or when a referencing object's pointer to the object is overwritten. If an object becomes unreachable, the object is needlessly occupying memory and is thus considered to be “garbage” (a “garbage object”). In such circumstances, the memory this object occupies can be reclaimed by the system so that it can be reused. The phrase “garbage collection” refers to automatic memory management strategies involving the identification or removal of unreachable objects and the reclamation of the memory space occupied by the unreachable objects.
As part of their memory management scheme, some garbage collection strategies relocate “live” objects, objects still reachable by the executing procedure. As shown in
FIG. 1
, some of these garbage collection strategies, referred to as copying garbage collectors, generally copy the live objects
100
from one memory space, the old memory space
102
, to another memory space, the new memory space
104
, leaving behind the garbage objects
106
and updating all references to relocated objects. Thereafter, the old memory space
102
from which the objects were copied will contain only garbage objects and can be reused because all live objects have been removed. During the running of a procedure, some of the live objects in the new memory space
104
eventually become unreachable and become garbage. And as new, live objects are allocated, the new memory space fills up. When the now memory space
104
fills, the process repeats itself by copying, only the new live objects
108
and the live objects
100
that have not become unreachable in the new memory space back to the old memory space
102
, thus leaving behind any garbage objects contained in the new space. Copying is a time-efficient garbage collection strategy because it avoids searching for and selectively removing garbage from the memory space.
During execution of a procedure, copying garbage collectors copy the live objects from the old memory space to the new memory space, by first copying the root set of the procedure. The “root set” of a procedure is an object that is the origination point from which all reachable objects of the procedure can be traced. The root set also contains global variables, local variables, and registers used by the procedures. If an object is not reachable from the root set either directly or indirectly (through a path of pointers), the object is unreachable and hence garbage.
Once the root set has been copied, each live object will be scanned. When an object is “scanned,” all objects to which it directly refers are copied from the old memory space to the new memory space, and pointers in that object are updated to point to the newly relocated position. For instance, the scanning of the root set will copy all of the objects directly pointed to by the root set. This process, known as “transitive closure”, copies all objects pointed to by the root set, all objects pointed to by them, etc. When all of the objects in the heap are copied and scanned, all live objects will have been copied over from the old space into the new space and all references updated. Consequently, all of the garbage will be left behind in the old space. A more complete description of copying garbage collectors, scanning, and other garbage collection aspects can be found in Wilson,
Uniprocessor Garbage Collection Techniques,
University of Texas, Lecture notes in Computer Science, International Workshop on Memory Management, September 1992, which is hereby incorporated by reference.
One important aspect associated with some procedures is, they must have a bound on the maximum amount of time they can use. These procedures have real-time requirements, meaning the amount of processing time must be predictable and typically short. For example, real-time procedures are very useful for data processing applications demanding a rapid and reliable processing speed for transmission of video or voice signals. For such real-time procedures, real-time garbage collection strategies have been developed. In real-time garbage collection strategies, the procedure can rely on garbage collection-related processing not exceeding a maximum amount of time and not imposing an unexpectedly large time burden on the system. As such, in a real-time garbage collector, the maximum amount of time that can be consumed by the garbage collector for its processing is known even in the worst case scenario.
Henry Baker published a garbage collection strategy for real-time garbage collection in a 1978 paper, Baker,
List Processing in Real Time on a Serial Computer,
M.I.T. C.A.C.M. 21, 4 (4/78), 280-294, 1978, which is hereby incorporated by reference. For a summary of this strategy, see also Richard Jones and Rafael Lins,
Garbage Collection: Algorithms for Automatic Dynamic Memory Management,
John Wiley & Sons, 1996, which is also incorporated herein by reference. Baker's strategy operates in a similar manner to the copying garbage collectors discussed above, scanning in the objects from the old memory space to the new memory space. However, this scanning is performed incrementally and interleaved with allocation of new objects into the new memory space, so that, in most cases, it can be ensured that all live objects are copied and all pointers updated before the new memory space is filled. For every new object put into the new memory space, a predetermined number of live objects are scanned. As before, all garbage is left behind in the old memory space, and the old memory space will be free for use when the process reverses to copy live objects from the new memory space back to the old memory space.
Although Baker's algorithm was an advance over then-existing garbage collection strategies with respect to real-time systems, it was developed during a time when computers had a small amount of memory, which may pose a problem: if the amount of memory space in use overflows, the procedure aborts. Another limitation of Baker's strategy is, if more than the expected fraction of objects survive from the old memory space to the new memory space, there may not be enough space remaining for allocation of new objects. In this situation, since copying is interleaved with allocation, the new memory space will run out of spac

Affiliated with

Also associated with

Rating

Incremental heap expansion in a real-time 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 Incremental heap expansion in a real-time garbage collector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental heap expansion in a real-time garbage collector will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2477765