JPH0756799A - Method for managing storage area - Google Patents

Abstract

PURPOSE:To provide a storage area managing method capable of efficiently managing especially a storage area. CONSTITUTION:This storage area managing method is constituted of a storage area operating means 2 for executing the allocation of a storage area to be used for application processing 1, the return of an unnecessary storage area, the initialization of storage area management prior to the allocation and return request of the storage area, and the ending operation of storage area management at the time of completing requests to all storage areas, a block operation means 3 for executing the allocation and return of a block expressing the unit of a storage area less than a certain fixed size, a heap operation means 4 for executing the allocation and return of a heap expressing a large storage area capable of storing plural blocks, the allocation of blocks into each heap and the security of a heap area, and free area managing means 5, 6 for acquiring and registering unused free areas.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a storage area management method, and more particularly to a storage area management method for allocating and returning variable length storage areas. When operating a computer system, storage that allocates limited storage areas in response to storage area allocation requests from various application processes, and reuses storage areas that are returned when they are no longer needed Area management is required.

[0002]

2. Description of the Related Art Generally, storage area management secures a large storage area "heap" in response to an allocation request for a data area used by an application process, and allocates a size of the size requested by the application process. Allocate a "block" in this heap. When the block becomes unnecessary in the application process and returned to the storage area management, the storage area management reuses the returned unused free block for the next block allocation. This principle diagram is shown in FIG.

The methods of reusing free blocks are conflicting with each other, such as determining free blocks to be reused at high speed and suppressing “fragmentation” in which a large area is occupied by a small used size as much as possible. As a basic method to realize both extremes, there is a "first-fit method" that reuses the first found free block that is larger than the allocation request size, and the free block that is larger than the allocation request size. There is a "best-fit method" that reuses the smallest size of. The optimal fitting method tends to have smaller odd fragments, but it becomes much slower than the initial fitting method as the number of empty areas increases.

For these methods, the "buddy syst" method is used.
em) ”is generally used as a method for determining free blocks at high speed while suppressing fragmentation. Figure 32
Is the most common of the alter ego methods, "exponential alternation method (exponent
ial buddy system) ”to show the principle of free block management. In this method, an array for each size corresponding to a variation of a power of 2 with an upper limit determined in advance is prepared, and a list of empty blocks is managed for each size. Due to the fact that it is divided into sizes of powers of 2, it does not necessarily match the allocation size requested by the application process, but if an empty block larger than the allocation request size is reused, the remaining size becomes another power of 2 empty block. It can be divided into and reused.

FIG. 33 shows the principle of division and reconstruction in the alternation method. For example, for allocation request size 5,
Reusing an empty block of size 8 leaves 3 remaining size
Is divided into free blocks of size 2 and 1. Conversely, when this block of size 5 is no longer needed by the application process and is returned, the empty blocks of sizes 2 and 1 adjacent to that area are combined to form an empty block of size 8 of the original size. If there is another free block of size 8 adjacent to the free block of size 8 that has been grouped together, reconfiguration is recursively performed such that it is grouped into a free block of larger size 16. Reference: "12. Data structure and algorithm"
Memory Management ”Alfred V. Aho, John E. Hopcroft, Jeffrey
D. Ullman / Translated by Yoshio Ohno Information Processing Series 11 Baifukan 1987.

[0006]

The above-described alternation method has the following two problems. (1) Due to the nature of the algorithm, the upper limit of the size to be divided and managed must be set. If the upper limit size is not provided, the start pointer of the list of empty blocks by size cannot be managed as an array, and the head pointer of the list cannot be determined at high speed by easy calculation by exponential decomposition from the size value. (2) If the allocation and the return for the same small block are frequently repeated, the overhead is extremely large.

In many cases of applied processing, the number of small blocks allocated is large. Further, according to the structure prepared by the compiler language, blocks having the same structure type and the same size are frequently allocated and returned. Moreover, the above two problems are in a mutually contradictory relationship. That is, in order to solve the problem of (1), the larger the upper limit size is, the larger the overhead of the division and reconstruction of (2) becomes.

