JP3353376B2 - Storage area management method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a real-time OS for guaranteeing a processing time in an OS, and more particularly to a real-time OS memory management system capable of allocating and releasing memory of an arbitrary size.

[0002]

2. Description of the Related Art In general, in a real-time OS, in order to efficiently manage a memory and ensure a high-speed response to a user's request, the memory is divided into blocks of a fixed size, and the memory currently allocated to the user is used. The management is divided into a middle block and an unallocated empty block (or usable block). At the time of a memory allocation request, a continuous free block satisfying the requested size (hereinafter, one or more continuous free blocks is called a hole) is detected, and the requested size is allocated to the user. The rest will be managed as a new hall. At the time of a memory release request, the release position in all free blocks is detected, and in order to prevent block fragmentation, if it is continuous with holes before and after the memory area where the release is requested, it is combined and managed as a new hole .

[0003] Conventionally, such a management of a hall has been performed as follows.
April 21, 989 Ascii Publishing Co., Ltd. "MINI
X operating system "on pages 242 to 244. As an example of this method, FIG.
5 shows the relationship between the management data held by the real-time OS and the memory. In FIG. 15, reference numeral 1 denotes a concept of a memory. A hatched portion is a hole, and a white portion is a memory block already allocated. Reference numeral 41 denotes a hole management table associated with one hole, and has a size of the hole and a pointer pointing to the next hole. Reference numeral 3 denotes a free list indicating the head of the list including the hole management table 41. Real-time O
When the memory reservation request is issued, S searches the free list 3 based on the free list 3 and detects holes satisfying the requested size. When the detected hole is equal to the required size, the hole is taken out from the free list 3 and assigned to the user. If the detected hole is larger than the required size, the requested size is allocated to the user, and the required size is subtracted from the hole size. On the other hand, when a memory release request occurs, the free list 3 is searched in order to detect whether there is a continuous hole before and after the released hole. If there is a continuous hole before and after, the hole is removed from the free list 3, connected to the open hole, and then connected to the free list 3 again.

[0004]

However, the above-mentioned memory tube
In the logical system, the required size is
In order to detect a hole to add, and when releasing,
Detecting the release position of the freed memory area for connection with the hole
To do so, it was necessary to search for a free list. That
Therefore, the desired hole is connected near the head of the free list.
If you are fast, but first in the hole near the end
If the desired hole is detected, the search time will be longer.
Therefore, there is a problem that the occupation time of the CPU becomes long.

[0005]

[0006]

According to the first aspect of the present invention, a storage area management system divides a storage device into fixed-length blocks and divides the storage device into used blocks and unused blocks. A storage area management method for managing one or more consecutive unused blocks as holes, the storage area management method having the following elements. (A) present in correspondence to the free list (b) divided blocks for managing the hole as a list, ho - Le
Size or at least one continuous busy block
Phrases and size of the immediately preceding blanking blocks to be released upon release of the block management table (c) storage area for storing a flag indicating whether the tail block pointer and holes to the beginning of the next hole
By the flag of the lock and the releasing block
Block or immediately after the last block of the hole
Last tail block, a result of the block by referring to the flag is determined by means for determining the status of the last block of determining whether means; (d) flags the holes, blocks the hole of the previous hole If it is the last block of the hole ,
The size of the self-holes in addition to the size stored, clears the flag of the first block the management data immediately before the hall, a flag indicating the fact of the most <br/> tail flag of the last block management data of its own holes If the previous block is not the last block, the own hole is inserted at the end of the free list, and the flag of the block immediately after the last block of the own hole or the flag of the last block of the hole indicates the last. If not, the process is terminated.If the end is indicated, the data is stored in the first block management data of the own hole.
Are added the size of the immediately following hole size is, the maintenance means for clearing the end of the block management data flag of its own hole.

