Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-10-10
2002-12-10
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06493730
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to allocating storage space for objects within a persistent object system. More specifically, the present invention relates to allocating storage space for persistent objects within the heap of a persistent object system that uses a generational garbage collector.
2. Related Art
Many modern computing devices, for example web servers, execute computer programs that are designed to run for long periods of time. It is advantageous for these computing devices to have a persistent object system that allows faster recovery when the computer program is stopped and restarted. A computer program can be stopped and restarted for a number of reasons. For example, the computing device may need maintenance, the power may fail, or a program executing on the computing device may fail.
A persistent object system provides the illusion of a very large object heap that is automatically backed by stable storage. During operation of a persistent object system, objects are automatically saved to stable storage, typically on a disk, and fetched from stable storage into virtual memory on demand.
Persistent object systems automatically perform atomic writes to stable storage in order to ensure that a program's data will survive intact even if the program crashes. Hence, persistent programs (programs using a persistent object system) do not have to reinitialize the state of their objects when they restart. This reduces application startup time and eliminates the need for code to recreate and reinitialize objects.
To make persistent programs as fast as possible, object faulting must be efficient. This means that object heap allocation must be efficient. This is especially true for persistent programs as these programs often fault-in millions of objects. During object faulting space is allocated for an object in the program's garbage collected object heap, and the persistent object is copied into the allocated space from the stable store.
Many high-performance garbage-collected object heap implementations are generational. They take advantage of the fact that most objects have a short lifetime and segregate objects into two or more regions of the object heap called generations. In a two generation object heap implementation, these can be termed a young generation region and an old generation region. New objects are allocated to the young generation region, which is garbage collected frequently to reclaim the storage of short-lived objects. Long-lived objects that survive several young generation garbage collections are promoted (moved) to the old generation region.
Faulting persistent objects into the young generation can make garbage collection, especially young generation garbage collection, much more time-consuming than garbage collection of non-persistent systems. Objects faulted-in by a persistent object system tend to have longer lifetimes than newly allocated transient (non-persistent) objects. Hence, when a faulted-in object is allocated in the young generation region, it usually ends up being promoted to the old generation region after several young generation region garbage collections creating needless work for the young generation garbage collector.
References from the old generation region to the young generation region are normally rare but are common in persistent object systems where persistent objects are faulted-in to the young generation region. The young region garbage collectors must do substantial work for the persistent objects faulted-in to the young generation region because object heap implementations store references from the old generation region to the young generation region in data structures that are designed to save space rather than for fast processing.
If the rate at which persistent objects are faulted-in is high, the young generation region is mostly filled with long-lived persistent objects. This causes the rate of the young region garbage collections to increase. Also, each of the young region garbage collections will reclaim only a small number of objects. Furthermore, each young region garbage collection will typically be much more expensive because of the cost of processing a large number of references from the old generation region to the young generation region as explained above.
Hence, faulting persistent objects to the young generation region of the object heap is inefficient.
What is needed is a persistent object system that eliminates the above-described disadvantages of faulting a persistent object into a young generation region of an object heap.
SUMMARY
One embodiment of the present invention provides a system for allocating storage space for objects within a persistent object system. The persistent object system includes an object heap that is organized into a young generation region and an old generation region. The system uses the young generation region to store newly created objects and uses the old generation region to store objects that have not been removed by several garbage collection cycles. The system allocates storage space for new (transient) objects in the young generation region of the object heap. Periodically, the system copies the transient objects from the object heap to a stable store to form a checkpoint of the system state. Transient objects become persistent objects when they are copied to the stable store. Persistent objects are removed from the object heap when the system is stopped and when room is needed in the object heap for additional objects. When a persistent object that has been removed from memory is referenced during execution of a computer program, the system faults the persistent object directly into the old generation region of the object heap from the stable store.
In one embodiment of the present invention, the object heap is located in a virtual memory of the persistent object system.
In one embodiment of the present invention, the object heap can include regions for generations other than the young generation region and the old generation region.
In one embodiment of the present invention, transient objects are newly created objects.
In one embodiment of the present invention, the generational garbage collector reclaims unreferenced objects. In doing so, the generational garbage collector first deletes objects that are no longer referenced from the object heap. Next, the generational garbage collector reallocates storage space formerly used by the deleted objects within the object heap. Finally, the generational garbage collector promotes transient objects from the young generation region of the object heap to the old generation region of the object heap if the transient object is not deleted by the generational garbage collector after a user configurable number of garbage collections.
In one embodiment of the present invention, the system copies transient objects to the stable store in order to generate a checkpoint of a state of the computer program.
In one embodiment of the present invention, the persistent object is removed from the object heap because the persistent object system required more space within the object heap, the persistent object system was shut-down or stopped because of a hardware or software error; or the persistent object system was subject to a system crash or power failure.
In one embodiment of the present invention, the system faults persistent objects directly into the old generation region of the object heap by allocating space in the old generation region of the object heap, and then copying the persistent object from the stable store to the old generation region of the object heap.
REFERENCES:
patent: 6247027 (2001-06-01), Chaudhry et al.
patent: 6339782 (2002-01-01), Gerard et al.
patent: 6393439 (2002-05-01), Houldsworth et al.
Atkinson Malcolm P.
Lewis Brian T.
Mathiske Bernd J. W.
Printczis Antonios
Grundler Edward J.
Mizrahi Diane D.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Wu Yicun
LandOfFree
Efficient object faulting with generational garbage collection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient object faulting with generational garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient object faulting with generational garbage collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2983302