It is also possible to consider a method of managing a hash table based on the size value without using the alternation method. For example, the number of arrays in the hash table is 10 (array 0 to array 0
9), when the list management is performed for each remainder obtained by dividing the size value of the empty block by 10, the size of the empty block is 0,
Lists 10 and 20 are managed in the array 0, and sizes 1, 11, and 21 are managed in the array 1. In this method, unlike the alternation method, it is managed by the size of the empty block itself without being limited to the size of a power of 2, there is no division and reorganization, and there is no upper limit of the size value. Problems arise. (3) If there is no free block that matches the allocation request size, fragmentation is large. If an empty block that does not match the requested size is obtained from one array of the hash table, the difference between the size of the empty block and the requested size is large. Since the array order of the hash table is not in ascending order of size, it is difficult to find an empty block of an optimal size that suppresses fragmentation, even when sequentially examining different array numbers.

(4) If there are many empty blocks of the same size, the overhead of searching for empty blocks is large.
Since one array of the hash table is not limited to empty blocks of the same size, it is necessary to check the size of each empty block linked to the list. This overhead is extremely large when there are many free blocks of the same size. The present invention has been made in view of such a problem, and an object thereof is to provide a storage area management method capable of efficiently managing a storage area.

[0010]

FIG. 1 is a principle block diagram of the present invention, and FIG. 2 is a more detailed principle diagram thereof. In FIG. 1 and FIG. 2, the storage area operating means 2 follows a predetermined allowable size of the block area, and allocates an allocation request smaller than this size to the block operating means 3 as a block area. It is allocated to the heap operation means 4 as an area of the heap itself. In the conventional technique, the storage area is allocated from the application process 1 as a block in the heap area of a fixed size, and the heap area itself is not reused. On the other hand, in the present invention, the free area management means 6 for the heap is provided in order to reuse not only the blocks but also the heap itself.

FIG. 3 shows a more detailed principle of the free space management means 5 of the present invention. In FIG. 3, the size-based list management means 7 performs grouping for each size range of a predetermined free area (for example, a free block), and the hash table management means 8 performs grouping for each size range. With respect to the free area, the free area is sorted into an array of hash tables based on the size value. Also, the size / entry management means 9
A list is managed from each array of the table, and empty areas are further grouped for each same size for list management. This method gives priority to speeding up the selection of free space to be reused, and even if the size of the free space managed in the hash table does not match the requested size, the area to be reused is small and both This is a method in which the influence of fragmentation is small because the size difference is suppressed within a certain size range.

[0012] Generally, the number of blocks, which are small-sized regions, is very large, and the blocks tend to have the same size. The free area management proposed by the present invention can be said to be a management method suitable for blocks. On the other hand, the number of long data areas that exceed the allowable size of the block area allocated as the heap area is extremely small, and there are few cases where a plurality of long data areas have the same size. Moreover, since it is the highest priority to minimize the fragment size that becomes odd in such a large area, it can be said that the optimal fitting method is suitable for managing the free area of the heap.

As described above, the allowable size of the block area when the method of managing the free area is divided into the block and the heap, the range of the free area size value in the size-based list management means in the free area management of the present invention, The hash
The number of arrays in the table, performance and fragmentation control (space saving)
Is an important factor in terms of. Therefore, in the initialization of the storage area operating means 2 in FIG. 1, these factors can be set as the operation control parameters for the management of the storage area as the optimum values for each application process.

[0014]

According to the present invention, according to the predetermined allowable size of the block area, the allocation request of this size or less is allocated to the block operating means 3 as a block area, and when exceeding this size, the heap operating means 4 is allocated. Since it is allocated as the area of the heap itself, it overcomes the disadvantage of the alternation method that cannot allocate a large data area that exceeds the upper limit of a certain size. In addition, the free space management means 5
The value of the size of free space (for example, free block) itself,
The free space is allotted to the array of hash tables, and even if the same small block is allocated and returned frequently, it is not limited to the size of power of 2 as in the alternation method, and it is divided and re-allocated. There is no organization.

Further, the free area management means 5 groups the hash table by means of a hash table management means 8 for managing the free area by the hash value of the size value and a predetermined range of the size value of the free area. The size-based list management unit 7 is provided, and fragmentation is suppressed by the size of the grouped size even when there is no free block that matches the allocation request size. Furthermore, the free area management means 5 is provided with a size / entry management means 9 which manages a list by grouping free areas for each same size, and the size / entry management means 9 manages the list from each array of the hash table. Therefore, even if there are many free areas of the same size, the search depends on the number of types of sizes per array of the hash table, not on the number of free areas.

Finally, the storage area manipulating means 2 has an allowable size of the block area which is an important factor in terms of performance and suppression of fragmentation, and the free area size in the size-based list managing means 7 in the free area management 5. It is possible to provide a storage area management method that is optimized for each application process by performing initialization so that the range of values and the number of arrays in the hash table can be specified as operation control parameters.