In the storage area management method according to the second aspect of the present invention, a storage device is divided into fixed-length blocks, and is divided into used blocks and unused blocks. The storage area management system that manages used blocks as holes has the following elements. (A) a free list group composed of N free lists managing the holes as a list; (b) at least the size of a hole pointed by the free list and managing the holes, a pointer for indicating the next hole, and a corresponding storage. (C) A means for connecting the hole management data for managing holes satisfying the following expression to the k-th free list in the free list group by a pointer: 0 ≦ k ≦ N ^2k ≦ hole size <2 ^{k + 1} (d) means for allocating the first hole pointed to the free list n which satisfies the following expression at the time of storage area allocation processing. 1 ≦ n ≦ N, 2 ⁿ⁻¹ ≦ storage size to be allocated <2
ⁿ

According to a third aspect of the present invention, in addition to the second aspect, a flag indicating whether or not the hole management data exists in each of the free list groups. Is provided in correspondence with the free list group.

[0009]

In the storage area management method according to the first aspect of the present invention, the block management table corresponding to the divided blocks on a one-to-one basis is provided with a flag indicating whether the block is being used together with the size and the like. There are features. This allows
When the storage area is released, the release processing can be performed by referring to the flags of the blocks before and after the area to be released, so that the processing can be sped up.

In the storage area management method according to the second aspect of the present invention, the size of a hole is classified into (2 ⁿ ≦ hole size <2 ^{n + 1} ), and a free list having n as an index is defined. It is characterized in that a power-number list, which is a group, is provided. In this way, at the time of the storage area allocation request, a list of the exponential numbers of the holes satisfying the request size is obtained from the request size, the first hole of the list is removed from the list as a desired hole, and after the request size is allocated. , And return the remainder to the power number list again. When a storage area release request is made, if a hole can be connected to holes before and after the release request, the holes are connected, and then a power-up number list to be connected is obtained from the size of the release area, and connected to the end of the list. In this way, particularly, the speed of the storage area allocation processing can be increased.

The storage area management method according to the third aspect of the present invention is characterized in that, in addition to the second aspect, a list management table corresponding to each free list group is provided. As a result, in order to detect a power-number list to which a desired hole is connected, it is possible to check the flag of the list management table instead of searching for the power-number list, thereby making it possible to further speed up the processing.

[0012]

【Example】

Embodiment 1 An embodiment of the present invention will be described. FIG. 1 is a diagram showing a relationship between management data and a memory in a storage area management system according to the present invention. In FIG. 1, reference numeral 1 denotes a conceptually described memory which is divided into blocks of a fixed size as in the conventional example and used. The middle block (open area) and the unused block (shaded area) are divided into 1
It is managed as one hall.

Reference numeral 2 denotes a block management data group associated with each of the above blocks. Next indicates the block management data of the first block of the next hole, size indicates the size of the hole, and F indicates the last block of the hole.
Otherwise, U is composed of the stored flag information.

Reference numeral 3 denotes a free list indicating the first block management data of the list connecting the holes. In the present embodiment, the process at the time of occurrence of memory allocation detects a desired hole by searching a free list as in the conventional example.

Next, the operation of memory management when a memory area release request is issued will be described with reference to the flowcharts of FIGS. In FIG. 1, for example, block 22
When the release request of (corresponding block management data is B22 in FIG. 1) is generated, first, the information of the block management data B21 of the block 21 immediately before the block 22 is checked (step 10), and the flag information is F. (Step 11) The processing shown in the flowchart of FIG. 3 is performed to connect to the immediately preceding hole (Step 12).

Next, a block 23 immediately after the block 22
The block management data B32 of the block 32 obtained from the size information of the block management data B23 is checked (step 13). Since the flag information is F (step 14), the flowchart shown in FIG. The processing shown is performed (step 15), and the release processing is completed.

When a release request for block 15 (corresponding block management data is B15 in FIG. 1) is issued,
In step 11, block management data B of block 14
Since the flag information of No. 14 is not F, the block management data B15 is linked to the head of the free list in step 16, and
Change the flag information to F. Since the flag information of the block management data B16 of the block 16 is not F in step 14, the release processing is completed as it is. FIG.
FIG. 11 shows a relationship diagram between the block management table and the memory after the release processing of the block 15 is performed.

