JPH04148350A - Cell management method in storage devices - Google Patents

Abstract

PURPOSE:To quicken both a data access processing and a reconstructing processing of the tree structure in a garbage collection by separating inter-cell pointers into 2 series, into pointer for managing area assignment and for constructing the tree structure. CONSTITUTION:Pointer information 1a for managing the assignment of a storage area 2, and pointer information 1b for constructing the tree structure is duplexed for each cell. The garbage collection processing divides the area of valid cell and an invalid cell by using the pointer information 1a for managing the assignment of the storage area 2, and then retrieves the pointer information 1a for constructing the tree structure in order to reconstruct the tree structure. Thus, the cell of the tree structure which easily performs access of the data having the tree structure can be obtained, and the processing time of the garbage collection can be shortened.

Description

[Detailed Description of the Invention] [Summary] A cell management method for an area in a computer storage device A cell management system that has tree-structured cells that facilitate access to tree-structured data and that can shorten garbage collection processing time. The purpose is to provide a method.

Pointer information for @ll side allocation management and pointer information for constructing a tree structure are provided in each cell multiple times, so that when multiple cells with a tree structure are assigned to a request source, the multiple cells that are assigned once are linked to a chain. In addition to setting pointer information for area allocation management for each cell, link relationships between cells on the tree structure are set in the pointer information for building the tree structure, and empty invalid cells that are scattered across the storage area are aggregated. When carrying out processing, first, each valid cell that has been allocated is copied to another storage area according to a chain based on pointer information for area allocation management, and then the tree structure within the valid cell in the original storage area is copied. The system is configured to search for valid cells in the copy destination storage area that have the same pointer information as the pointer information for construction, and update the pointer information for tree structure construction.

[Industrial application field]

The present invention relates to a cell management method for an area in a computer storage device, and particularly to a cell management method using a tree structure and a garbage collection processing method.

[Prior Art] In multiple programming processing, when a program makes a request to acquire an area, empty invalid cells are allocated as a contiguous area from the divided storage area, and when the cells are returned from the program that has finished processing, the process is performed again. Manage it as an invalid cell and make it reusable.

FIG. 7 shows a cell structure, and the management chain area has a management chain area and a data area.

Two pointers are set: an R (right) chain and an L (left) chain. The group of invalid cells and the group of 9 allocated valid cells are linked by pointers and connected in a chain.

However, as the operation of a computer progresses, invalid cells become scattered in the storage area.

Since the size of the area requested by each program varies, it becomes gradually impossible to allocate the newly requested area with only consecutive invalid cells, and it becomes impossible to allocate the newly requested area only with consecutive invalid cells, so it becomes impossible to allocate the newly requested area with only consecutive invalid cells, and it becomes impossible to allocate the newly requested area with only consecutive invalid cells. It will start assigning things connected to .

FIG. 8 shows an example of area allocation. As shown in the figure, the valid cell areas assigned to each of programs A and B are composed of chains of a plurality of cells located at discontinuous positions.

However, a region consisting of such discontinuous cells.

When accessing continuous data, it is necessary to follow links between cells, which results in a time-consuming access and a problem of slowing down computer processing speed.

Therefore, at a certain stage, a process is performed to consolidate the invalid cells that are scattered in one place. This process is called garbage collection. In this case, processing is performed to rearrange one valid cell that has been allocated. FIG. 9 shows the state as a result of performing garbage collection processing on the state of the storage device shown in FIG.

As shown in the figure, the invalid cells and valid cells are rearranged so that they form continuous areas.

This is because relocated cells have different addresses.

The pointer is replaced.

[Problems to be Solved by the Invention] In the conventional cell management system described above, chains of cells are linked one-dimensionally. However, some data has a two-dimensional tree structure, and while conventional cell management methods can efficiently access one data array direction, cell chains cannot be accessed in other data array directions. In this case, it is necessary to perform access between discrete cells, and the access efficiency is significantly reduced. In order to enable efficient access to data that has a tree structure, it is possible to duplicate the chain, but in this case, the process of replacing pointers during garbage collection becomes complicated.

There was a problem that the processing time became long.

SUMMARY OF THE INVENTION An object of the present invention is to provide a cell management system that has tree-structured cells that facilitate access to tree-structured data and that can shorten garbage collection processing time.

[Means for Solving the R Problem] The present invention provides each cell with dual pointer information for storage area allocation management and pointer information for tree structure construction, and garbage collection processing is performed for storage area allocation management. The system uses pointer information to classify valid and invalid cell areas, and then searches for pointer information for tree structure construction to reconstruct the tree structure.

FIG. 1 is a diagram explaining the principle of the present invention.