[0017]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 4 is a system configuration diagram of an embodiment of the present invention. 5 to 7 are flow charts showing the operation of the entire embodiment. This system uses start processing (S
100), "initialization" of the storage area operating unit 16 (S11
0), data loading from the file 13 on the secondary storage device to the main storage (S120), and display of data content on the display device 11 (S130). Subsequently, in the data update process (S200), a command is accepted from the keyboard 12 (S210), and data is inserted (S22).
0) and deletion (S230) are performed, and the result is reflected on the screen repeatedly. When the end command is accepted, the end process (S300) is performed, and the data on the main memory is saved to the file 13 on the secondary storage device (S300).
310), "terminate" the storage area operating unit 16 (S)
320).

In the data loading (S120) of the start processing (S100) of FIG. 5, first, a large buffer area for storing a plurality of records is "allocated" to the storage area operating unit 16.
A request is made (S121), then the contents of a plurality of records are read from the file 13 into the buffer area (S122), and the record area is requested to be “allocated” to the storage area operation unit 16 (S123), while the record is transferred from the buffer area to the record area. Copy the contents. When the reading of the contents of all records and copying to the record area are completed (S12
4) The buffer area is “returned” to the storage area operating unit 16.

In the insert command (S220) of the data update process (S200) of FIG. 6, the data input together with the command from the keyboard 12 is interpreted (S221), and a new record area is requested to the storage area operation unit 16 by "allocate". Then, the input data is copied to the record area (S223) and the latest state of the screen in which the record is inserted is reflected (S224). Similarly, with the delete command, the input data is interpreted (S231), the latest state of the screen in which the record is deleted is reflected (S232), and then the record area to be actually deleted is returned to the storage area operation unit 16. (S233).

In the data save (S310) of the end processing (S300) of FIG. 7, first, a large buffer area for storing a plurality of records is "allocated" to the storage area operating unit 16.
A request is made (S311), the record area on the main memory allocated next is sequentially traced, and the result is stored in the buffer area and written to the file 13 on the secondary storage device. When the writing of the contents of all records to the file is completed,
The buffer area is “returned” to the storage area operation unit 16 (S312), but the “return” of a plurality of record areas that have been sequentially skipped is not performed (though it may be). The plurality of record areas are collectively released from the main memory in the next "termination" (S320).

FIG. 8 is a flowchart showing the operation of "initialization" (S110) of the storage area operating unit 16 shown in FIG. In this process, prior to the “allocation” and “return” of the storage area, the common control table shown in FIG. 24 that controls the entire storage area management is initialized (S111). Upon initialization, based on the operation control parameters passed from the application process 14, the block allowable upper limit size and the block allocation dedicated heap area size are set, and a list by size and a hash table for managing the free block area are set. It is ensured and the initial value is set (S112). Further, one heap area dedicated to block allocation is secured in advance and an initial value is set (S113).

FIG. 9 is a flow chart showing the operation of "termination" (S320) of the storage area operating section 16 shown in FIG. In this process, the unused heap area, individual data area heap, heap used for block allocation, and size entry heap are released (S321 to S3).
24). These areas are provided with the leading pointer in the common control table, and the list is sequentially released from this pointer. Furthermore, as termination of free block management, the hash tables for the number of size-based lists and the size-based lists themselves are released (S332, S33).
3). "Release of area" from the main memory is, for example, UNIX
It is assumed to use the free function of the library.

FIG. 10 is a flow chart showing the "allocation" operation (S123, S222) of the storage area operating section 16 shown in FIGS. In this processing, application processing 1
Input the requested size from 4 and return the pointer of the allocated storage area. First, the request size specified by input is compared with the block allowable upper limit size set in the common control table, and if the request size is larger, "heap allocation" is performed for the heap operation unit as a long data area (S131). , Otherwise, "block allocation" is performed for the block operation unit as a block area (S13).
2). In either case, the area immediately after each header portion of the allocated heap area or block area is returned as a pointer of the storage area used in the application processing.

FIG. 11 shows the storage area operating unit 16 shown in FIG.
5 is a flowchart showing the "return" operation (S233). In this processing, the pointer of the storage area from the application processing 14 is input and specified, and the pointer of the header portion of the heap or block immediately before this pointer area is obtained. The "heap return" process (S241) is performed, and if the storage area type is block, the "block return" process of the block operation unit (S24)
Perform 2). FIG. 25 shows the heap and block data structures.

