JPS6367656A - Processing system for data storing area control - Google Patents

Abstract

PURPOSE:To decrease the replacement frequency of idle area chains and to contrive to increase the chain scanning speed by chaining the areas larger than the fixed length to the use them as subjects for search of idle areas and replacing only the total idle areas in case the idle area is smaller than the fixed length owing to reduction of a desired area under use, etc. CONSTITUTION:When a processing request for area control requires the area return processing, an area return processing means is started. This processing means connects the returned area to an idle area chain as long as said area is larger than the fixed area length. While just the return area length is added to the total length of idle areas in a control area to complete processing if said returned area is smaller than the fixed area length. When the processing request requires acquisition of areas, an area acquiring means selects an idle area out of a chain of only those idle areas larger than the fixed area length formed as mentioned above through the same processing as conventional. Thus the chain processing frequency is decreased in the area return processing and furthermore the length of the chain that is scanned in the area acquisition processing is decreased. Then the area control processing time is reduced.

Description

[Detailed Description of the Invention] [Summary] This is a management processing method that improves the processing efficiency of storage area management of a storage device.

All free areas of various sizes are managed by chaining them together. , when the length is less than the above-described certain length, only the total amount of free space is updated.

This method reduces the update frequency of the free space chain,
Chain scanning can be sped up.

[Industrial application field]

The present invention relates to a storage area management processing method for a storage device such as a computer system.

In a storage device or the like that stores database data, some kind of area management processing is generally required to deal with increases and decreases in free space due to increases and decreases in data length due to storage of new data and updates to stored data.

[Conventional technology]

FIG. 2 is a block diagram showing an example of the configuration of the computer.

The processing device 1 executes a program loaded into the main storage device 2, and manages a database stored in a storage device 3, which is constituted by, for example, a magnetic disk storage device.

The storage area of the storage device 3 is managed by being divided into storage blocks called pages, each having a certain area length (for example, 4096 bytes).

As illustrated in FIG. 3 (al), each page 10 is divided into sections a, b,
c, etc., unallocated free areas (white areas in the figure) α, β, T, etc., and a predetermined control information area.

For each page 10, for example, the entire area except for the control information area is set as one free area, and the area is divided into each data to be stored sequentially from the beginning, and each data area is allocated without any gaps, and then It is possible to leave continuous free space.

However, after that, due to an increase/decrease in the data length due to updating of the stored data, or deletion, etc., empty areas divided into relatively small sizes become scattered.

Therefore, as shown in FIG. 3 (al), a pointer indicated by, for example, an intra-page displacement address is held in the control area 11 provided in the control information area, and points to the beginning of one free area that is the beginning of the chain.

For example, at the beginning of each free area, a number of bytes indicating the length of the free area and a next area pointer pointing to the start of the next free area are stored, and all free areas within page 10 are connected. Configure a chain.

The area at the end of the chain can be identified, for example, by setting the next area pointer to a specific value (for example, a value consisting of all 1 bits).

Further, the control area 12 holds the total area length of all free areas, and the control area 13 holds the number of bytes indicating the maximum area length of the largest free area.

Regarding the allocated data areas, the address and area length of each area are indicated by the pointer and byte number display for each data area held in the control information area 14.

When the required area length of the storage area increases or decreases due to data updates, when new data is added, when stored data is deleted, etc., this is generated from the program that performed each process such as update. In response to the area management request, area management processing whose flow is shown in FIG. 4 is executed.

In FIG. 4, in processing step 20, the processing is classified depending on whether the request is a request to acquire a storage area or a request to return a free area.

In the case of an area acquisition request, in processing step 21,
Select the page on which to search for areas. In this selection, the maximum area length of the control area 13 of each page 10 is compared with the requested 5-page area length, and one page having a free area with a maximum area length exceeding the requested value is determined. Note that if this request is due to an increase in data length due to an update of stored data, the page storing the original data will be selected preferentially.

If there is a page that satisfies the required conditions, in processing step 22, the chain of free areas starting from the pointer in the control area 11 is traced as described above, and the area length of each free area in the chain is compared with the requested area length. By doing so, one of the free areas having a size equal to or larger than the requested area length is selected.

In processing step 23, the chain pointer is updated so that the selected free area is removed from the chain, and in processing step 24, the request source is notified of the address, etc. of the selected free area, so that the area can be used. do.

As described above, the state of the chain has changed, so in processing step 25, the area length of the area just allocated is compared with the value of control area 13, and if they match, the entire free area of the chain is scanned in processing step 26. , find the maximum region length, and set that value as the maximum value of the control region 13.

Next, in processing step 27, the size of the area that has just been allocated is subtracted from the total value of the free area length of the control area 12 to update the total value, and the process ends.

If there is no suitable page in processing step 21, the total value of the control area 12 of each page is compared with the requested length in processing step 28, and the total value of the free area length satisfies the requested size. Find a page.

If there is a required page, in processing step 29, a known so-called garbage collection process is executed, and the allocated data area of the page is packed, for example, toward the beginning, and the free space is collected at the back, thereby creating a large free space. An area is created, and the process proceeds to step 24, where the free area is handed over to the request source.