Next, the connection with the immediately preceding hole (block 21) in step 12 of FIG. 2 will be described with reference to the flowchart of FIG. The connection with the immediately preceding hole does not require insertion into the free list by using the next information of the head block management data B21 of the immediately preceding hole as it is.

First, the size of the free area is set to 1 in the size information of the head block management data B21 of the immediately preceding hole.
Is added (step 20). Then, the flag information of the block management data B21 is cleared (step 21).
Flag of the last block management data B22 of the release area
F is set in the information (step 22), and the connection processing with the immediately preceding hole is completed.

Next, the connection with the holes (blocks 23 to 32) immediately after step 15 in FIG. 2 will be described with reference to the flowchart in FIG. Since the free area is already linked to the free list irrespective of the connection processing with the immediately preceding hole in step 11 of FIG. 2, the next information used in the free list is the first block management data B21 of the free area. Just use it.

Therefore, first, the head block management data B23 of the immediately following hole is removed from the free list (step 30), and s of the head block management data B21 of the release area is removed.
10 which is the size information of the block management data B23 is added to the size information (step 31). Then, the flag information of the last block management data B22 in the release area is cleared (step 32). FIG. 6 is a diagram showing the relationship between the block management table and the memory obtained as a result of releasing the block 22.

Embodiment 2 Next, another embodiment according to the present invention will be described. FIG.
FIG. 2 is a diagram showing a relationship between management data and a memory in the memory management according to the present embodiment. In the figure, reference numeral 1 denotes a memory;
It is filled with holes (shaded area), which are collections of unused blocks. Reference numeral 41 denotes management data for managing holes as in the conventional example, and includes at least an address indicating a hole size and a memory block, and a pointer for forming a list.

Reference numeral 42 denotes a free list group, which divides the hole size by 2 ⁿ to 2 ^{n + 1} , and forms one free list for each n. For the sake of simplicity, it is assumed that the memory is composed of 32 blocks and that there is one hole of each of sizes 1, 2, 5, 6, and 10, as shown in FIG. I do. Since the number of free lists is 32 = 2 ⁵ , the list may be composed of five lists. A free list 0 has a size 1 hole, a free list 1 has a size 2-3 hole, and a free list has a free list. 2, the holes 4 to 7 are connected to the free list 3, the holes 8 to 15 are connected to the free list 4, and the holes 16 to 31 are connected to the free list 4.

The operation when a memory allocation request of size 5 occurs in such a state will be described with reference to the flowcharts of FIGS. First, the number of a free list having holes that can surely satisfy the allocation of size 5 is obtained (step 50). At this time, assuming that the number of the desired free list is n, 2 ^n-1 ≦ request size <2
^What is necessary is just to find ⁿ that satisfies n. This is a value obtained by adding 1 to the most significant bit number when 5 is expressed in binary, that is, n = 3.

Next, it is checked whether n = 3 obtained in step 50 exceeds the upper limit of the number of the free list (step 51). In the case of this embodiment, the upper limit of the free list number is 4, and n does not exceed the upper limit.
It is checked whether a hole is connected to the free list 3 (step 52). In this embodiment, since holes are connected to the free list 3, the first hole management data of the free list 3 is removed (step 53), and it is checked whether the size of this hole is larger than the required size 5 (step 53). 54). In the case of the present embodiment, the size of the hole management data is 10 and is larger than the required size 5, so the size of the hole management data is subtracted by the required size and set to 5 (step 55). Next, the number of the free list to which the remaining hole management data is to be linked is obtained (step 56). At this time, assuming that the number of the free list to be obtained is n, n that satisfies 2 ⁿ ≦ the remaining hole size <2 ^{n + 1} may be obtained. This is the value of the most significant bit number when 5 is represented in binary, that is, n = 2.

