Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-01-03
2003-09-09
McLean-Mayo, Kimberly N. (Department: 2187)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06618738
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technology for managing memory resources, and in particular, it relates to a technology for managing memory resources used by the execution of an application program and executing a garbage collection process for collecting free memory areas of the memory resources.
2. Description of the Related Art
As a method for efficiently managing limited memory resources without increasing a programmer's load in a processing system, there is a method called “garbage collection” (hereinafter called “GC”). The GC process specifies free data in a memory and collects a memory area used by the data to use the area for another piece of data.
In the description of GC, a memory resource to be managed is called a “heap”. The heap is composed of units of data strings called cells (or objects). Each cell can include pointers pointing to another cell and other data, but excluding pointers.
Outside the heap there is an aggregate of the pointers, such as a register, a stack, etc., to which an application program executed on the processing system can directly refer, and this aggregate is called a root. In the heap, there are both a cell that can be directly or indirectly accessed by a pointer reference from this root and a cell that cannot be accessed in such a way. The former cell can be accessed by the execution of an application program and is called a “live cell”, “surviving cell”, etc. The latter cell cannot be accessed by the execution of an application program and is called a “dead cell”, etc.
The GC judges whether each cell is live or dead in a heap, regards dead cells as “garbage” and collects the “garbage” as an area that can be used by another piece of data.
The GC can be classified into several categories based on the principle of an adopted algorithm. A variety of GC methods are described in detail in “Feature: The Basics of Garbage Collection and its Recent Trend”, Information Processing, Vol.35, No.11, Information Processing Society of Japan (1994). Here, a parallel type GC, which is one of the methods, is described.
Processes in which GC is performed in the processing system are largely classified into two categories: a process executed by an application program and a process executed by GC. The former is called a mutator and the latter is called a collector.
According to the basic algorithm of GC, in order to prevent the change in the life/death status of a cell by a mutator, the mutator is temporarily stopped while a collector is executed by the processing system, and the collectors are collectively executed. However, basically the collector must extract all cells that can be reached by sequentially tracing pointers from a root as live cells. In this case, the process load becomes fairly large depending on the amount of live cells. Therefore, the interruption time of a process on the mutator side cannot be neglected.
In order to reduce the execution interruption time of a mutator due to GC, a variety of GC algorithms have been proposed.
Conventionally, a classic GC called collective type GC was used in which the execution of processes by mutators is stopped and a collector collectively collects memories. Since this method stopped a mutator for a long time, the response performance of an application program was degraded, which is a problem.
Then, a method that prevents the interruption for a long time of a mutator by distributing processes by collectors among processes by mutators in terms of time instead of collectively executing GCs and by executing both the processes in parallel one part at a time, was proposed. This is called parallel type GC.
Here, The summaries of both an on-the-fly GC proposed by Mr. Dijikstra et al and a snapshot GC proposed by Mr. Yuasa of the parallel type GCs are described. For detailed information about these GCs, see E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, “On-the-Fly Garbage Collection: An Exercise in Cooperation”, Communications of the ACM, Vol.21, No.11, pp.966-975 (1978); T. Yuasa, “Real-Time Garbage Collection on General-Purpose Machine”, Journal of Systems and Software, Vol.11, pp.181-198 (1990); and T. Yuasa, “Feature: The Basics of Garbage Collection and its Recent Trend, 3. Real-Time Garbage Collection”, Information Processing, Vol.35, No.11, pp.1066-1013, Information Processing Society of Japan (1994).
The on-the-fly GC is obtained by improving a mark and sweep method, which is one of the collective type GC basic algorithms. According to the mark and sweep method, one cycle of GC is divided into two phases, a mark phase and a sweep phase, and is executed.
In the mark phase, first, a root is secured (this process is often specifically called a “root-insertion phase”). Then, a process for marking all reached cells while sequentially tracing pointers from the root, is executed.
Then, as a sweep phase, the entire heap is scanned and unmarked cells are collected. Simultaneously, the marks of marked cells are erased in preparation for a subsequent GC. After that, a mark phase (including a root-insertion phase) and a sweep phase are alternately repeated. This is a mark and sweep type GC.
According to the on-the-fly GC, a collector executes a mark and sweep type GC in parallel with a mutator process. In this case, the replacement of pointers by a mutator often occurs in the midst of a mark phase of GC by a collector. In this case, although a dead cell is made a live cell by the replacement of pointers, the live cell is often not marked in a mark phase. Then, this live cell is collected as “garbage” in a subsequent sweep phase, which is another problem. Therefore, according to the on-the-fly GC, each cell in the heap is marked with one of three colors: black, dark black and white. The cell-marking procedure by the on-the-fly GC is described with reference to FIG.
1
.
Before the collector starts on-the-fly GC, all cells in a heap are marked white. The collector, first, refers to a root and turns a cell mark directly pointed to by a pointer of this root dark black. (A) in
FIG. 1
shows that the marks of cells A and B directly pointed to by the pointer of the root are turned dark black. In FIG.
1
and
FIG. 2
referred to later, dark black marks attached to cells are indicated with diagonal lines.
A dark black cell mark indicates that a cell must be marked black again later. Actually, a cell is not marked dark black, but the collector pushes a pointer pointing to the cell to a stack provided for GC (GC stack) (this process is called a “root insertion process”, etc.).
Then, the collector turns the dark black cell mark black. In other words, the pointer is popped from the GC stack and the mark of the cell pointed to by the pointer is turned black.
Furthermore, if the black-marked cell stores another pointer pointing to another cell, the collector turns the marks of all cells pointed to by all pointers stored in the cell dark black. In this way, all pointers pointing to other cells stored in the black-marked cell are pushed to the GC stack.(B) in
FIG. 1
shows that the dark black mark of cell A shown in (A) is turned black and further the white marks of cells C and D pointed to by the pointers stored in cell A are turned dark black.
According to the on-the-fly GC, a collector process performs the marking described above and in addition, a mutator process performs another marking. If either the root or one of cells in the heap stores a pointer and if a cell pointed to by a stored pointer is marked white, a mutator turn the white mark of the cell pointed to by the pointer dark black. (C) in
FIG. 1
shows that as a result of a mutator process, the pointer of the root that points to cell B in (A) is modified to point to cell D and the pointer stored in cell A that points to cell D is modified to point to cell B. (C) in
FIG. 1
shows that as a result of these modifications, of the marks of cells B and D that are pointed to by the pointer of the root and the new pointer stored in cell A, respectively, the white mark of cell D i
Maeda Munenori
Ozawa Toshihiro
Fujitsu Limited
McLean-Mayo Kimberly N.
Staas & Halsey , LLP
LandOfFree
Device and method for managing memory resources by using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for managing memory resources by using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for managing memory resources by using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3043524