FIG. 12 is a block operating section 1 shown in FIG.
7 is a flowchart showing an operation (S132) of “block allocation” of No. 7. This processing is called from the "allocation" processing (S123, S222) of the storage area operating unit 16 of FIG. 10, the allocation request size is input and designated, and the pointer to the allocated block area is returned. First, a request for "acquiring an empty block" is made to the empty block management unit (S14).
1). If there is no free block that satisfies the requested size, a new block is allocated on the heap (S14).
5). When newly allocating a block on the heap, the remaining area of the heap at the head of the effective heap link for block allocation (hereinafter simply referred to as “current heap”) in the common control table of FIG. 24 satisfies the requested size. Check If the remaining area is insufficient, it is necessary to allocate the heap for block allocation, and the heap operation unit is requested to "allocate heap" (S144).

Prior to the "heap allocation", it is checked whether or not there is a remaining area in the current heap, and if there is, the remaining area is swept out as a free block. (S142),
A request for "vacant block registration" is made to the free block management unit for blocks in the remaining area (S143). When a "heap allocation" is made, the current heap points to the newly allocated heap area. At this point, the current heap is always the heap with the remaining area that meets the requested size. Therefore, a "allocate block in heap" request is made to the heap operation unit 18 for this current heap, and a pointer to the newly allocated block area is obtained. Both free blocks to be reused and newly allocated blocks are bound to valid block links in the common control table of FIG.

FIG. 13 is a block operating section 1 shown in FIG.
7 is a flowchart showing an operation (S242) of “block return” of No. 7. This processing is called from the "return" processing (S233) of the storage area operation unit 16, inputs the pointer of the block, and removes the block pointed by the pointer from the valid link, and then the empty block management unit 19 A "free block registration" request (S25
1).

FIG. 14 shows the operation of the "heap allocation" of the heap operation unit 18 shown in FIGS. 8, 10 and 12 (S113, S).
131 and S144). This process is the "allocation" process (S1) of the storage area operating unit 16.
23, S222), the "block allocation" process of the block operating unit 17 (S132), and the storage area operating unit 16
Called from the "Initialization" process (S110), the heap partition is distinguished between block allocation and individual data area (long data area), and the allocation request size is input and specified, and a pointer to the allocated heap area is specified. return. First, a "free heap acquisition" request is made to the free heap management unit 23 (S154). If there is no free heap that satisfies the request size, a "heap area allocation" request is made to the heap operation unit (S155), and a new heap area is allocated in the main memory.

If the new heap partition is for block allocation, the request size is changed to the standard size of the block allocation heap in the common control table shown in FIG. 24 prior to this. Whether it is a reused free heap or a newly allocated heap, it is linked to the effective link of the heap according to the heap partition. That is, in the case of the heap for block allocation, the head pointer of the effective heap link for block allocation in the common control table of FIG.
It is linked by the head pointer of the link. Further, this heap division is recorded in the header part of the heap area. FIG. 26 shows a relationship diagram between data in the effective storage area.

FIG. 15 shows the heap operating unit 18 shown in FIG.
14 is a flowchart showing the operation of "heap return" (S241). This process is called from the “return” process (S233) of the storage area operation unit 16, inputs the heap pointer, specifies the pointer, and removes the heap pointed to by the pointer from the effective link. A "free heap registration" request is made (S261). This process
It is simply linked to the unused heap link for the individual data area in the common control table of FIG. 24, and the flowchart is not shown. The heap section of the heap returned by this processing is always the individual data area heap, and is removed from the individual data area effective heap link. In the case of the heap area dedicated to block allocation, the heap itself is not returned or reused because it is reused for each block allocated in it.

FIG. 16 shows the heap operating unit 18 shown in FIG.
"Block allocation in heap" operation (S142, S1
45) is a flow chart showing (45). This process is the “block allocation” process of the block operation unit 17 (S132).
Is called from, and inputs the allocation request size, and returns a pointer to a block of that size allocated in the heap. The pointer of the final position used (used size) of the data part of the heap (immediately after the header part) is used as the pointer of the block to be allocated, and the request size specified by input is added to the final position used of the heap header part and allocated. Size s of the header part of the created block
The value is set in the size.