Next, from n = 2 obtained in step 56,
Connect the remaining hole to the end of free list 2 (Step 5
7), the memory allocation processing is completed. FIG. 10 shows the relationship between the hole management data and the memory after the above processing.

On the other hand, if a memory allocation request of size 10 occurs, n = 4 in step 50, and in step 52, since no holes are connected to the free list 4, the process proceeds to step 58. In step 58, 1 is set to n.
Is added to make n = 5, and it is checked whether the value of n exceeds the upper limit (step 51). In the case of this embodiment, since n exceeds the upper limit value 4, the process proceeds to step 59. In step 59, the free list (n-1) = 3 is searched for a hole satisfying the size 10. If there is no hole satisfying the size 10 as a result of the search, the user is notified that the memory of the requested size cannot be allocated.

In the case of this embodiment, since the hole management data satisfies the required size 10, the process proceeds to step 53, and the hole management data is removed from the free list 4. Next, the size of the hole 5 is compared with the required size (step 54). As a result, since the size of the hole 5 and the required size are both equal to 10, the allocation process is terminated. FIG. 11 shows a relationship diagram between the hole management data and the memory after the memory allocation of size 10 is performed.

Next, a case where a request to release the block 22 occurs in the state of FIG. 7 will be described with reference to the flowcharts of FIGS. First, the hole management data group is traced to detect whether a hole exists immediately before the block 22 as in the conventional example (step 60). If there is no hole immediately before, the process proceeds directly to step 61. In the case of this embodiment, since the hole 4 exists,
Hole management data for managing hole 4 in step 61 (free list 0 points in this embodiment)
From the free list 0. Thereafter, the block 22 is connected to the hole 4 to form a size 2 hole (step 62). Next, it is detected whether a hole exists immediately after the block 22 (step 63). If there is no hole immediately after, the process proceeds directly to step 64. In the case of this embodiment, since the hole 5 exists, the hole management data for managing the hole 5 is stored in the free list 3 in step 64.
Remove from Thereafter, the blocks 21 to 22 are connected to the hole 5 to form a hole of size 12.

Next, the number of the free list to which the connected holes are to be connected is determined (step 66). At this time, assuming that the number of the free list to be obtained is n, n that satisfies 2 ⁿ ≦ the remaining hole size <2 ^{n + 1} may be obtained. This is the value of the most significant bit number when 12 is represented in binary, that is, n = 3.

Next, from n = 3 obtained in step 66,
The connected holes are connected to the end of the free list 3 (step 67), and the memory release processing is completed. FIG. 12 shows a relationship diagram between the hole management data and the memory after the release processing of the block 22 is performed.

Embodiment 3 Next, another embodiment according to the present invention will be described. FIG.
Is a diagram showing the relationship between management data and memory in the memory management according to claim 3;
7 is the same as that in FIG. 7 in the second embodiment. Reference numeral 71 denotes a list management table indicating a list management bit string corresponding to each free list in the free list group 42 on a one-to-one basis. Hole management data is connected to the corresponding free list. 1 is set when they are connected, and 0 is set when they are not connected.

The memory allocation processing in such a state will be described with reference to the flowchart of FIG. FIG.
Steps 50 to 59 are the same processes as those in the flowchart of FIG.

In step 51, if n obtained in step 50 does not exceed the upper limit, the list management table is searched from bit number n, and the bit number whose bit is "1" is obtained first (step 80). . If the bit to be found is not in the list management table (step 81), the process proceeds to step 59, and the same operation as in the second embodiment is performed thereafter.

If the bit to be determined in step 81 is found in the list management table, the flow advances to step 53, and the same operation as in the second embodiment is performed thereafter.

[0036]

As described above, according to the present invention, the management data is made to correspond one by one to the block which is the management unit of the memory in the real-time OS, and it is determined whether the block corresponding to the management data has been allocated or is available. Have information to judge,
When a release request for the allocated memory area occurs, the necessity of connection with the preceding and following holes can be checked by checking the management data corresponding to the block immediately before the release area and the management data corresponding to the block immediately after the release area. With the configuration, it is possible to avoid repetitive processing at the time of a memory release request.

