Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-01-10
2003-01-21
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06510440
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to garbage collection mechanisms that automatically recover memory that is no longer in use by an operating system nor application programs in a computer system, and more particularly to a system and method for reducing computational overhead associated with such garbage collection mechanisms.
BACKGROUND OF THE INVENTION
Modern programming systems that support object-oriented data models often provide automatic storage management, thereby freeing the programmer from the requirement of explicitly requesting storage for data from the system, and, more importantly, offering storage when it is no longer needed. The latter requirement has historically been the source of many and the most troublesome program bugs. Automatic recovery of storage no longer in use is often referred to as garbage collection.
Garbage collection is a complex topic that has been the subject of many technical articles and at least one text book. The following is a simplified explanation of dynamic memory allocation and garbage collection. For a more detailed discussion of basic garbage collection technology, see, for example, Richard Jones and Rafael Lins, “Garbage Collection,” John Wiley & Sons Ltd., 1996, U.S. Pat. No. 5,088,036, and U.S. Pat. No. 5,930,807, all of which are incorporated by reference in their entirety.
Referring to
FIG. 1
, there is shown a typical computer system
100
having a central processing unit (CPU)
102
, user interface
106
, and main memory
108
. The main memory
108
stores an operating system
110
and one or more application programs
112
(one shown). The operating system
110
and application programs
112
comprise processes (also called threads or tasks) that include program code and data (such as constants, local variables and other parameters) used in the execution of the program code. In addition, the main memory
108
stores at least one heap
116
used for dynamic memory allocation. The space in main memory
108
allocated to store the operating system
110
, application programs
112
, and the heap
116
need not be contiguous. For example, pages or possibly larger contiguous chunks of main memory can be typically linked together using tables or other well known prior art mechanisms.
The program code and data stored in main memory
108
refers to objects. The term “object” is herein defined to mean any data structure created by a process. The heap
116
stores such objects. More specifically, when a process spawns an object, a memory allocation routine
118
in the operating system is called. The memory allocation routine
118
responds by allocating a region in the heap
116
for storing the object.
The representation of the object in the heap may vary. In object-oriented programming systems, for example, an object typically contains the variables declared in the object's class and all of the object's super classes. It should be noted that the heap
116
may store additional information related to the objects, the details of which are not relevant to the present invention.
The program code and associated data stored in main memory
108
use a reference to point to the representation of a given object in the heap
116
. Such a reference is referred to herein as an “object reference.” The object reference may be direct or indirect. A direct object reference identifies the location in main memory for the object (for example, the location in main memory of the header of the object). On the other hand, an indirect object reference points to an object handle, which can be used to locate the location in main memory for the object. In this document, the term object reference refers to both direct and indirect object references.
The memory allocation routine
118
discussed above may occur repeatedly. Clearly, if this routine continued unabated, all of the space in the heap
116
would be exhausted. Therefore, space in the heap
116
must be restored by either explicit action of the program, or some other mechanism.
The solution to this problem is to recover blocks of memory space in the heap
116
that are no longer being used by the active processes. Garbage collection is a term that refers to automatic methods of recovering unused memory in the heap
116
. Garbage collection is based on the fact that if no pointer to a heap object exists anywhere in the executing environment of a program, the object can never again be accessed and therefore the storage occupied by the object can be reused for another object. Garbage collection comprises the identification of all reachable objects, i.e., those that can be accessed by the executing program. All reachable objects are identified by marking all objects pointed to by the roots of a programs (i.e., local variables and static variables) and all objects pointed to by objects pointed to by roots, recursively, until all reachable objects have been identified. Reached objects are considered “live” and are kept. Objects which are not reached are considered “dead” and their storage space is made available for future allocations.
A garbage collection routine
120
typically gathers and recovers unused memory upon the occurrence of a predefined event, such as the expiration of a predetermined time period or the available heap memory reaches a predefined threshold. A large number of different garbage collection methodologies have been proposed. For a discussion of the state of the art, see, for example, Jones and Lin, “Garbage Collection,” John Wiley and Sons Ltd, 1996, incorporated by reference in its entirety above.
One way to make garbage collection more efficient, and to reduce the length of system pauses caused by garbage collection, is to reduce the number of objects that need to be processed during a given garbage collection cycle using a generational garbage collection scheme. Generational schemes are based on the observations that most objects have short lifetimes, dying shortly after they are allocated, and that objects which do not die quickly and have been reachable for some time will continue to be reachable (i.e. live). Generational schemes partition the objects in the heap into groups called “generations,” based upon the ages of the objects, where an object's age is typically measured in terms of the number of garbage collections that the object has survived. For this discussion, consider two generations, a “young” generation of recently allocated objects, and an “old” generation of objects which have survived some minimum number of collections. Typically, the young generation is much smaller than the older generations.
Generational schemes perform frequent collections of the young generation, and only occasionally do full collections of the entire heap. Typically, generational schemes perform a minor garbage collection upon the occurrence of a predefined event (such as the expiration of a predetermined time period or the available heap memory reaches a predefined threshold). The minor garbage collection routine identifies younger generation objects that are not reachable from the objects stored in the heap, and identifies the space in the heap previously allocated to one or more of these objects as a candidate for reclamation. Less frequently, a major garbage collection routine is performed that identifies all objects that are not reachable from the objects stored in the heap, and identifies the space in the heap previously allocated to one or more of these objects as a candidate for reclamation
FIG. 2
shows a system in which the heap
116
has been logically divided into three generations: Generation
0
stores the youngest objects, Generation
1
stores objects that have persisted for at least N garbage collection cycles (where N is typically a value between 1 and 4), and Generation
2
stores the oldest objects in the system. The simplest policy is to advance all live objects from one generation to the next oldest generation each time a generational garbage collection is performed. Another technique is to divide the youngest generation i
Alpern Bowen
Attanasio Clement Richard
Smith Stephen Edwin
International Business Machines - Corporation
Pham Hung
Vu Kim
LandOfFree
Method and apparatus for performing generational garbage... 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 apparatus for performing generational garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing generational garbage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015891