FIG. 17 shows the heap operating unit 18 shown in FIG.
14 is a flowchart showing the operation of "securing heap area" (S132). This process is called from the "heap allocation" process (S113, S131, S144) of the heap operation unit 18, inputs the allocation request size, and returns a pointer to the secured heap. The size of the heap area secured in the main memory is the sum of the requested size and the size of the header part. The requested size specified by input is set to the area size max of the header part of the heap area secured with this value, and the final position used is cleared to 0.
It is assumed that the "area reservation" on the main memory (S161) uses, for example, the malloc function of the UNIX library.

FIG. 18 is a flowchart showing the operation (S141) of "acquiring an empty block" of the empty block managing section 19 shown in FIG. This process is called from the "block allocation" process (S132) of the block operation unit 17, inputs and specifies the allocation request size, and returns a pointer when a free block satisfying this size is found,
If there is not, a NULL pointer is returned. First, the pointer to the block to be returned is reset to NULL assuming that no free block is found. Next, based on the requested size designated by input, a "hash table determination" request is made to the size-based list management unit 20 (S171).
Check the number of free blocks in the determined hash table. If 0, it means that there are no free blocks.
The pointer of the block to be returned is returned as NULL. If it is not 0, it means that there is a free block of some size, and it is further checked from the hash table whether or not there is a free block that should satisfy the requested size. in this case,
First, a "size entry search" request is made to the hash table management unit 21 (S173), and it is checked whether there is a size entry larger than the requested size.

This condition is satisfied only because the pointer to the size entry returned from the "size entry search" process (S173) is not NULL.
Next, if there is a size entry larger than the requested size, one empty block is taken out from the size entry, and the taken out empty block is removed from the link from the size entry. As a result, if there is no free block in this size entry, remove this size entry from the link from the hash table,
"Delete size entry" (S174) is performed. "Delete size entry" simply binds to an unused size entry link in the common control table of FIG. By doing so, the area of the deleted size entry is reused when creating the size entry for the size value of the new free block. In response to the extraction of one empty block, 1 is subtracted from the number of empty blocks in the hash table. Furthermore, the pointer of the retrieved empty block is returned as the pointer of the block that satisfies the required size. FIG. 27 shows a relationship diagram between the data in the free storage area, FIG. 28 shows a relationship diagram between the list by size and the hash table, and FIG. 29 shows a relationship diagram between the size entry and the empty block.

FIG. 19 shows the operation of "registration of free block" by the free block management section 19 shown in FIG. 13 (S143, S2).
51 is a flowchart showing 51). This process is the “block allocation” process (S13) of the block operation unit 17.
2) and called from the "block return" process (S242), the pointer to the block to be registered as an empty block is input and designated. First, a "hash table determination" request is issued to the size-based list management unit 20 based on the size of the block designated by the pointer designated by the input (S).
271). When registering an empty block in the determined hash table, the hash table management unit 21
Requesting "size / entry search" to (S273),
Check for a size entry that matches the size of the input block. This condition is that the pointer to the size entry returned from the "size entry search" process (S273) is NULL or its size
You will not be satisfied unless the size of the entry matches the size of the block. If not, a "size entry creation" request is made to the hash table management unit 21 (S27).
4) Link the created size entries from the hash table.

The links from the hash table to the respective size entries are arranged in the order of the size values of the empty blocks (in this embodiment, the size values are arranged in descending order), and should be registered. It is possible to easily search the size entry corresponding to the empty block and the size value, or the size entry corresponding to the empty block of the optimum size (the required size or more and the minimum size) to be reused. Conversely, when linking a size entry with a new size value to the hash table, the order of this size value must be preserved. Therefore, the size of the
If the entry's pointer is NULL, then at the beginning of the link from the hash table, if not NULL, then the size of the newly created size
It can be seen that the entry should be inserted, which facilitates link binding. In this way, with respect to the size entry newly created or already existing, the input designated block is linked to the free block link from this size entry, and the number of free blocks in the hash table is incremented by one.

FIG. 20 is a flowchart showing the operation (S171, S271) of the “hash table determination” shown in FIG. 18 of the size-based list management unit 20 in the free block management unit 19. This processing is performed by the empty block management unit 1
Called from the "free block acquisition" process (S141) and the "free block registration" process (S242) of 9, the block size is input and designated, and each size has a hash table that keeps this block size within the range. Return the array number (hash table No.) of the list. Based on the number of lists by size (n) in the common control table of FIG. 24, the pointer to the array by size list for free block management, and the order of the array by size list is this block size threshold value. Assuming that the block sizes are in ascending order, the block size threshold value in each size list is searched for a block size greater than or equal to the specified input block size. The array of the list according to size is searched from 0 to n-2, and if there is no corresponding one, the last array number n-1 is adopted.

