JP2989608B2 - Cell pool management device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Summary] From a cell pool having one or more cell pages each having a storage area of a predetermined unit, one or more cells of a smaller unit are selected in response to a storage area acquisition request from an application program. The present invention relates to a cell pool management device that performs control to release cells to a cell pool in response to allocation and a storage area return request.

Eliminating the overhead due to considering cell pool area degeneration processing (processing to reduce the cell pool itself when free space increases) every time a cell is acquired from the conventional cell pool and the cell is returned to the cell pool, The purpose is to acquire and release cells at high speed.

Therefore, when connecting the empty cells in the cell pool to one chain and allocating the cells to the application program, the required number of cells are cut out from the head of the empty cell chain, and when the application program returns the cells, A means for managing a series of returned cells by linking them to the beginning of an empty cell chain, and at a predetermined time, classifying which cell page an empty cell belongs to and detecting a cell page in which all the empty cells are empty cells A means for performing a cell pool degeneration process by removing the cell page from the cell pool is provided, so that the cell allocation management process and the cell pool degeneration process are separated from each other.

[Industrial applications]

The present invention relates to a cell pool management device that manages a cell pool for allocating and reclaiming a storage area according to a request of an application program.

With the recent spread of computer systems, the amount of data processed by the computer systems has increased, and there is no limit to the improvement in the processing capacity required for the computer systems. Under such circumstances, it is required that the overhead of the operating system generated when allocating and retrieving a storage area based on a request from an application program is as small as possible.

[Problems to be solved by conventional technology and invention]

The management of the cell pool includes opening a cell pool / securing a cell page, allocating a cell (acquiring a cell from an application program), collecting a cell (opening a cell from an application program), expanding a cell pool, and degenerating a cell pool. It consists of five stages of processing.

The cell pool area usually acquires a storage area in units of one page (for example, 4 KB) due to virtual storage control or the like. Thus, a cell pool consists of one or more cell pool pages.

When an application program needs a storage area, it requests an area of a necessary size. Normal,
The size is an arbitrary size in units of 16B to 256B smaller than one page. Therefore, in order to efficiently allocate a storage area in response to a request from an application program, it is necessary to divide a cell pool page into smaller units (cells) and manage the pages in smaller units.

In addition, the application program acquires a cell each time it becomes necessary, and releases the cell when it becomes unnecessary.
Therefore, control for expanding or reducing (reducing) the cell pool in page units according to the situation is required.

FIG. 7 is a diagram for explaining a conventional cell pool management device.

(A) shows the case of cell allocation (acquisition),
(B) shows a case of cell collection (release), and (c) shows a case of cell pool page removal (degeneration). In this example, it is assumed that one cell pool page is composed of five cells.

The figure shows the state of the cell pool at a certain point in time, □ indicates management information of one cell pool page, and ○ indicates an unused cell (empty cell). Therefore, in this figure, a 6-cell page is used, the first page uses 3 cells, and the second page indicates that all the cells are empty cells.

In acquiring cells, it is checked in order from the top cell pool page whether there are a number of empty cells (shown by を 満 た す) satisfying the request of the application program. And examines the next cell pool page and extracts as many as necessary.
reference}. This example shows that two cells have been acquired from the first page and three cells have been acquired from the next page in response to five cell acquisition requests. If the number of empty cells is less than the requested number of cells in the entire cell pool, a cell pool page is added (expansion processing).

When releasing a cell, for example, the management information at the head of each cell is checked to determine which cell pool page each cell to be released (indicated by ◎) belongs to, and a corresponding cell is determined. Release to the pool page {see this figure (b)}.

The above process is repeated for each cell acquisition and release process,
In addition, for example, when there are a certain number or more of cell pool pages in which all cells are empty cells in the cell pool, those cell pool pages are removed and the cell pool itself is reduced {see FIG. processing).

In the above cell acquisition processing, the number of cells requested by the application program must be searched for each cell pool page. In the cell release processing,
It was necessary to check which cell pool page the released cell belongs to and return it to the management of the corresponding cell pool page.

These are due to the fact that the operations of acquiring and releasing each cell are performed in consideration of performing the degeneration process of each cell pool page. Furthermore, when a specific cell is held in a certain application program, the cell pool page is degenerated every time a cell acquisition / release request is generated from the application program, even though the cell is never degenerated. A useless process of executing the process in consideration is performed.

