JPS6027962A - Structure memory control system - Google Patents

Abstract

PURPOSE:To obtain a control system which makes a garbage collection at a high speed by allowing an external device to access a cache memory simultaneously access from a block control unit to a mass storage memory. CONSTITUTION:When a request to generate a structure newly is made by an external processing unit, the size of a block wherein the structure is stored is sent to a structure memory control unit 120 and a hierarchical bit map 121 is used to search for an unused area of necessary size. Simultaneously, the unit 120 makes a request to secure one unused block number to a block control unit 100 and reports this number to the external processing unit to store the requested size in a size area subsequently. The block number given to the area wherein the new structure is stored and what order an element in the block is in are designated, so that the external processing unit generates the new structure in a memory 130.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to the implementation of a prologue structure and a management method for a dynamic memory management device.

In recent years, as interest in intelligent systems has increased, predicate logic language prologues have been attracting attention. One of the reasons for this is that structures composed of variable elements can be handled directly.

For example, in the prologue, the state in which there are "apples,""tangerines," and "pear" in a basket is called a "basket" with structural temperature.
It can be expressed as follows using a structure with 3 elements.

Basket (apples, oranges, none) Furthermore, the fact that Abe has this basket can be described as follows using a structure with a structural body temperature of ``has'' and two elements.

The (fat part, basket (apple, orange, none)) prologue makes it easier to describe data by using a structure with variable elements like this.

On the other hand, when a prologue is executed, a large number of structures are dynamically created and destroyed, so a large amount of memory cells are required as an area for the structures. Therefore, in order to improve the usage efficiency of memory cells, a garbage collection is performed in which used memory cells are once collected and used to store structures again. However, the processing cost associated with garbage collection is high, and may amount to 30% to 50% or more of the total processing cost.

The present invention provides a structure management method that can process such garbage collection at high speed.

One of the well-known implementation methods for realizing a structure is to connect multiple fixed-length areas with pointers.

Hereinafter, this method will be referred to as the first structure realization method. h 1st
The figure shows a conceptual diagram when a binary tree list cell 10 is used to express a structure (fat section, basket (apple, orange, none)). The most important feature of this method is that the unused area does not need to be in a continuous area because the unit for securing memory cells is a fixed length. In other words, the task of collecting used memory cells through garbage collection only requires connecting fixed areas (two consecutive memory cells in a binary tree list) with a pointer. However, the method of connecting fixed-length areas with pointers has the disadvantage that there is a large overhead when accessing the elements of the structure. For example, in order to access the n-th element of a structure, the pointer must be traced n times, which causes a memory access bottleneck.

As another method to overcome the drawbacks of the above method, there is a known method in which the elements of the structure are arranged in a continuous area and each element is accessed by offset from the header (hereinafter referred to as
This method is referred to as the second structure realization method. ). FIG. 2 is a conceptual diagram expressing a structure (thick part, basket (apple, orange, pear)) according to the second method. In FIG. 2, 20 is a structure hair area, 21 is an element number area, 22 is a mark pit used to indicate that the structure is in use or has been used during garbage collection, and the edict is data. Represents an area. The three areas including the structure hair area 20, element number area 21, and mark bit 22 will not be particularly referred to as a header area hereinafter.

In this method, a header area and a data area n for storing each element of the structure are allocated as continuous areas for the structure. Therefore, when a structure is included as an element, a pointer to the structure header area may be used as the element. Furthermore, elements can be accessed quickly using offsets from the header area.

However, this method has a problem in that the overhead of garbage collection is large because the structure needs to be stored in a continuous area of variable length. Furthermore, due to the nature of structures, there is a possibility that one structure may be shared by a plurality of structures. FIGS. 3(1) and 3(2) are conceptual diagrams showing the transition of memory areas due to garbage collection when structure A and structure C share structure B. FIG.

In FIG. 3, 30 is a memory, 31 is a structure area in use, and 32 is a used or unused area. Further, FIG. 3(1) shows the memory state before performing the garbage collection, and FIG. 3(2) shows the memory state after performing the garbage collection.

Carbage collection in this method is realized as follows. First, perform an operation to mark the structure currently in use. This is done by using the following algorithm to check the stack that stores information about the structure currently in use when the external processing device performs processing, and check the mark pits of structures that are directly or indirectly referenced from the stack. This is achieved by setting the area flag.

For all structures pointed to by the stack, if the structure's mark pit is already set, do nothing, otherwise set the structure's mark pit, and add the structure as an element. When a structure is included, the process is repeated for all structures that are elements.

The mark pit is set using the above algorithm.