FIG. 21 shows the "size / size" of the hash table management unit 21 in the empty block management unit 19 shown in FIG.
It is a flow chart showing operation (S173, S273) of "entry search". This process is called from the "free block acquisition" process (S141) and the "free block registration" process (S242) of the free block management unit 19, and the block size (request size) is input and designated. If there is a matching size value size entry, the pointer is returned. If there is no size entry, the smallest size value out of the requested size values is returned, and if there is no size entry larger than the requested size, a NULL pointer is returned. Will be returned. First, the pointer to the size entry of the compatible size to be returned is reset to NULL. This hash function is then
Determine the sequence number on the table. As a simple hash function, for example, the remainder obtained by dividing the block size value of this request size by the number of arrays in the hash table is returned,
It is assumed that this is the array number on the hash table.

From the head pointer of the link to the size entry of the determined array number on this hash table, the size value of the size entry and the requested size are compared until the pointer becomes NULL following the successive links. To go. First, when the size of the size entry is smaller than the requested size, it means that there is no size entry larger than the requested size after this, and the search for the size entry is interrupted. Otherwise, this size entry is at least larger than the requested size, and for this reason, the size entry at this time is recorded as that of the conforming size. Further, if the size of this size entry matches the requested size, this size entry must be of a conforming size, and this suspends the search for the size entry. When the iterative process of following the size entry links is completed in this way, as already described, the order of the size entry links is from the largest size value. For example, the smallest size (the smallest size if the sizes match) is obtained, or NULL is obtained as the matching size entry pointer, and that pointer is returned.

FIG. 22 shows the "size / size" of the hash table management unit 21 in the empty block management unit 19 shown in FIG.
It is a flow chart showing operation (S274) of "entry creation." This process is called from the "free block registration" process (S274) of the free block management unit 19, the block size (request size) is input and designated, and the pointer of the newly allocated size entry area is returned. . First, the pointer of the size entry to be returned is set to the unused size entry in the common control table of FIG.
Set the first pointer of the link. This pointer value is N
If it is not UL, it means that there is an unused size entry, and this unused size entry is removed from the unused link for reuse. If it does not exist, it is necessary to allocate a new size entry from the size entry heap, and also in the area (current size entry heap) indicated by the link pointer of the size entry heap in the common control table. Examine the final allocation number last. If this value matches the heap size for size entry in the common control table (upper limit of array size of size entry), it means that it is full. In this case, for new size entry. Allocates a heap area.

L of heap for reserved size entry
ast is reset to 0 and is linked to the link of the heap for the size entry of the common control table to become a new heap for the current size entry. Whether the heap for the current size entry is new or existing, one size entry is allocated from this area, and last
The value of is incremented by 1. Whether the size entry is reused or newly allocated, the size value of this size entry is set to the requested size specified, and the start pointer of the link from this size entry to an empty block Reset the entry to NULL. Figure 30
Fig. 1 shows the structure of the size entry area.

FIG. 23 is a flow chart showing the operation (S154) of the "free heap acquisition" of the free heap management unit 23 shown in FIG. This processing is based on the optimal fitting method, and is the "heap allocation" processing (S11) of the free heap operation unit 18.
3, S131, S144), the heap size (request size) is input and designated, and if a free heap satisfying this size is found, the pointer is returned, and if there is no empty heap, a NULL pointer is returned. First, the pointer to the minimum heap to be returned is reset to NULL assuming that no free heap can be found. Next, the head pointer of the unused heap link for individual data area in the common control table of FIG. 24 is set as the current unused heap pointer. After that, until this pointer becomes NULL,
Repeat free heap exploration. First, if the area size max of the current unused heap is less than the required size, the process proceeds to the next heap. If the minimum heap has been determined (the minimum heap pointer is not NULL) and the area size max of the minimum heap is less than the area size max of the current unused heap at this time, the process proceeds to the next heap.

If none of the above, the current unused heap at this time is at least the requested size and the minimum size among them, and the pointer is recorded as a new minimum heap. Furthermore, if the area size at this time matches the requested size, this heap becomes the optimum size, and the search for the empty heap is interrupted. As a result of exploring the free heap, the minimum heap
If the pointer is set (not NULL),
Remove the heap from the links of unused heaps and return it as an optimal free heap that satisfies the requested size. In the present invention, a storage area allocation request from the application processing 14 is allocated as a heap or block according to the request size. I will explain how to correspond.