Therefore, there is a problem that an application program that emphasizes performance has a large overhead in the operating system when acquiring and releasing a cell.

An object of the present invention is to allocate a cell from a cell pool of a storage page immediately upon receiving a request from an application program, and reduce the time elapsed due to unnecessary processing.

[Means for solving the problem]

FIG. 1 is a diagram illustrating the principle of the cell pool management device of the present invention. The above problem is solved by a cell pool management device configured as follows.

When connecting all empty cells in the cell pool to one chain and assigning cells to the application program, cut out as many cells as required from the empty cell chain and return them when the application program returns cells. An empty cell management means for managing the connected cells by linking them to an empty cell chain, and at a predetermined time, classifying which cell page each cell of the empty cell chain belongs to, Cell pool degeneration processing means for detecting a certain cell page and removing the cell page from the cell pool.

[Action]

According to the present invention, the empty cell management means connects all the empty cells by one chain, and when there is a cell acquisition request, for example, cuts out from the head of the empty cell chain that has been chained. When a cell release request is issued (see FIG. 1A), only the process of connecting to the beginning of an empty cell chain is performed (see FIG. 1B). Cell acquisition and release processing can be executed.

Then, the cell pool degeneration processing unit executes the degeneration processing at a predetermined time.

In the degeneration processing (see FIG. 1 (c)) at this time, for each cell connected to the empty cell chain, which cell pool page belongs, for example, the control information provided at the head of each cell is determined. It is examined by seeing, etc., and classified by cell pool page {see FIGS. 1 (5) and (6)}. In this classification, the order of returning empty cells to each cell pool page is arbitrary. This is because in the degeneration of the cell pool, it is only a matter of whether or not there is a cell being used in each cell pool page.

Next, for each classified cell pool page, if all cells in the cell pool page are empty cells,
The cell pool page is released, and the remaining empty cells are processed so as to be connected again to the above-mentioned chain {FIG. 1 (7),
See (8).

Therefore, in the cell pool management device according to the present invention, it is not necessary to perform processing in consideration of the degeneration of the cell pool page when acquiring and releasing a cell, so that the processing speed at the time of acquiring and releasing a cell is improved.

The degeneration processing of the cell pool may be performed at an appropriate time such as when the load on the system is reduced. For example, the process is performed in response to a degeneration process designation or the like that is activated by the operating system as needed, or more simply at regular intervals, or at a time when the number of cells in the chain reaches a predetermined number.

〔Example〕

 Hereinafter, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a diagram for explaining the principle of the operation of the cell pool page management apparatus of the present invention. FIG. 1 (a) shows a cell acquisition process, FIG. 1 (b) shows a cell release process, and FIG. The case of the degeneration processing of the cell pool is shown.

FIG. 2 is a diagram showing a cell pool release process according to the present invention, wherein (a1, a2) shows an example of the entire configuration, and (b)
Shows a configuration example of a cell.

FIG. 3 is a diagram showing a process for acquiring a cell according to the present invention, FIG. 4 is a diagram showing a process for releasing a cell according to the present invention, and FIG. 5 is a diagram showing a process for expanding a cell pool according to the present invention. FIG. 6 is a diagram showing a cell pool degeneration process according to the present invention. Note that the same reference numerals indicate the same objects throughout the drawings.

Hereinafter, the cell pool management apparatus of the present invention will be described with reference to FIGS. 2 to 6 while referring to FIG. The process of opening a cell pool, the process of acquiring and releasing a cell pool, the process of expanding a cell pool, and the process of degenerating a cell pool will be described in this order.

(1) Cell pool opening processing: {see FIG. 2} When a user (application program) first requests a storage area, a cell pool management book 1a and a predetermined number are stored as shown in this figure (a1, a2). Area for the cell pool information entry 1b is obtained, a predetermined number of cell page areas (for example, the number specified by the initial value) are obtained, and these are chained. The details are described below.

The following processing is repeated by the number specified by the initial value of the cell pool.

1) A predetermined number of cell page areas are acquired, and their addresses are stored in the cell page pointer of the cell page information entry 1b extracted from the empty cell page information entry pointer of the cell pool management book 1a.