[0037]

[0038]

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a relationship between management data and a memory according to a first embodiment of the present invention.

FIG. 2 is a flowchart illustrating a memory release process according to the first embodiment of the present invention.

FIG. 3 is a flowchart showing a connection process with the immediately preceding hole in FIG. 2;

FIG. 4 is a flowchart showing a connection process with a hole immediately after in FIG. 2;

FIG. 5 is a diagram illustrating a relationship between a block management table and a memory after a memory area release process of a block 15 according to the first embodiment of the present invention.

FIG. 6 is a diagram illustrating a relationship between a block management table and a memory after a memory area of a block 22 is released according to the first embodiment of the present invention.

FIG. 7 is a diagram illustrating a relationship between hole management data and a memory according to the second embodiment of the present invention.

FIG. 8 is a flowchart illustrating a memory allocation process according to the second embodiment of the present invention.

FIG. 9 is a flowchart illustrating a memory release process according to the second embodiment of the present invention.

FIG. 10 is a diagram illustrating the relationship between the hole management data and the memory after the allocation of the memory area of size 5 according to the second embodiment of the present invention.

FIG. 11 is a diagram illustrating the relationship between the hole management data and the memory after the allocation of the memory area of size 10 according to the second embodiment of the present invention.

FIG. 12 is a diagram illustrating a relationship between the hole management data and the memory after the memory area is allocated to the block 22 according to the second embodiment of the present invention.

FIG. 13 is a diagram illustrating a relationship between hole management data and a memory according to the third embodiment of the present invention.

FIG. 14 is a flowchart illustrating a memory allocation process according to a third embodiment of the present invention.

FIG. 15 is a diagram showing the relationship between hole management data and memory according to conventional memory management.

[Explanation of symbols]

 1 Memory 2 Block Management Table 3 Free List 41 Hole Management Data Group 42 Free List Group 71 List Management Table

Continuation of the front page (56) References JP-A-4-236639 (JP, A) JP-A-4-219836 (JP, A) JP-A-3-265944 (JP, A) JP-A-4-349546 (JP) JP-A-58-171780 (JP, A) JP-A-2-193231 (JP, A) ANDREW S., et al. TANENBAUM, supervised by Bunka Sakamoto, supervised by Teruyo Onishi, MINIX operating system, Japan, ASCII Corporation, September 1, 1990, P241-P244 (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 12/00 501 G06F 12/02 510

Claims (1)

(57) [Claims] 1. A storage device is divided into fixed-length blocks, and is divided into used blocks and unused blocks.
A storage area management method for managing one or more continuous unused blocks as holes, the storage area management method having the following elements. (A) present in correspondence to the free list (b) divided blocks for managing the hole as a list, ho - Le
Size or at least one continuous busy block
Phrases and size of the immediately preceding blanking blocks to be released upon release of the block management table (c) storage area for storing a flag indicating whether the tail block pointer and holes to the beginning of the next hole
By the flag of the lock and the releasing block
Block or immediately after the last block of the hole
Last tail block, a result of the block by referring to the flag is determined by means for determining the status of the last block of determining whether means; (d) flags the holes, blocks the hole of the previous hole If it is the last block of the hole ,
The size of the self-holes in addition to the size stored, clears the flag of the first block the management data immediately before the hall, a flag indicating the fact of the most <br/> tail flag of the last block management data of its own holes If the previous block is not the last block, insert your own hole at the end of the free list and enter the block or hole immediately after the last block of your own hole.
If the flag of the last block of the hole does not indicate the last, the processing is terminated as it is. If the flag of the last block indicates the last, the processing immediately follows the size stored in the first block management data of the own hole. Maintenance means to add the size of the hole and clear the flag of the last block management data of the own hole.