JP2545587B2 - Garbage collection method - Google Patents

Description

The present invention relates to a garbage collection method which is a kind of memory management of an information processing device.

[Prior Art] The field of application of computers has expanded from the conventional center of numerical calculation to so-called artificial intelligence. As a result, the formats of data handled by computers are diversifying. In the field of processing that treats human intelligence as it is with a computer, it creates some cohesive one-dimensional array data in the main memory,
An expression format called a pointer, which is a single word indicating the start address of the data, is often used. The one-dimensional array data pointed to by the pointer in such a format is called a structure. In some cases, pointers to other structures may be placed in the structure, and in this way, structure data associated with each other are linked by a chain of pointers.

FIG. 9 shows a state in which such data is expanded in the main memory. In the figure, 1 is a main memory, and one word of the main memory 1 is composed of a tag portion 1a and a value portion 1b. Tag part 1a
Is used to indicate the attribute of the data. 1c is the address of main memory. Reference numeral 2 is a route register, which has a tag portion 2a and a value portion 2b as in the main memory. The route register 2 stores a route of data which is connected and expanded by a chain of pointers in the main memory. There are three types of data attributes shown in the tag portion 2a in this figure. The vect on the route register 2 indicates that it is a pointer to the structure data. The top address of the structure is stored in the value part 2b. The dsc at address 0 of address 1c of seed memory 1 is a structure descriptor, and the size of the structure is stored in its value portion 1b. In this example, the following 3
Words are the elements of the structure. The int at address 2 is an integer, which has no structure and indicates the integer value in the value part of the word. Addresses 1 and 3 are pointers to other structures, and structures 4 and 10 are pointed to respectively. Furthermore, in the structure at address 10, there is a pointer at address 12 and the structure at address 14 is pointed to. Here, addresses 7, 8, 9 and 13 in the figure are the places where structures that were temporarily used in the process of processing in the past were present, but now they are out of the chain of the structure mentioned above. , This site will never be referenced again. Such areas are called garbage or dust areas.

The data in the main memory as described above is generated as needed as the processing progresses, and the newly generated data is placed in an unused area having a larger address and chained by a pointer. In addition, a structure that is no longer pointed to by anything in the process of processing becomes garbage while remaining in the memory. When such garbage increases in the main memory, the utilization rate of the main memory decreases. Therefore, the entire area is compressed except for this garbage area at an appropriate timing. This is called garbage collection (GC). Figure 10 shows the flowchart of the GC process by the copy method. In this process, the process starts from the pointer of the route register,
The structure pointed to from within is copied in order from the beginning of the new copy area. Next, the element of the copied structure is examined, and if it is a pointer, it is similarly copied to the next address in the copy area.

When this processing is performed on the data in FIG. 9, the final copy area becomes as shown in FIG. 11, and the reference relationship of the original structure data remains the same, but only garbage is removed and the data is packed in one direction. It becomes a combined state.

[Problems to be Solved by the Invention] According to the above processing, all the structures connected by the pointers in the main memory are processed and processed, so that no matter where the garbage data is, it is correctly removed and the area is compressed. Be assured. On the other hand, on the other hand, the structure in the range that does not actually include garbage, that is, the range from addresses 0 to 6 in FIG. 9 is also processed like the other parts, and the garbage collection processing time becomes long. There was a problem.

The present invention has been made to solve the above problems, and an object thereof is to narrow the target range of GC and to shorten the GC processing time.

[Means for Solving the Problem] The garbage collection method according to the present invention determines an area in the main memory in which garbage collection is not performed, and in an instruction that may rewrite the area,
When rewriting the inside of the area and writing a pointer to the outside of the area, the address to write this pointer is stored, and when the garbage collection is performed thereafter, the value of the pointer after the garbage is removed. It is characterized by rewriting to a new address.

[Operation] In the present invention, first, an area where garbage collection is not performed is set in the area on the main memory. This can be set using a means such as a register. Next, when a pointer pointing outside this area is written into this set area, the address on the main memory where this pointer is written is stored. These processes can be performed using a means such as a table. Then, at the time of garbage collection, the value of the pointer is rewritten. That is, since the address where the pointer is written is known, the location of the pointer is specified, and the value of the pointer is rewritten to the new address after the garbage is removed. Since this processing only needs to be performed in the area where garbage collection is not performed, it can be completed in a short time.

[Embodiment of the Invention] An embodiment of the present invention will be described below with reference to the drawings.

In FIG. 1, reference numeral 1 is a main memory showing the contents of a normally accessed area, and one word of the main memory 1 is composed of a tag portion 1a and a value portion 1b. The tag portion 1a is used to store the attributes of the data and the reference mark according to the present invention. 1c is the address of main memory. Reference numeral 2 is a route register, which has a tag portion 2a and a value portion 2b as in the main memory. The route register 2 stores a route of data which is connected and expanded by a chain of pointers in the main memory. Reference numeral 3 is a GC base register for holding a boundary value with the non-GC target area according to the present invention, 3a is a tag portion, 3b is a value portion, and the tag value ref is used to indicate an address with a reference pointer. 7 in this example
It indicates that the address is the boundary of the non-GC area. Four
Is a table showing the position of the pointer pointing to the GC target area existing in the non-GC target area according to the present invention, 4a is a tag part, 4b is a value part, and if the tag part 4a is int (integer), the table is not Indicates that it is in a registered state, and if the tag part is ref (reference pointer), it indicates that the pointer pointing to the GC target area may exist at the address pointed to by the value part.