2) Cell 11 is allocated to the cell page according to the cell size, and the cell page information entry is added to the head address.
The address of the cell page pointer of 1b is stored and each cell is chained by the next pointer.

Next, one cell page information entry 1b is chained as a cell page in use as a cell page information entry pointer of the cell pool management book 1a, and another cell page information entry 1b is chained with an empty cell page information entry pointer. Cell size, number of cell pools, cell start address, number of cells in cell page,
The number of remaining cells (total number of cells) and the like are specified or set by default. For example, the cell size is determined by the size of the cell page information entry pointer + the cell size specified by the user.

Then, the address of the cell pool management book 1a is notified to the user (application program) as the "cell pool ID".

The cell 11 created in the cell pool opening process has a size (cell size) requested by the user + an area for degeneration management of the cell pool (cell page information entry pointer: 4 bytes in this example) as shown in FIG. 11a, the area available to the user includes a "next empty cell pointer" for empty cell management.

In the degeneration management area 11a, the address of the cell page information entry 1b indicated by the cell pool management book 1a managing the cell page belonging to the cell is stored.

(2) Cell acquisition process: {see FIG. 3} In this figure, (a) shows a state before acquisition, and (b) shows a state after acquisition.

First, if the acquisition request number is larger than the “remaining cell number” in the cell pool management book 1a, the cell pool described later is expanded.

If it is not large, the head cell address is taken out from the "head cell pointer" of the cell pool management book 1a,
Substitute in the top acquisition cell pointer for user notification. Cells for the acquired number from the top acquired cell address (shown by oblique lines)
And assigns the last cell address to the last acquired cell pointer, assigns the contents of the first 4 bytes of the cell (pointer to the next empty cell) to the "first cell pointer" of the cell pool management book 1a, and The number of cells obtained is subtracted from the number of cells.

(3) Cell release processing: {see FIG. 4} In this figure, (a) shows a state before release, and (b) shows a state after release.

First, the first four bytes (pointer to the next empty cell) of the cell indicated by the last released cell pointer are stored in the cell pool management list.
Substitute the contents of the “top cell pointer” in 1a. And
The contents of the head released cell pointer are set in the “head cell pointer”, and the released number is added to the “remaining cell number”.

(4) Expansion processing of cell pool: {see FIG. 5} In this figure, (a) shows a state before expansion, and (b) shows a state after expansion.

First, when it is determined that the above-mentioned cell pool expansion is necessary, for example, one area (cell page) of 4 Kbytes is acquired.

Next, one cell page information entry 1b pointed to by the "empty cell page information entry pointer" of the management book 1a is taken out and connected to the chain of the cell page information entry pointer (indicated by cell page information entry ₂ ).

That is, the “empty cell page information entry pointer”
Temporarily saves the contents (address) of the cell page information entry pointer next to the cell page information entry 1b pointed to by the area (the "next cell page information entry pointer" of the extracted empty cell page information entry). Set "cell page information entry pointer" of book 1a,
The contents of the "free cell page information entry pointer" in the management book 1a are changed to the "cell page information entry pointer" in the management book 1a.
, And the address of the saved “empty cell page information entry ₂ ” is set as the “empty cell page information entry pointer” in the management book 1a and chained.

Cell page pointer _{2 of} cell page information entry (cell page information entry ₂ ) cut out from an empty entry
Is set to the start address of the acquired cell page.

From the acquired cell page, the cell 11 of the size specified by the cell size is cut out by several cells in one cell page (shown by oblique lines), and the address of the cell page information entry 1b is set at the head of each cell 11 Then, the leading address + the fourth byte is chained by the pointer.

Cell pool management book in the first 4 bytes of the expanded last cell
The contents of the “top cell pointer” of 1a are set, and the “top cell pointer” stores the top cell address of the expanded cell page.

Then, "number of cell pages" in cell pool management book 1a,
"Remaining cell number" is updated respectively.

(5) Degeneration processing of cell pool: {see FIG. 6} In this figure, (a) shows a state before degeneration, and (b)
Shows a state during degeneration, and (c) shows a state after degeneration.

First, when the “number of cell pages” indicated by the cell pool management book 1a is “1”, since the degeneration is impossible, the process returns as it is. Even if the number of cell pages is equal to or greater than '2', if the number of remaining cells is equal to or less than the number of cells of one cell page, since the degeneration is impossible, the process returns as it is.