The remaining structures can be collected as used space. However, just by connecting single ζ used areas with pointers as in the first structure realization method using fixed areas, it is not possible to secure a continuous area as the area for the next new structure. Therefore, in order to secure an unused area on a continuous area, as shown in FIG. 3(1), +2), the structure area 31 in use is relocated.
It is necessary to collect the used area 32.

The problem with this method is that when relocating the i body, all pointers pointing to the relocated structure must be rewritten.

An object of the present invention is to solve the problems of the second structure representation method described above, and to create a structure that allows fast access to elements and minimizes the overhead of structure location during garbage collection. The purpose of this invention is to provide a structure memory management method that realizes a structure.

According to the present invention, a large-capacity memory stores a structure including a fixed-length header section and a variable-length data section; a cache memory that stores a part of the large-capacity memory and is accessed by an external device; A hierarchical pit map that holds information for identifying a used area and an unused area of a large capacity memory, and for identifying individual structures stored in the large capacity memory and the cache memory. and the conversion process between the number and the storage address on the large-capacity memory, and when a continuous area for storing a new structure in the large-capacity memory cannot be secured, the structure on the large-capacity memory in use in the large-capacity memory using information in the layered bitmap;
a block management unit that performs an operation for securing a storage area for the various structures in parallel with the execution of processing by the external device using the cache memory, and the structures stored in the cache memory; Converting between the identification number and the storage address on the cache memory, fetching a structure that does not exist on the cache memory from the large capacity memory, or storing a newly generated structure in the large capacity memory. a cache management unit that executes processing, and a structure that allows the external device to access the cache memory using the cache management unit in parallel with the block management unit accessing the large capacity memory. A physical memory management scheme is obtained.

Next, the present invention will be explained in detail using the drawings.

FIG. 4 is a block diagram of a structure memory management device that is one of the embodiments of the present invention. In the figure, 100 is a block management unit, 101 is a block number area, 1
02 is a mark pit area, 103 is a pointer area that points to the beginning of the area on the memory that stores the structure, and 104 is a size area that stores the size of the block. Also, 1
10 is a cache management unit that manages the cache memory, 111 is a carry block number area that stores the block number allocated to the structure stored on the cache memory, and 112 is an unused area on the cache memory. The cache mark pit area 113 used for determination is a cache pointer area that points to the beginning of the area on the cache memory that stores the structure. 120 is a structure memory management unit, and 121 is a hierarchical bitmap.

Furthermore, 130 is a memory, and 140 is a cache memory. 160 is a stack memory in which information used to execute the prologue is stored.

The structure memory management unit 120 manages the memory 130 and the cache memory 140 using the information of the layered bitmap 121, the block management unit 100, the cache management unit 110, and This unit instructs marking of the structure currently in use based on the block number corresponding to the structure in use stored in the stack memory 160. 170 is a data bus that connects the cache memory 140, memory 130, stack memory 160, and an external processing unit (not shown); 190 is a data bus that connects the cache management unit 110, the block management unit 100, and the structure memory management unit; 120, a stack memory 160, and an address bus coupling an external processing unit (not shown). Further, 180 is an internal bus that connects the memory 130, the block management unit 100, and the structure memory management unit 120. Reference numeral 190 denotes an internal bus that connects the cache memory 140, the cache management unit l-' 110, and the structure memory management unit 120.

The structure memory management method in this embodiment will be explained with reference to the drawings. FIG. 5 is a conceptual diagram illustrating the structure memory management method in this embodiment.

Note that in the 102 mark bit areas, 11'' represents a block in use, and "0" represents an unused block.

When no structure is defined, the mark bit area 102 in the block management unit is "0".

When a request to create a new structure is issued to the structure memory management unit 120 from an external processing unit (for example, a prologue processor) (not shown), the operation of the structure memory management unit 120 is as follows. Become.

For example, consider storing a structure basket (apples, oranges, pears) in memory. First, the block size 4 for storing the structure is sent to the structure memory management unit 120, and the structure memory management unit 120
The hierarchical bitmap 121 is used to search for an unused area with a size of 4 or more. In parallel with searching for unused space,
The structure memory management unit) 120 requests the block management unit 100 to reserve one unused block number.

The block management unit 100 has a block number (block number 1 in FIG. 5) secured for the new structure.
is notified to an external processing unit (not shown). After that, the requested flock size is stored in the size area. By specifying the block number given to the area to store the new structure and the element number in that block, an external processing unit (not shown) can
A new structure can be created on 30.

While the block management unit 100 is determining the block number to allocate for the area to store the new structure, the structure memory management unit 120 can use the layered bitmap 121 to store the new structure. Search for an unused area and notify the block management unit ioo of the start address of the unused area.