In the data load and data save in the flowcharts of FIGS. 5 to 7, a plurality of records are stored in the buffer area corresponding to the size of the physical block in the file on the secondary storage device, for example, 4K to 8K bytes. Read and write in bulk. Only one buffer area of this large storage area needs to be allocated when executing the data load and data save processes. Therefore, such a storage area is preferably allocated as a heap.

Further, in this embodiment, the data that is collectively loaded from the file is saved again in the file as a result of correction such as deletion and insertion of records. As such an application process, a text editor that modifies data of a character string having a variable length for each record of each line such as a program source is assumed. Assuming that the number of characters that can be displayed on the screen is up to 80 characters, it is customary to enter most records within 80 characters, and often records up to 160 characters for 2 lines are entered. A recorder with more than 3 lines may be input. It is conceivable that such a record storage area, for example, within 2 rows, that is, within 160 bytes, is allocated as a block storage area, and a record area exceeding that size is allocated as a heap storage area. . That is, if the block allowable upper limit size is designated as 160 bytes, the record areas within 2 rows are allocated as blocks, and the record areas and buffer areas larger than that are allocated as heaps.

Further, the number of record areas within one line is extremely large, and there is a high possibility that a large number of record areas of the same size will be allocated within this size range. Therefore, for the management of empty blocks, records within 1 row are further grouped into sizes of 2 levels, those within 40 bytes are the first size list, and those within 80 bytes are the second size list. In addition, those with a size of 160 bytes or more are managed in the third size list, and the number of hash table arrays is taken into consideration for each size list, considering the frequency of the number of cases and reuse of blocks of the same size. It is possible to set it.

[0047]

As described above in detail, according to the present invention, a small storage area is allocated as a block area and a large storage area is allocated as a heap area, so that the allocation size of the storage area is not restricted. Further, when reusing the returned storage area, it is possible to select the storage area to be reused at high speed while suppressing fragmentation as much as possible.
Furthermore, it is possible to provide an optimum storage area management method according to the usage tendency of the storage area for the application processing.

[Brief description of drawings]

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

FIG. 2 is a more detailed principle block diagram of the present invention.

FIG. 3 is a block diagram showing a more detailed principle of free area management according to the present invention.

FIG. 4 is a system configuration diagram of an embodiment.

FIG. 5 is a flowchart (1) showing the overall operation of the embodiment.

FIG. 6 is a flowchart (2) showing the overall operation of the embodiment.

FIG. 7 is a flowchart (3) showing the overall operation of the embodiment.

FIG. 8 is a flowchart showing an operation of initializing a storage area operating unit.

FIG. 9 is a flowchart showing an operation of finalizing a storage area operating unit.

FIG. 10 is a flowchart showing an operation of allocating a storage area operating unit.

FIG. 11 is a flowchart showing a return operation of the storage area operation unit.

FIG. 12 is a flowchart showing a block allocation operation of the block operation unit.

FIG. 13 is a flowchart showing a block return operation of the block operation unit.

FIG. 14 is a flowchart showing the heap allocation operation of the heap operation unit.

FIG. 15 is a flowchart showing a heap return operation of the heap operation unit.

FIG. 16 is a flowchart showing an operation of allocating blocks in a heap by a heap operation unit.

FIG. 17 is a flowchart showing a heap area allocation operation of the heap operation unit.

FIG. 18 is a flowchart showing an operation of an empty block management unit for acquiring an empty block.

FIG. 19 is a flowchart showing an operation of free block registration of a free block management unit.

FIG. 20 is a flowchart showing the operation of a hash table determination of the size-based list management unit.

FIG. 21 is a flowchart showing the operation of the hash table management unit for size entry search.

FIG. 22 is a flowchart showing the operation of the hash table management unit for creating a size entry.

FIG. 23 is a flowchart showing the operation of free heap acquisition by the free heap management unit.

FIG. 24 is a data structure of a common control table.

FIG. 25 is a heap and block data structure.

FIG. 26 is a relationship diagram between data in the valid (in use) storage area.

FIG. 27 is a relationship diagram between data in empty (unused) storage areas.

FIG. 28 is a diagram showing a relationship between a list by size and a hash table in free block management.