When the “number of cell pages” indicated by the cell pool management book 1a is “2” or more, the following processing is repeated until the end of the cell 11 linked to the “top cell pointer” of the cell pool management book 1a.

The cell 11 is connected to the queue of the first cell pointer in the cell page of the cell page information entry 1b indicated by the cell page information entry pointer 11a (see FIG. 2 (b1)) up to the first four bytes of the cell. {See (b) of this figure} That is, the next cell pointer of the cell 11 indicated by the last cell pointer in the cell page in the cell page information entry 1b,
The address of the cell 11 is set in the last cell pointer in the cell page, and '1' is added to the number of cells in the cell page of the cell page information entry 1b.

When the above processing is completed up to the last cell, the cell page information entry 1b linked to the "cell page information entry pointer" in the cell page management book 1a is searched in order, and the following processing is performed.

1) The number of cells in the cell page of the current cell page information entry 1b is “the number of cells in one cell page” of the cell page management book 1a.
If it is the same as the above, the area of 4 Kbytes indicated by the cell page pointer of the current cell page information entry 1b is released, and the "number of cell pages" and "the number of remaining cells" of the cell page management book 1a are released.
To update.

Then, the current cell page information entry 1b is linked to the queue of the "free cell page information entry pointer" in the management book 1a.

That is, the next cell page information entry pointer of the current cell page information entry 1b is set to the previous cell page information entry.
The next cell page information entry of 1b is set, and the "free cell page information entry pointer" of the cell page management book 1a is set as the next cell page information entry pointer of the current cell page information entry 1b, and the cell page management book 1a is set. The address of the current cell page information entry 1b is set in the "free cell page information entry pointer".

2) If the number of cells in the cell page of the current cell page information entry 1b is smaller than the "number of cells in one cell page" of the cell page management book 1a, the process ends only by returning the cell 11 connected to the entry 1b. .

〔The invention's effect〕

As described above in detail, the cell pool management device of the present invention configures an empty cell chain by connecting all cells by one chain, cuts out an empty cell chain when acquiring a cell, and extracts an empty cell chain when returning a cell. It is characterized in that the process of acquiring and returning cells is performed at high speed, in which the speed is increased as the process only for connecting to the cell chain.

The process of degenerating the cell pool when vacant cells accumulate is executed as needed. At that time, the chain of vacant cells is examined to clarify which cell page each vacant cell belongs to. In other words, since the processing required for the degeneration processing of the cell pool area is managed independently,
There is no need to perform processing in consideration of the degeneration of the cell pool area at the time of cell acquisition and release, and the processing speed at the time of cell acquisition and release is improved.

[Brief description of the drawings]

1 is a diagram illustrating the principle of the cell pool management device of the present invention, FIG. 2 is a diagram illustrating a cell pool opening process according to the present invention, FIG. 3 is a diagram illustrating a cell acquiring process according to the present invention, and FIG. FIG. 5 is a diagram showing a cell release process according to the present invention, FIG. 5 is a diagram showing a cell pool expansion process according to the present invention, FIG. 6 is a diagram showing a cell pool degeneration process according to the present invention, and FIG. FIG. 3 is a diagram illustrating a cell pool management device. In the figure, 1a indicates a cell pool management book, 1b indicates a cell page information entry or an empty cell page information entry, 11 indicates a cell, 11a indicates a cell page information entry pointer, and.

 ────────────────────────────────────────────────── (5) References JP-A-60-5358 (JP, A) JP-A-62-118454 (JP, A) JP-A-60-118949 (JP, A)

Claims (1)

(57) [Claims] 1. A method according to claim 1, further comprising: allocating, in response to a storage area acquisition request from an application program, at least one cell of a smaller unit from a cell pool having at least one cell page having a storage area of a predetermined unit. A cell pool management device that controls release of cells to a cell pool in response to a return request. When all empty cells in a cell pool are connected to one chain and cells are allocated to an application program, the cell pool management device starts from the empty cell chain. When the application program returns a cell that satisfies the request and returns the cell, a vacant cell management means that manages the returned series of cells by connecting them to a vacant cell chain, Classify which cell page each cell in the empty cell chain belongs to, and There pool of cells management apparatus characterized by comprising detecting the cell pages a empty cell, and cell pools degeneration processing means for removing the cell pages from pool of cells, the.