The flock management unit 1-100 stores the start address of the unused area prepared for the new structure in the pointer area of the block number assigned to the area storing the new structure. As the value of the structure, the block number assigned to the area where the structure is stored is returned, so if you write the structure as follows: For structures included as elements, the block number of the structure as an element is stored in the position where the element of the structure is stored, as shown in FIG.

@Figure 5 further shows the structure Has (hanako, basket (apples, oranges, pears)) is a structure Basket (apples, oranges, pears) Indicates a shared state.

As new structures are generated one after another, the structure memory management device 120 finds itself unable to secure an unused area large enough to store the new structures, and starts garbage collection processing.

When garbage collection is started, all the values of the mark bits 102 are first set to "0". At the same time, the value of the hierarchical hit map 121 on the structure memory management unit 120 is also set to "0". Next, each block number of the area storing the structure stored in the stack memory 160 is marked as a block in use according to the following algorithm.

(1) After setting the mark bit 102 to “1”, from the address next to the address pointed to by the pointer area 103,
Search for the number of elements in the structure, and perform the operation (2) on the elements whose value is the block number. At this time, from the address stored in the pointer area 103, it is set in the hierarchical bitmap 121 that a continuous area of the size stored in the size area 104 is in use. The set of mark bitmaps 102 and the set of hierarchical bitmaps 121 are respectively block management units) 1
00 and the structure memory management unit 120 in parallel.

(2) If the value of the mark pit I-, 102 of the corresponding block is "I II", perform the process (1) for the next block number on the stack memory 160. The value of the mark pit 102 is "O" Then, for that block (
Perform the process 1).

As a result, on the block 9m unit 100, 41'' is set only in the mark pitch area 102 of the block number currently in use.Furthermore, the hierarchical bitmap on the structure memory management unit 120 121 is set with information about the middle area for one person and the unused area in the memory 130.

Next, using the information on the currently used area of the hierarchical bitmap 121, the currently used area is located. At this time, the location of the currently used area is performed in units of blocks. In parallel with the location of the in-use area, the pointer area 103 of the block management unit 100 is updated. For example, FIG. 6 shows a state in which block 3 has been relocated by the paste location process in the memory state of FIG. 5. When the used area is relocated block by block, the size of the used area increases as the relocation progresses. Once the used space is large enough to accommodate the newly generated structure that caused the garbage collection, the used space is allocated to the block number assigned to the new structure. Register it as an area and give permission to the external processing unit to resume processing.

When the external processing unit finishes generating the new structure, it resumes processing using the cache memory 140.

The structure memory management unit 120 allows the external processing unit to complete the generation of a new structure and transfer it to the cache memory 140.
If you confirm that the process has been resumed using

Next, a description will be given of the hierarchical bitmap 121 that searches for an area to store a new structure and provides information on areas in use during relocation processing.

FIG. 7 is a conceptual diagram of an embodiment in which information on the used area of the memory 310 is managed using the bitmap 300. In FIG. 7, one bit on the bitmap 300 corresponds to two cells on the memory 310, and by checking the bits on the bitmap 300, it can be determined whether the corresponding two cells on the memory 310 are in use or not. It is now possible to get information on whether it is used or not.

In FIG. 7, the value of the bit of bitmap 300 is “0”.
When the bit value is "1", it means that the two cells on the corresponding memory 310 are unused areas, and when the bit value is "1", it means that the two cells on the corresponding memory 310 are the used area. .

Therefore, when a request is made to allocate an unused area, it is necessary to continuously
A bit string is searched for on the bit map 300, and its start address is output.

“
When the bit string of "O" does not exist on the bitmap 300, garbage collection processing is requested.

The layered bitmap used in this structure memory management method is created by layering multiple bitmaps to speed up the process of searching for unused areas using bitmap 3oo in Figure 7. One bit of the bitmap has information regarding the status of several consecutive bits of the bitmap located below, thereby suppressing the increase in the number of bitmap accesses due to the existence of a large used area.

FIG. 8 is a conceptual diagram of an embodiment of a layered bitmap. 410.420.430.440 are each bitma.

450 is a memory. Bitmap 410
The upper 1 bit has information regarding the status of 4 bits on the bitmap 420, and the meanings of the bit values are as follows.

ti> When the value of the bit on the bit map 440 is “0”, it indicates that two cells on the corresponding memo IJ 450 are unused, and when the value is “1”, it indicates that the two cells on the corresponding memo IJ 450 are unused. 2 cells are in use.

(2) When the value of the bits on the bitmaps 410, 420, and 430 is "1", it means that the values of consecutive 4 bits on the corresponding bitmap one level below are all "1".

When the value is "0", it indicates that at least one of the consecutive 4-bit values on the corresponding lower bitmap is "0".