FIG. 29 is a diagram showing the relationship between size entries and empty blocks in empty block management.

FIG. 30 is a configuration diagram of a size entry area.

FIG. 31 is a principle block diagram of a conventional method.

FIG. 32 is a principle view of a conventional alternation method.

FIG. 33 is a principle diagram of division and reconstruction of a conventional alternation method.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Applied processing 2 ... Storage area operating means 3 ... Block operating means 4 ... Heap operating means 5, 6 ... Free area management means 7 ... Size list management means 8 ... Hash table management means 9 ... Size entry management means

Claims (9)

[Claims] 1. In storage area management for allocating and returning storage areas, allocation of storage areas used in application processing (1), return of storage areas that are no longer needed in application processing (1), and application The storage area management is initialized prior to the allocation of the storage area and the return request from the processing (1), and the storage area management is completed after the requests for the storage area from all the application processing (1) are completed. A storage area operating means (2), a block operating means (3) for allocating and returning a block representing a unit of storage area of a certain size or less, and a heap allocation for representing a large storage area for storing a plurality of the blocks, Heap operation means (4) for returning, allocating blocks in the heap, and securing heap areas, and free area management for acquiring and registering unused free areas in the blocks and heaps Storage area management method characterized by comprising a stage (5,6). 2. The storage area operating means (2) previously provides an upper limit size allowed as a block area, and when the storage area allocation request from the application processing (1) is less than or equal to this upper limit size. An area is allocated as a block area in the heap to the block operating means (2), and in response to a request to allocate a storage area (long data area) that exceeds the upper limit size, the heap operating means (4) is made to use the area of the heap itself. The storage area management method according to claim 1, further comprising allocating a storage area. 3. The heap operation means (4) is configured so that the heap area secured as a long data area is applied processing (1).
3. The storage area management method according to claim 2, wherein, when returned as an unused area from, it is reused as a heap area for allocation of the next large data area or a block allocation. 4. The heap manipulating means (4) re-determines the heap area when determining a heap area for block allocation, if there is a free heap area larger than the size of the block area requested by the application processing (1). 3. The storage area management method according to claim 2, wherein a heap area dedicated to block allocation is newly secured with a fixed size if not used. 5. The free area management means (5) specifies a hash table in which free areas are grouped for each predetermined stepwise size range, and the hash is based on the value of the size of the free area. Size-based list management means for calculating array number of hash table by function (8)
When registering an unused free area, register it in the hash table position of the array number calculated by the hash function.If reusing the free area, register the array number calculated by the hash function. A hash table management means (7) for obtaining a free area having a size equal to or larger than a requested size from a hash table position and deleting the obtained free area from the hash table. The storage area management method according to item 1. 6. The free space management means (5) uses a hash function when registering a size / entry management means (9) in which free areas of the same size are grouped and an unused free area. From the hash table position of the calculated array number, search for a size entry of the same size as the free space, register the free space in the size entry if there is the size entry, and newly create the size When creating an entry, registering free space in the size entry, and reusing the free space, search for a size entry larger than the requested size from the hash table position of the array number calculated by the hash function. , If there is the size entry, the empty area is taken out from the size entry, and if there is no free area in the size entry, The storage area management method according to claim 5, further comprising a hash table management means (8) for deleting the size entry from the hash table. 7. The hash table management means (8)
When registering an unused free area, register the free area or size entry by aligning with the size value of the free area from the hash table position of the array number calculated by the hash function. 6. A method for efficiently searching for a size entry of the same size when registering an area and for searching for an optimum size free area or size entry when reusing a free area. 6. A storage area management method described in 6. 8. The optimum adaption method, wherein, when reusing a free heap, the free area management means (6) selects, from all free heaps, a heap allocation request size or more and a minimum size. With respect to the management of empty blocks, a method of free space management according to the size and number of storage areas is used so as to use the free space management means (5) according to claim 5, claim 6 or claim 7. 8. The storage area management method according to claim 5, 6 or 7, wherein the storage areas are selectively used. 9. The storage area operating means (2) is a maximum size allowed as a block area, a fixed size of a heap area dedicated to block allocation, and a size-specific list used by the free area managing means (5). Number, the threshold value of the size of the free area to be grouped for each size list, and the number of hash table arrays for each size list, the operation control parameters are optimized for each application process (1). The storage area management method according to claim 1 or 5, wherein the value is designated to be initialized from the application processing (1) side.