In processing step 28, if there is no page that satisfies the required conditions, the request cannot be satisfied within the range of existing pages, so this processing is ended and appropriate abnormality processing is started.

In the case of an area return request, the process proceeds from process step 20 to process step 30, where predetermined free space information as described above is written in the area passed from the request source, and process step 31
, connect to the free space chain of the page in that region.

Connection to the chain is performed, for example, by setting the value of the pointer in the control area 11 to the next area pointer in the free area to be connected, and by setting in the control area 11 the address of the area to be connected.

Next, in a processing step 32, the area length of the returned area is compared with the maximum value held in the control area 13, and if the returned area is larger, the area length of the returned area is changed to the control area 13 in a processing step 33. to update the maximum value.

Also, in processing step 34, depending on the area length of the return area,
The total free area length held in the control area 12 is increased and the process ends.

[Problem that the invention seeks to solve]

As explained above, in the area management process, in the case of an area acquisition and return request, the free area chain is updated every time, and when scanning the free area for area acquisition,
Since it is necessary to trace a relatively long chain connecting all the free areas of the page, the overhead of area management becomes relatively large, and an improvement has been desired.

[Means for solving problems]

FIG. 1 is a process flowchart showing the configuration of the present invention.

In the figure, reference numeral 40 indicates processing constituting an area return processing means, and reference numeral 41 indicates processing constituting an area acquisition processing means.

[For production]

As in the conventional case, when there is a processing request for area management and the request is for area return processing, the area return processing means 40 is activated from processing step 20.

When the returned area is larger than a certain area length, the area return processing means 40 connects the area to a chain of free areas, and when the area is smaller than that, it simply connects the area to the control area 1.
The process is completed by simply adding the return area length to the total free area length in step 2.

When the request is for area acquisition, the area acquisition means 41 performs the same process as the conventional one, except that it selects an empty area from a chain of only empty areas larger than a certain area length configured as described above.

With the above method, the number of chains to be processed in the area return process is reduced, and the length of the chain scanned in the area acquisition process is shortened, so that the processing time for area management can be reduced.

〔Example〕

In FIG. 1, in processing step 2o, the processing is classified depending on whether the request is a request to acquire a storage area or a request to return a free area.

In the case of an area return request, the process proceeds from process step 2o to process step 42 of the area return processing means 40, where free area information is written in the area passed from the request source in the same manner as described above.

Next, in processing step 43, the area length of the return area is
A comparison is made to determine whether the area length is greater than a certain area length defined by this system.

The fixed area length is, for example, the average length of the data constituting this database, etc., and is specified in the area management program as a system control constant.

If the return area is larger than a certain length, process step 4
Step 4 connects the return area to the free area chain. The connection process to the chain may be the same as before, for example, control area 1
Insert the return area at the beginning of the chain pointed to by pointer 1.

Thereafter, in processing steps 45 and 46, the value of the maximum area length held by the control area 13 is updated if necessary, as in the past, and in processing step 47, the total free area length value of the control area 12 is increased. Finish processing.

If the size of the return area is less than a certain length in processing step 43, the connection process to the above chain is not performed,
The process immediately proceeds to step 47, where only the control area 12 is updated, and the process ends.

An example of a chain configured in this way is shown in Figure 3 (
'b).

FIG. 3('b) is an example of a page with the same free space state as in FIG. 3(a) explained above, but according to the present invention, relatively small free spaces α and γ are not chained and Only regions β and δ constitute a chain. In addition, control area 1
The total value of the free area of 2 and the value of the maximum area length of the control area 13 are the same in (a) and (bl).

In the case of an area acquisition request, the area acquisition processing means 41 performs processing similar to the conventional process through processing steps 21 to 27.

However, since the chain scanned in processing step 22 is a chain constructed by selecting only free areas larger than a certain length as described above, the chain to be scanned is relatively short and does not cover areas exceeding the required area length. Since it is easy to reach, it can be processed in a short time.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, in managing an area for storing data such as a database of a computer system, the overhead time of management processing in acquiring and returning data storage area is reduced. It has a significant industrial effect of improving the processing efficiency.

[Brief explanation of drawings]

Figure 1 is a flowchart of processing showing the configuration of the present invention, Figure 2 is a block diagram of an example configuration of a computer system, Figure 3 is a diagram explaining the state of a page, and Figure 4 is a flowchart of conventional processing. . In the figure, 1 is a processing unit, 2 is a main storage device, 3 is a storage device, 10 is a page, 11.12.13 is a control area,
14 is control information, 20 to 34, 42 to 47 are processing steps, 40 is an area return processing means, and 41 is an area acquisition processing means. Flowchart of a process showing one component of the present invention. FIG. 1 A block diagram of a configuration example of a computer system. Figure 2: Diagram explaining page status Figure 4: Flowchart of conventional processing

Claims (1)

[Claims] In the management of free space for storing data in a predetermined storage block of a storage device, means for calculating and holding the total area length of all free space within the storage block ( 40) and means (40) for configuring a chain by connecting the free areas exceeding a predetermined area length in the storage block, and configuring the chain when storing data of a required length. An area having an area length equal to or greater than the required length is selected from among the areas to be stored (41), and if an empty area less than the predetermined area length occurs, only the total value is updated (40). A data storage area management processing method characterized by being configured as follows.