The method of searching for an unused area using a hierarchical bitmap follows the following algorithm.

(1) Using the uppermost bitmap 410, the value is “0”.
''. At this time, the bit 411 that is in charge of address 0 of the memory 450 (the rightmost end in FIG. 8) is searched. This is because there is a high possibility that a structure that is always used will be stored on the side.If a bit whose value is "θ" is found, the process moves to process (2).

(2) The value sent from the upper bitmap is “0”
From the position of the bit on the bitmap above ``, we can learn the consecutive 4 bits corresponding to that bit.

When the size of the requested unused area is larger than the size of the area on the memory 450 corresponding to the bit on the bitmap currently being examined, process (3) is performed. The value is “0”
″ bit, and perform the processing (
Do 2).

(3) Search for a bit string whose values are all "0", which corresponds to the size of the requested unused area, locate the first bit of that bit string, and perform process (2) on the lower bitmap. However, when the bitmap currently being examined is the bitmap 440, the starting address of the unused area on the memo IJ 450 is calculated and output from the starting bit position of the found bit string.

This structure memory management method separates the load on external devices from the garbage collection process that collects used memory cells that occur as a result of the dynamic creation and destruction of a large number of structures during prologue execution.
Garbage collection processing time seen from an external device using structure memory can be reduced.

[Brief explanation of drawings]

Figure 1 is a conceptual diagram showing an example of when a structure is realized using a fixed area, Figure 2 is a conceptual diagram showing an example of garbage collection when a structure is expressed mutably, and Figure 4 is 1 is a block diagram of a structure memory management device that is an embodiment of the present invention. FIG. Further, FIGS. 5 and 6 are conceptual diagrams explaining the garbage collection method of the present invention, and FIGS.
FIG. 8, Episode 4, is a conceptual diagram illustrating the hierarchical bitmap of the present invention. In the figure, IO is a binary tree list cell, 20 is a structure area, 21 is an element number area, 22 is a mark bit, the edict is a data area, 30 is a memory, 31 is a structure area in use,
32 is used area, ioo is block management unit +-
, ioi is a block number area, 102 is a mark bit area, 103 is a pointer area, 104 is a size area, 11
0 is a cache management memory, 111 is a cache block number area, 112 is a cache mark bit area, 113 is a cache pointer area, 120 is a structure memory management unit, 121 is a hierarchical bitmap, 1
30 is a memory, 140 is a cache memory, 160 is a stack memory, 170 is a data bus, 180 is an internal bus, 190 is an address bus, 131 is an area in use, 132
, 134 is used area, 300.410, 420, 43
0,440 is a bitmap, 310,450 is a memory, and 411 represents one bit of the bitmap 410. Figure 1 n Figure 2 Figure 3 (+) (2) Figure 4 Figure 5 Figure 6 Figure 7 300 Figure 8 Procedural Amendments Axis) 59, 10122 Showa Year Month Day 1, iJl'l Display of 1981 Special Fraud Application No. 1
No. 36126 2, Title of invention Structure memory management method 3
, Relationship with the case of the person making the amendment Applicant: 33-1-4, Shiba IL-cho, Minato-ku, Tokyo, Agent 5, Column for detailed description of the invention in the specification to be amended, Drawing 6, Contents of the amendment 1) On page 11, line 16 of the specification, "190 is" is amended to "200 is". 2) Figure 4 of the drawings attached to this application is amended to look like an attached drawing. Agent Patent Attorney Yo Uchihara

Claims (1)

[Claims] a large-capacity memory that stores a structure consisting of a fixed-length header part and a variable-length data part; a cache memory that stores a part of the large-capacity memory and is accessed by an external device; and a cache memory that stores a part of the large-capacity memory and is accessed by an external device; a layered bitmap that holds information for identifying areas and unused areas;
the large capacity memory; a conversion process between a number for identifying each structure stored in the cache memory and a storage address on the large capacity memory; and a new structure in the large capacity memory. When it is no longer possible to secure a contiguous area to store the structure in the large capacity memory, the structure in use in the large capacity memory is relocated in the large capacity memory using the information in the layered bitmap, and the structure in the new large capacity memory is relocated. a block management unit that performs an operation for securing a storage area for a structure in parallel with the execution of processing by the external device using the cache memory; and identification of the structure stored in the cache memory. conversion between a number and a storage address on the cache memory, fetching a structure that does not exist on the cache memory from the large capacity memory, and storing a newly generated structure in the large capacity memory. and a cache management unit that executes the cache management unit, and the external device can access the cache memory using the cache management unit in parallel with the block management unit accessing the large capacity memory. Structure memory management method.