Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-04-27
2004-07-27
Jung, David (Department: 2134)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S170000
Reexamination Certificate
active
06769004
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method for automatic memory management known as “garbage collection.” More specifically, this invention relates to improvements in incremental garbage collection most useful for object-oriented program-controlled systems with real-time constraints.
BACKGROUND OF THE INVENTION
Briefly, garbage collection, the automatic recycling of dynamically allocated memory, is a tried and tested memory management technique that has been in use since its invention by John McCarthy in 1958 as part of the implementation of Lisp. Garbage collection avoids the need for the programmer to deallocate memory blocks explicitly, thus avoiding a number of problems, including memory leaks, double frees, and premature frees. The burden on the programmer is reduced by not having to investigate such problems, thereby increasing productivity, and dramatically simplifying programs by allowing modules to present cleaner interfaces to each other. The use of garbage collectors in automatic memory management is well known in the prior art, and detailed descriptions of the art appear in U.S. Pat. No. 6,055,612 and other sources cited in this disclosure, and incorporated by reference herein. The reader is assumed to be one of skill in the art and familiar with the terms common to the art.
Nevertheless, many garbage collectors stop all other activity in the system for a significant, unpredictable duration of time while the garbage collector is running, which makes these systems unsuitable for systems with real-time constraints. In response to such limitations in standard garbage collectors, a number of incremental garbage collectors have been proposed and developed which avoid the stop-and-collect procedure of traditional garbage collectors. However, the incremental garbage collectors developed to date have not fully met the needs of a hard real-time system.
Many existing incremental garbage collectors require some unpredictable and possibly large atomic operation either at the start of a collection cycle or as part of the completion of the mark phase. For example, the garbage collector described in Taiichi Yuasa, “Real-Time Garbage Collection on General Purpose Machines,”
Journal of Software
&
Systems,
11(3):181-198 (1990), copies the entire program stack at the start of a collection cycle, and incrementally scans that copy. The garbage collector disclosed in Mark Stuart Johnstone, “Non-Compacting Memory Allocation and Real-Time Garbage Collection,” Ph.D. thesis, U. of Tex. at Austin (December 1997), treats all stacks as part of the root set to be scanned in an atomic operation at the start of each collection cycle. While these solutions lead to some efficiency gains, both suffer from an unpredictable and possibly large startup pause.
Likewise, the garbage collector disclosed in Tian F. Lim et al., “A Memory-Efficient Real-Time Non-Copying Garbage Collector,”
Conference Proceedings of the International Symposium on Memory Management
, Vancouver, Canada (October 1998), scans stacks at the end of a collection cycle, scanning all stacks and then reinitiating the mark phase for objects shaded grey during the stack scan. (For purposes of additional clarity in this disclosure, the tri-color marking scheme is used in which during the mark phase of the collector, objects are partitioned into three sets. Black objects have been noted as reachable and have had their contained references scanned. Grey objects have also been noted as reachable but their contents have not yet been scanned. White objects have not yet been noted as reachable and might be reclaimed. To mark an object, the method of system examines its color, and if it is white, transfers it to the grey set. Grey objects are transferred to the black set when they are scanned.) Lim et al. make this process incremental by limiting the amount of stack scanning that will be performed and rescanning those stacks that were reactivated after a preempted increment of stack scanning. This solution presents two limitations: first, the granularity of this operation is relatively coarse, and second, a high rate of stack reactivation could significantly delay the completion of this process, possibly indefinitely.
Finally, Thierry Le Sargent & Bernard Barthomieu, “Incremental Multi- Threaded Garbage Collection on Virtually Shared Memory Architectures,” in
Proceedings of International Workshop on Memory Management
, St. Malo, France (September 1992), propose the use of virtual memory support to perform incremental stack scanning. In their proposed collector, the top page of each stack is treated as part of the root set and scanned at the start of the collection cycle, while other pages of the stack are made inaccessible. An attempt to access an inaccessible stack page is trapped by the virtual memory system, and the page is scanned at that time. The incremental scanner then scans stack pages that have not otherwise been scanned. This approach requires that essentially arbitrary chunks of the stack (or individual pages) can be scanned with little or no information available about their content, which imposes possibly significant restrictions on what the mutator can store on the stack and in what format.
Therefore, while many incremental garbage collectors—including those discussed above—are described as real-time, for the reasons discussed their performance cannot meet the needs of certain real-time applications. For these systems, results must be on time, and a late result is as useless as an incorrectly calculated one. Therefore, there remains the need for an improved garbage collector able to satisfactorily meet the needs of a system requiring real-time operation.
SUMMARY OF THE INVENTION
The object of the invention is attained by modifying an incremental garbage collector so that the stack scan can be performed incrementally in units of individual stack locations without having to rescan any stack when the garbage collector is preempted by the system to perform real-time operations.
In the present invention, the stack is scanned by dividing it into call frames, and by using continuation replacement to notify the collector that the mutator has modified a frame being processed by the collector. In one embodiment, a stack is scanned in push order, from the base of the stack toward the top of the stack.
In the preferred embodiment, when starting the scan of a call frame, the continuation for reactivating that call frame is replaced with an unwind routine which is used to detect reactivation of that frame. The scan of the stack is made incremental by recording at each step the call frame being processed and the progress made so far in processing it. This allows the stack scanner to perform some small increment of work and then return, resuming where it left off when next invoked. An increment of work in this process can be as little as scanning one stack location.
It is a further object of the preferred embodiment of the present invention that when the stack scanner reaches the last call frame for a stack, there are two cases to be considered. If the stack being scanned is not the current stack, then proceed as for any other call frame. Otherwise, when the stack being scanned is the current stack, the call frame should be treated as if it were partially scanned and then reactivated; that is, it should be processed in the same manner as would be done by the unwind routine.
It is also an object of the invention to integrate the incremental scan of the stacks into the mark phase of a collector.
Finally, although the method and system described herein were developed as part of a treadmill collector, it does not rely on details of that collector. This method can be applied to, for example, a Mark and Sweep collector, an indirection-based collector, or a replicating collector known to one of skill in the art.
REFERENCES:
patent: 4797810 (1989-01-01), McEntee et al.
patent: 5392432 (1995-02-01), Engelstad et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 6055612 (2000-04-01
iRobot Corporation
Jung David
Testa Hurwitz & Thibeault LLP
LandOfFree
Method and system for incremental stack scanning 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 incremental stack scanning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for incremental stack scanning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213786