The state of the data in the main memory is now the first at an appropriate timing.
It is assumed that the situation is as shown in the figure. In this state, the value of the start address plus 1 of the area being used is set in the GC base register 3. From the address 0 to immediately before this, it becomes a non-GC area. In this example, addresses 0 to 6 are not shrunk by GC even if garbage occurs thereafter. The next time the GC is started, this range is generally excluded from processing. However, if a pointer pointing to the GC target area in this area is generated in the subsequent processing, the pointer may change due to the GC and must be maintained in the GC processing. Dedicated command write-vecto to write a value to a structure element
r-element is used. FIG. 2 shows the format of this instruction. In this instruction, three argument registers 5, 6, and 7 are designated. The structure address of the write destination is designated in the argument register 5, the structure element number of the write destination is designated in the argument register 6, and the data to be written is designated in the argument register 7.

FIG. 3 shows a state in which after the initial state shown in FIG. 1 is set, the post-treatment proceeds to form a new structure. Main memory 1
A new structure is created at addresses 7, 8 and 9, and this is the third element of the structure after address 3 starting from address 0.
Written using ite-vector-element. The processing of this instruction will be described with reference to the flowchart of FIG.
In the step of S51, the two arguments 5 and 6 of FIG. 2 are added to obtain the address 3 of the writing destination. In S52, it is determined whether this is less than the GC base. If it is GC-based or higher, write operation is performed as it is in normal processing. In S53, the original contents of the write destination are read. Then, in S54, it is determined whether or not the element is already pointed to by the reference table. This is done so that the reference table does not increase even if the same element is rewritten many times. The reference mark is written in the tag portion 1a. If there is no reference mark,
It is determined that the data to be written is pointer type data and the pointer destination is GC base or higher. If this condition is satisfied, it means that a pointer to the GC target area has been generated, and the pointer is written with the reference mark in S59 after registration in the reference table in S57. As a result, the state shown in FIG. 3 is obtained. The R in the tag portion 1a at the address 3 in the main memory 1 indicates that a reference mark is attached.

The data structure is further advanced, and the structure in which the address 3 is separately generated is rewritten in FIG. 4. The new structure is placed from the address 10. Structure in the original address 7, 8, 9 has a garbage not referenced anywhere for address 3 is overwritten with the new pointer.

Assuming that the GC is activated in the state of FIG. 4, its processing will be described with reference to the flowcharts of FIGS. 7 and 8. First, the GC main routine shown in FIG. 7 is started. In S71, first, unconditionally, the area outside the GC base up to the GC base is copied. For systems that have the function of mapping physical memory to logical addresses, it is possible to use a method that simply rewrites the mapping and omits the copying of each word. Next, in S72, the contents of the route register are read, and the copy processing routine is called to process the pointer. This is shown in FIG. In S81, the pointer destination address and the GC base value are compared, and the pointer pointing to the GC non-target area does nothing. In this example, the value of the route register points to address 0, so nothing is done for this. Returning to S74 of FIG. 7, in the example of the table 4 shown in FIG. 4 for reading the first entry of the reference table, the reference pointer (ref) points to the address 3. In S75, the tag portion is determined and the tag is ref, so in step S76, the contents of address 3 after copying are read and the copy process is called. Since address 3 is a pointer to address 10 of the structure, proceed to S82 after the determination in S81.
Copy 3 words from address 10 to 3 words from address 7 in the new copy area. Next, the structure element copied in S84 is an integer of 200, which is not a pointer type. Since there is no pointer in the element of this structure, the process directly ends, and the process returns to S78, and the entire GC process ends because the next reference table entry is an integer. The state of the main memory after GC is as shown in FIG.

In the above embodiment, the GC by copying has been explained, but the so-called marking and sliding compaction method may be used as the GC method, and the same effect as in the above embodiment can be obtained.

Further, the GC base register and the reference table may be either dedicated registers or those placed in a specially provided area on the main memory.

[Effects of the Invention] As described above, according to the present invention, an area in the main memory in which garbage collection is not performed is set, and the area is rewritten in the area that may be rewritten. When rewriting the inside and writing a pointer outside the area,
The address to write this pointer is stored, and when garbage collection is performed after that, the value of the above pointer is rewritten to a new address after the garbage is removed, so the area where garbage collection is not performed is extremely processed. It has the effect of simplifying and increasing the garbage collection processing speed.

[Brief description of drawings]

FIG. 1 is a block diagram of the contents of main memory and related registers for explaining the operation of the GC method according to one embodiment of the present invention, FIG. 2 is the format of a write instruction, and FIGS.
FIG. 6 is a diagram showing how the contents of the schematic diagram of FIG. 1 change as the processing progresses. FIG. 5 is a flow chart of a write command, and FIGS. 7 and 8 are GCs according to the present invention.
Flowchart of processing, FIG. 9 is a schematic diagram of the contents of the main memory and related registers for explaining the operation of the conventional GC method,
FIG. 10 is a flow chart of the conventional copy type GC processing,
FIG. 11 is a schematic diagram of the contents of main memory and related registers after GC. 1 ... Main memory, 1a ... Tag part, 1b ... Value part, 2 ... Route register, 3 ... GC base register. The same reference numerals in the drawings indicate the same or corresponding parts.

Claims (1)

(57) [Claims] 1. In a garbage collection, the structure data connected by a chain of pointers is stored in a main memory, and a process of excluding an area of the structure data removed from the chain of pointers is performed at a predetermined timing. When an area that does not perform garbage collection is set in the area on the main memory, and the area is rewritten in an instruction that may rewrite the area, and a pointer outside the area is written , A garbage collection method characterized in that the address to which this pointer is written is stored, and when the garbage collection is performed thereafter, the value of the pointer is rewritten to a new address after the garbage is removed.