Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-01-29
2004-07-20
Breene, John (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06766336
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a garbage collection apparatus for performing scavenging and compaction on cells using trays.
2. Description of the Prior Art
An application uses a heap for performing dynamic memory allocation. The heap referred to as unused cells. The application reserves a number of cells required for an application process as a cell block.
FIG. 28
shows an example of a heap. In the drawing, the heap includes a root cell block, cell blocks
1
to
5
, and an unused cell area. The unused cell area is a collection of unused cells that have not been allocated.
When reserving memory the application forms reference relationships between cell blocks so that a reserved cell block can be referenced by other cell blocks. In
FIG. 28
such references are shown by polygonal lines. A cell block
4
is referenced by a root cell block, a cell block
2
by the cell block
4
, and a cell block
5
by the cell block
2
. The root cell block is a cell block that is the start of the reference relationship.
To explain in more detail, the application holds a valid reference showing a start cell of the reserved cell block in a cell included in another cell block. A valid reference is a cell address or similar. To give one example shown in
FIG. 28
, the application holds a valid reference
3
showing a start cell in a cell block
2
.
However, cell blocks that cannot be traced (reached) from the root cell block may be generated when the application is executing processing for a particular process. Such cell blocks are said to be unreachable (dead). Processing performed to free unreachable cell blocks and collect the freed cell blocks together to form an unused cell area in which cell blocks are once more capable of being used is known as garbage collection. A device for executing this processing is known as a garbage collector.
The garbage collector performs scavenging (relocating unreachable objects) and compaction (also known as compactifying). In
FIG. 28
, the garbage collector performs scavenging to return unreachable cell blocks
1
and
3
to an unused state, and then performs compaction to gather up the plurality of unused cell blocks into one unused cell area. When this processing is performed, the garbage collector updates valid references held by cells in order to maintain reference relationships between cell blocks.
Various refinements have been made to the algorithm used by the garbage collector. The following is an explanation of three garbage collectors in the prior art.
FIG. 29
shows a structure of a heap in a first prior art. In the drawing, the heap includes cells, and reference flags corresponding to each cell. The garbage collector performs scavenging as follows:
(1) sets ‘in use’ flags indicating whether cell blocks are in use or not at 0 (here, an ‘in use’ flag uses 1 bit from each cell block);
(2) reads a valid reference held in a root cell block;
(3) determines that a cell block at a location indicated by the read valid reference is in use, and sets the ‘in use’ flag for the cell block at 1;
(4) refers successively to each of the reference flags for the cell block determined to be in use, and retrieves all of the reference flags set at 1; and
(5) reads valid references held in cells corresponding to each of the retrieved references. The garbage collector repeats the processing of (3) to (5) for all of the cell blocks that are reachable from the root cell block.
Following this, the garbage collector performs the following compaction:
(1) calculates a reference value for a start cell after compaction for all cell blocks with an ‘in use’ flag set at 1;
(2) rewrites reference values for all cells that have an ‘in use’ flag and a reference flag set at 1 with the reference values calculated in (1); and
(3) shifts cell blocks with an ‘in use’ flag set at 1 to the reference locations calculated in (1).
FIG. 30
shows a heap memory for a second prior art example. As shown in the drawing, the heaps includes reference flags, cells, and trays. A cell block holds a valid handle indicating a tray, and the tray holds a valid reference indicating a start cell in a cell block. Reference relationships between cell blocks are indicated indirectly by using trays.
For example, a cell block
4
holds a valid handle
1
, which indicates a tray with a valid handle
1
. The tray with the valid handle
1
holds a valid reference
3
, which indicates a cell block
2
in which the valid reference
3
is located. Thus, cell block
3
can reference cell block
2
.
The garbage collector in the second prior art performs the following scavenging:
(1) specifies, via trays, cell blocks that are reachable from the root cell block, and sets the ‘in use’ flags for these cell blocks at 1 (this processing is similar to that in the first prior art);
(2) changes valid references for trays which are not referenced by any cell block to NULL references.
As one example of (2), the garbage collector updates the content of a tray with a valid handle
0
and a tray with a valid handle
2
that are not referenced by any cell block to a NULL reference. A NULL reference indicates that a tray is unused. Thus, cell blocks
1
and
3
, whose valid references
1
and
6
were held by the trays with the valid handles
0
and
2
prior to updating, are freed by the garbage collector to form an unused cell area.
Following this, the garbage collector in the second prior art performs compaction as follows:
(1) calculates a reference value for a start cell after compaction for all cell blocks with an ‘in use’ flag set at 1;
(2) overwrites trays holding a valid reference with the reference values calculated in (1); and
(3) shifts cell blocks with ‘in use’ flags set at 1 to a reference location calculated in (1).
In the example shown in
FIG. 30
, cell blocks
4
and
5
are shifted forward by an amount corresponding to the size of the freed cell blocks
1
and
3
. Here, the garbage collector updates the content of the trays so as to maintain references from a root cell block to a cell block
4
, and the cell block
4
to a cell block
2
and a cell block
5
.
FIG. 31
shows a heap for a third prior art. The third prior art is one example of what is known as a conservative garbage collector. Such technology is disclosed in more detail in
Garbage Collection in an Uncooperative Environment
(Hans-Juergen Boehm and Mark Weiser,
Software Practice and Experience
Vol. 18, pub. September 1988, pages 807 to 820).
Here, the heap holds pointers (references) to cell blocks at a start of each cell block. The garbage collector in the third prior art performs the following scavenging:
(1) sets ‘in use’ flags indicating whether cell blocks are in use at 0;
(2) reads a valid reference held in the root cell block;
(3) determines whether a cell block at a location indicated by the read valid reference is in use;
(4) reads content at a start location of a cell block determined to be in use, and makes an assumption as to whether the read content is a reference value.
The garbage collector repeats the above processing (3) to (4) for all cell blocks that are reachable from the root cell block.
In
FIG. 31
, the polygonal lines show reference relationships between cell blocks.
The garbage collector in the third prior art makes assumptions as to whether cells contain numerical values or references, and performs garbage collection in accordance with the results of these assumptions. However, the garbage collector may mistakenly assume that a numerical value is a reference. For example, in
FIG. 31
, the garbage collector mistakenly assumes that a numerical value 6 is a valid reference. The curved line in the drawing shows the referencing that is performed based on this mistaken assumption. Since the garbage collector mistakenly assumes the numerical value 6 to be a valid handle
6
, a mistaken reference from cell block
2
to cell block
3
is produced.
The garbage collector in the third prior art can perform scavenging, but not compaction. The reason for this is that if compaction is
Breene John
Matsushita Electric Industrial Co. Ltd
To Baoquoc N
LandOfFree
Garbage collection apparatus and a garbage collection method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Garbage collection apparatus and a garbage collection method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Garbage collection apparatus and a garbage collection method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225091