1 is a cell structure according to the present invention, of which 1a is:
Pointer information for area allocation management to form a chain of valid cells similar to that of the conventional cell management method, l
b is pointer information for constructing a tree structure for describing a tree structure between cells, and lc is a data section used for data storage.

2 is a storage area divided into cells. The numbers in the figure indicate cell numbers, the numbers with O indicate the numbers of valid cells to which areas have been allocated, and the arrows between cells are links of chains set by the area allocation management pointer information 1a of each cell. is exemplified.

3 is an example of a tree structure of cells, and is shown corresponding to valid cells illustrated in storage area 2. FIG.

Links between cells are hierarchically set using pointer information for constructing a tree structure of each cell.

4 is a valid cell copying process in garbage collection, in which valid cells are read out by following the chain created by the area allocation management pointer information 1a on the storage area 2, and are sequentially filled in another area and copied. At this time, the area allocation management pointer information 1a is updated to correspond to the new cell position.

Reference numeral 5 indicates a storage area for the state as a result of performing the effective cell copying process 4. Valid cell ■ of each storage area 2.

■, ■, ■, ■, 0 are rearranged by 1 above, ■
Indicated by '1■', ■', ■', ■', @'.

Arrows indicate links based on updated area allocation management pointer information.

6 is a tree structure construction pointer information update process in the Garheji collection, and for each valid cell relocated to the storage area 5, the tree structure is linked using the tree structure construction pointer information of the valid cell of the copy source. Accordingly, a valid cell at the copy destination is searched for, and an update process is performed to replace the tree structure construction pointer information of the valid cell at the copy destination in the corresponding link relationship so as to correspond to the new position of the copy destination.

7 is the updated tree structure represented by the tree structure construction pointer information 1b updated for each rearranged valid cell.

[Operation] The operation of the garbage collector processing according to the method of the present invention will be explained using the example of the tree structure shown in FIG.

(1) After copying the valid cell from the storage area 2 to the storage area 5 by the valid cell copying process 4, copy the valid cell having the same pointer information as the tree structure construction pointer information of the valid cell ■ of the starting point A to the storage area 5. Search among valid cells.

(2) Set the pointer of the starting point B to the address of the valid cell ■' in the search result.

(3) In storage area 2, refer to the valid cell ■ at point 0 linked downward by the vertical direction (vertical direction) pointer included in the pointer information for tree structure construction of the valid cell ■ at point A, and create the tree structure. The storage area 5 is searched for a cell having the same pointer information as the construction pointer information.

(4) Valid cell ■′ and valid cell ■′ at point D in search results
The pointer information for constructing a tree structure in the vertical direction is updated to correspond to each new address.

Using the above method, the correspondence in the tree structure between the valid cells in storage area 2 and the valid cells in storage area 5 is sequentially determined based on the pointer information for constructing the tree structure in the vertical and horizontal directions, and each The tree structure construction pointer information is updated, and the tree structure is rebuilt between valid cells in the storage area 5.

〔Example〕

FIG. 2 shows an example of the cell structure 1 in FIG.

The illustrated cell structure 1 has a total of six pointers.

Two of them are the right chain and left chain pointers included in the area allocation management pointer information 1a, and the remaining four are the bottom pointer, top pointer, right chain, and left chain pointers included in the tree structure construction pointer information. are each pointer.

The functions of these pointers are explained in detail with reference to FIGS. 3 and 4.

Figure 3 is an example of a tree structure, showing a three-level tree structure consisting of cells 1 to 5. Figure 4 shows the content of pointer information in each cell based on the example of the tree structure in Figure 3. show, third
The structure of each cell shown in the figure corresponds to the cell structure shown in FIG.

In FIG. 3, the cells from cell 1 to cell 5 are looped in numerical order for area allocation management using the right chain and left chain pointers of area allocation management pointer information 1a, as shown in FIG. linked in both directions.

Further, the address of the starting cell of the highest layer O and the number of cells are registered in a cell management block of control information managed by a cell management program (not shown). In this case, the address of the starting cell is the address of cell l,
The number of cells is 05゛.

In the tree structure of FIG. 3, the two hierarchies are between cell 1 and cell 2 and between cell 2 and cell 4.

The lower pointer and upper pointer in the tree structure construction pointer information lb in Figure 2 are linked in both directions, and between cells 2 and 3 and between cells 4 and 5 in the same hierarchy.
In between, the pointer information for constructing the tree structure shown in Figure 2 is shown.
It is bidirectionally linked by the two pointers in b, the right chain and the left chain. However, even between the layers, there are no direct links between cells 1 and 3 and between cells 2 and 5.

In this way, pointer information within the cell as shown in FIG. 4 is set.

Next, the flow of garbage collection processing according to an embodiment of the present invention will be explained with reference to FIGS. 5 and 6. FIG. 5 shows the overall flow of garbage collection processing, and FIG. 6 (A)
Figure 6 (B) shows the detailed flow of the effective cell copying process therein.
) is the detailed flow of the up/down pointer reconstruction process, and Figure 6 (C
) is a detailed flow of horizontal chain reconstruction processing.

In the overall flowchart of FIG. 5, all valid cells in a storage area are first copied to another storage area in step (3).

Next, use ■ to focus on layer 0, use ■ to check whether there is an element in the lower layer, and if there is an element below, use @ to perform up/down pointer reconstruction processing, use ■ to point to an element further down, and use Press to set the base point of the horizontal chain, press ■ to increase the number of layers by 1, and return to ■. The base point set in ■ is used to judge whether all the horizontal chains have been traced because the horizontal chains are loop-like bidirectional links. There is also one in each layer.

On the other hand, if there is no element further down in ■, check if there is a horizontal element in ■, and if there is an element next to it, check whether it matches the set base point because it is a horizontal chain pointer value, - If not defeated, perform the horizontal chain reconstruction process (■), point to the horizontal element with 0, and return to @.

On the other hand, if there is no horizontal element in ■, and if the pointer value of the horizontal chain matches the base point in ■, and the hierarchy is not 0 in ■, point to the upper element, and change the hierarchy value to − in ■.
1 and return to ■. Then, when the hierarchy value becomes 0 in ■, the process ends.

Next, a detailed flow of the valid cell copying process shown in FIG. 6(A) will be explained.

First, in step 2-1, point to the first valid cell using the starting address of the effective cell management block.0 Next, in step 2-2, the number of effective cells is set in the counter CNT.

(2) Check whether CNT=O or not in -3, and if CNT is a value other than O, (2) Copy the valid cell to another area in -4.

(2) Advance the valid cell pointer at -5 and perform CNT4-1. - Return to -3 and end when CNT-0.

Next, a detailed flow of the up/down pointer reconstruction process shown in FIG. 6(B) will be explained.

Use @-1 to point to the starting cell of the wI area of the copy destination.

In ■-2 to ■-4, search for a cell that has the same up/down pointer and horizontal chain pointer as the target cell, and when the relevant cell is found, set the up/down pointer between that cell and the target cell, finish.

Next, the horizontal chain reconstruction process shown in FIG. 6(C) will be explained.

- Point to the starting cell of the copy destination area with -1.

In (2)-2 and (2)-3, a cell having the same horizontal chain pointer as the target cell is searched for, and when the relevant cell is found, a horizontal chain pointer is set between that cell and the target.

〔Effect of the invention〕

According to the present invention, since the pointers between cells are divided into two series, one for area allocation management and one for tree structure construction, area management is easy.

It is possible to speed up data access processing and tree structure reconstruction processing in garbage collection.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram of the principle of the present invention, FIG. 2 is an explanatory diagram of a cell structure according to an embodiment of the present invention, FIG. 3 is an explanatory diagram of an example of a tree structure according to an embodiment of the present invention, and FIG. 4 is an explanatory diagram of an example of a tree structure according to an embodiment of the present invention. FIG. 5 is an overall flowchart of the process according to the embodiment of the present invention, FIG. 6 is a detailed flowchart of the process according to the embodiment of the present invention, and FIG. 7 is a diagram of the cell structure according to the conventional method. FIG. 8 is an explanatory diagram of an example of cell allocation according to the conventional method, and FIG. 9 is an explanatory diagram of the garbage collection processing result according to the conventional method. In Figure 1. I: Cell structure. 2: Storage area 3: Example of tree structure. 4: Valid cell copy processing. 5: Copy destination storage area 6: Tree structure construction pointer information update process. 7: Tree structure after update. Example of cell configuration according to this blindness example.

Claims (1)

[Scope of Claims] In a storage device in which a storage area is divided into a plurality of cells and area allocation is performed on a cell-by-cell basis, each cell is provided with pointer information for area allocation management and pointer information for constructing a tree structure multiplexed, When allocating multiple cells with a tree structure to a request source, the area allocation management pointer information for each cell is set so that the multiple allocated cells are linked to a chain, and the link relationship between cells on the tree structure is set. is set in the pointer information for tree structure construction, and when performing the process of aggregating empty invalid cells that are scattered in the storage area, first, the allocated valid cells are set according to the chain based on the pointer information for area allocation management. Copy each valid cell to another storage area, then trace the valid cells in the original storage area sequentially according to the tree structure construction pointer information, and use the same pointer information as the tree structure construction pointer information in the target valid cell. A storage device characterized in that a process of searching for a valid cell in a storage area of a copy destination, and updating pointer information for constructing a tree structure when a corresponding valid cell is found, is repeated for all links in the tree structure. Cell management method in.