JPH0552974B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a garbage collection method in a computer, in which garbage data dynamically generated during program execution is packed into one end of real memory.

[Conventional technology]

Numerical calculations have been the main field of application for conventional computers. In recent years, so-called symbolic processing, which directly handles human knowledge, has attracted attention and has even been called an artificial intelligence boom. These symbolic processes often involve pointing to significant data in the main memory (real memory) using data whose content is an address in the main memory, called a pointer, and connecting necessary data with a pointer. This process of connecting with pointers is performed as necessary during program execution, and pointers are also replaced. An area in the main memory that is no longer referenced due to pointer replacement will not be referenced again during subsequent program execution. Such data is called garbage. Garbage data is dynamically generated during program execution and is scattered in the main memory, so it is necessary to remove it and compress the entire main memory, ie, garbage collection.

In garbage collection using the mark and sliding compaction method, first, a mark is placed on the main memory cells that hold data necessary for program execution. Next, in sliding compaction, the marked cells are packed from one end of the main memory while maintaining the mutual positional relationship of the marked cells. The sliding compaction algorithm is COMM OF THE ACM, 21,
8, 1978 (PP662-665) is famous. This method uses an inverted pointer and sweeps the target area twice, without using a special work area, to change the pointer value (called pointer maintenance) that is required by reorganizing the garbage collection target area. This method is carried out by

FIGS. 20 to 23 are explanatory diagrams of the sliding compaction known as the Morris algorithm mentioned above. In Figure 20, 1
is a pointer for sweeping one cell at a time in real memory corresponding to an independent logical space for each process, which is a program execution unit, 2 is a cell holding upward pointer 4 that refers to cell 3, and 5 is cell 3 This is an inverted pointer that refers to cell 2 from cell 2.
In FIG. 21, 3' is the destination cell of cell 3,
6 is a pointer after garbage collection that corresponds to the upward pointer 4 obtained by processing the reverse pointer 5. In FIG. 22, 7 is a location pointer for packing cells that are not unnecessary areas (garbage) from one end of the logical space, 8 is a downward pointer that refers to cell 11, and 12 is a pointer generated when pointer 8 is processed. This is an inverted pointer. In FIG. 23, 13 is a pointer after garbage collection that corresponds to the pointer 8 obtained by processing the inverted pointer 12.

Next, the compaction operation according to Morris' method will be explained. In compaction, the logical space to be garbage collected is swept through two passes, that is, two sweeps. At this time, the preconditions are that the total number of garbage cells in the target area is known and that non-garbage cells are marked. Marking is performed to satisfy these conditions.

FIGS. 20 and 21 show the first pass processing of the compaction phase. The first pass sweep is performed in the same direction as the sorting direction. Sweep pointer 1 in the main memory sweeps from cell 2 to cell 3. Also, in the figure, the logical address of cell 2 is greater than the logical address of cell 3.
In the first pass processing, only upward pointers (pointers that refer to cells with a smaller logical address than the cell in which the pointer is written) and reverse pointers are processed. FIG. 20 shows the process when the sweep pointer 1 detects the upward pointer 4. In this case, a reverse pointer 5 to cell 2 is written in cell 3, and the contents of cell 3 are copied to cell 2. FIG. 21 shows the process when the sweep pointer 1 detects the reverse pointer 5. Reverse pointer 5
After the garbage collection of cell 3, the destination address is calculated for cell 2, which is referenced by cell 3.
Write a pointer 6 to the destination cell 3'. Also, the contents of cell 2 are copied to cell 3. The destination address after garbage collection is determined as follows. The sweep pointer 1 reduces the number of unnecessary area cells in the compaction target area known at the start of compaction each time it detects cells in the unnecessary area. By doing this, the sweep pointer can calculate the destination logical address after garbage collection of the cell currently being swept from the logical address currently being swept and the number of unnecessary area cells existing in the unswept area. It is.

FIGS. 22 and 23 show the processing when the sweep pointer 1 detects a cell in which the pointer is written in the second pass of the logical space sweep. At this time, the cells are arranged in the actual logical space, the downward pointer is processed, and the inverted pointer generated during the downward pointer processing is processed. The location pointer 7 first selects the cell with the smallest logical address. Sweep pointer 1 detects a cell 10 that is not an unnecessary area, and if the content of that cell 10 is not a pointer, copies the content of the cell pointed to by sweep pointer 1 to the cell pointed to by location pointer 7, and moves the location pointer 7 to the cell pointed to by sweep pointer 1.
Increase the value by 1. In FIG. 22, sweep pointer 1 is cell 1 where downward pointer 8 is written.
0 is detected. At this time, a pointer 12 to cell 9, which is referred to by location pointer 7, is written in cell 11, which is referred to by downward pointer 8 from cell 10. In the example shown in FIG. 22, an X is written in the cell 9 referred to by the location pointer 7. This is a case where X is not a pointer, and to be more precise, processing continues assuming that the contents of cell 10 referred to by sweep pointer 1 were X. Figure 23 shows sweep pointer 1
detects the cell 11 in which the inversion pointer 12 is written. At this time, a pointer 13 pointing to the cell 14 referred to by the location pointer 7 is written in the cell 9 referred to by the inversion pointer 12.

In this way, the relationship between cells 9 and 11 shown on the left side of FIG. 22 remains unchanged and they are packed on the side with smaller addresses in the logical space. Also, the second
As shown in Figure 3, when the sweep pointer 1 detects the upward pointer 12 in the second pass processing, the value of the upward pointer 12 has already been maintained to the value after garbage collection in the first pass processing, so The contents of the cell 11 referred to by the sweep pointer 1 may be copied to the cell 14 referred to by the location pointer 7.

[Problem to be solved by the invention]

However, as mentioned above, in the sliding compaction algorithm of the conventional garbage collection method, it is necessary to perform memory sweep of the sliding compaction target area twice, and it is difficult to measure the total number of cells marked at the time of marking. This is necessary for sliding compaction, which poses a problem in that the processing time for garbage collection becomes longer.

This invention was made in order to solve the above-mentioned problems, and it completes the memory sweep of the sliding compaction target area in one go, eliminates the need to measure the total number of marked cells at the time of marking, and An object of the present invention is to provide a garbage collection method that can shorten garbage collection processing time.

[Means to solve the problem]

The garbage collection method according to this invention is
A work area 21 for the garbage collector is set in a real memory area shared among all processes, and this work area 21 is used to ensure that the direction of the pointer in the shared area 20 matches the real memory sweep direction during compaction. When performing a sweep, the direction of the pointer is left as is, and when the direction is opposite to the sweep direction, the real memory cells are marked so that the pointer is all directed toward the work area 21. This makes it possible to change the real memory cells for the shared area 20 at the time of compaction. Sweep 1
It is characterized by ending in one episode.

[Effect]

The work area 21 serves as an intermediate table from the process-specific area to the shared area 20 during marking, and is used to change pointer values in the shared area 20 that are stretched in the opposite direction to the real memory sweep direction during compaction. . By using the work area 21, all pointers in the shared area 20 are substantially aligned in one direction at the end of marking. (Towards the work area 21, or in the real memory sweep direction) [Embodiment of the Invention] Figure 1 shows the state before garbage collection is executed, the end of marking, and the shared area according to the garbage collection method according to an embodiment of the present invention. FIG. 3 is an explanatory diagram of the operation after compaction. In the figure, 2
2 is an example of the state of main memory (real memory) before garbage collection is executed, 16 and 17 are physical spaces (partial areas of real memory), 18, 27, 19, and 28 are cells,
20 is a shared area shared among all processes, 21
is a garbage collection work area set in an area not subject to garbage collection in the shared area, and 23, 24, 25, and 26 are pointers. Further, 39 indicates an example of the state of the main memory at the end of marking, 27, 28, 29, 30, and 31 indicate cells, and 32 to 38 indicate pointers. 43 is an example of the state of the main memory at the end of compaction of the shared area, and 40, 41, and 42 are examples of the state of the main memory at the end of garbage collection of cells in the shared area that were referenced by other cells written in the work area 21. This is a pointer indicating the destination address.

FIG. 2 shows data types and the structure of one word handled in an embodiment according to the present invention. In the figure,
44 is the gc bit (2
45 is a tag section indicating the data attribute of the value section 46. Data types include vect,
There are CDSC and INT. vect is a pointer to a contiguous area in the shared area, and the data pointed to is cdsc (descriptor). The value part of cdsc describes the size of the contiguous area. INT indicates that the value part is an integer.
Contiguous area in the shared area pointed to by vect
It is called vect body. Also, vect only in the shared area
The body is removed. INT and vect are allowed data types that appear in the vect body.

It is assumed that the vect is not nested within the vect body as shown in FIG.
Furthermore, the structure created on the shared area is a tree structure.

All gc bits are 0 before garbage collection starts, and even after garbage collection, the gc bits of necessary cells are set to one of three states: mk, en, and rev. mk means that the marking of that cell has already been completed and that there is no cell that refers to that cell. en means that there is a cell referencing that cell. rev is a pointer generated during compaction and indicates that the contents of the cell are reversed pointers.

When marking the garbage collector, it sequentially sets the gc bit in cells in which data that is necessary even after garbage collection is written in the process-specific area. At this time,
When a pointer vect to the shared area is detected (this pointer is hereinafter referred to as the root pointer), that vect
gc of cells in the shared area that can be traced from
Set up the bits according to the procedure described below.

FIG. 4 is a flowchart showing the marking procedure starting from the route pointer. First, in step S1, the ring top rt is placed on the ring mark rm.
Substitute. The ring mark rm is a pointer to the next vect body to be marked, and the ring top rt is a pointer to an unmarked vect that appears in the structure being marked. Indicates a pointer that holds the address of the work area to be written to. In step S2, the cell to which the root pointer points is read, and in step S3, the gc bit is determined and the gc bit is enabled.
If this is indicated, the process moves to step S4 to process the route. The processing of this route will be explained with reference to FIG. The gc bit of cell 53 referenced by the root pointer is already en, and in this case, the cell 52 where the root pointer was written is
, copy the contents of cell 53. Also, if it is determined in step S3 that the gc bit is un (a state that does not belong to any of mk, en, and rev),
Proceeding to step S5, route processing is performed. The processing of this route will be explained with reference to FIG. of cell 59 referenced by the root pointer.
gc bit is un. First, the contents of the cell 59 are copied to the cell 60 pointed to by the pointer 56 that controls the work area 21 . After that, cell 58,
After writing the pointer to cell 60 in 59, the value of pointer 56 is decreased by "1".

Here, pointers 54 that control the work area 21
57 (see FIGS. 6 and 7) will be explained. 54 is the ring mark rm mentioned above, 55 is the ring top rt mentioned above, and 56 is the ring bottom rb.
If the cell referenced by the root pointer is unmarked, it indicates a pointer that holds the address of the work area where the contents of that cell will be copied.

After processing the route, move on to step S6.
Mark the body of the vect. This process will be explained with reference to the flowchart shown in FIG.
First, the body size of the vect is set in step S11, and if the size is not "0", the process moves from step S12 to step S13, the body element is read, and the tag is branched in step S14. As a result of tag branching, if it is INT, go to step S15, if it is vect, go to step S15.
Move to S16. The INT processing in step S15 is performed when the gc bit of the cell in which the body element is written is un
If so, set the gc bit of that cell to mk, otherwise do nothing. On the other hand, in step S16
The processing of vect will be explained with reference to the flowchart shown in FIG. The reference destination cell is read in step S21, and the gc bit of the reference destination cell is determined in step S22. As a result of this determination, if the gc bit is en, the process moves to step S23. The direction of the pointer in step S23 is determined by vect
This is done by comparing the value part of the vect tag data detected in the body of the cell with the logical address of the cell where the data was written. If it is determined that the direction of the pointer is downward, processing is performed to set the gc bit of the cell where the pointer was written to mk in step S25. Further, if it is determined in step S23 that the direction of the pointer is upward, the process moves to step S26. On the other hand, in step S22, gc
If it is determined that the bit is un, step S24
The direction of the pointer is determined, and if the pointer is pointing downward, the process moves to step S27, and if the pointer is pointing upward, the process moves to step S28.

Here, the processing of steps S26, S27, and S28 will be explained with reference to FIGS. 10 to 12. FIG. 10 shows the process of step S26. In FIG. 10, cell 66 references cell 65 by an upward pointer, and the gc bit of cell 65 is en.
In such a case, the contents of cell 65 are copied to cell 66. FIG. 11 shows the process of step S27. In FIG. 11, cell 68 refers to unmarked cell 69 with a downward pointer. In such a case, the gc bit of cell 68 is set to mk, and the gc bit of cell 69 referred to by cell 68 is set to en. Cell 70 referenced by ring top 55
Copy the contents of cell 68 to ring top 55.
Add "1" to. The process of step S28 is performed in the 12th step.
As shown in the figure. In FIG. 12, cell 72 refers to unmarked cell 71 with an upward pointer.
In such a case, copy the contents of cell 72 to cell 73 that is referenced in ring top 55, and
1 sets the gc bit to en. Also, in cell 72
The gc bit is set to mk, and the logical address of cell 73 is written in the value field.

After such processing, the process moves from step S6 to step S7 in FIG. 4, where it is determined whether the marking has been completed as described above, and if the marking has not been completed, the process returns to step S7.
Perform pop processing of S8. This pop processing at step S8 is shown in FIG. In FIG. 13, during pop processing, the logical address of the structure (real memory) to be marked next is obtained from the cell 75 referred to by the ring mark 54. The contents of the cell 76 are read from the contents of the cell 75 to know the size of the structure 74 to be marked. The contents of cell 76 are also copied to cell 75, and the logical address of cell 75 is written in the value field of cell 76. After these processes, "1" is added to the contents of the ring mark 54, and the marking of the structure 74 proceeds according to the algorithm for marking the body of the vect (step S6). Note that the gc bit is set in step S3.
In the case of mk, perform error processing in step S9.

With the algorithm described above, the garbage collection area having the data structure described in this embodiment can be compacted by sweeping the shared area in one pass.

Next, the shared area compaction process is performed in the 14th step.
This will be explained with reference to the flowchart shown in the figure. In the initial setting at step S31, the sweep pointer, location pointer, and conditions necessary for end determination are set. In step S32, the value is read from the cell referenced by the sweep pointer (SP), and in step S33, the gc bit of the read value is determined. If the gc bit is un, the process advances to step S37.
If mk, the process moves to step S34; if en, the process moves to step S35; and if rev, the process moves to step S36. When the gc bit is un, "1" is added to the value of the sweep pointer in step S37. gc bit
When the cell is mk, processing of the mk cell in step S34 is performed.
FIG. 15 shows the processing of this mk cell. In FIG. 15, in step S41, the read data is
Performs a tag branch and the result of this branch is INT or cdsc
In this case, the process of step S42 is performed. That is, the process in step S42 reads the gc bit of the read data.
un, write to the cell referenced by the location pointer, and then add "1" to the location pointer.

On the other hand, if the branch result is vect, the process of step S43 is performed. This process is shown in FIGS. 16 and 17. The tag of the read data is vect,
If the gc bit is mk, either the pointer points downward and refers to a cell in the shared area, or it refers to the garbage collector's work area.

FIG. 16 shows the processing of the downward pointer. In this case, the contents of the cell 85 referred to by the cell 84 are transferred to the cell 83 referred to by the location pointer 7.
Copy to. Thereafter, a reverse pointer that refers to cell 83 is written in cell 85, and "1" is added to location pointer 7.

FIG. 17 shows the processing of a pointer that refers to a work area. In this case, the data of cell 89 before the garbage collector is activated is the logical address of the cell referenced by cell 89 to which the upward pointer is written, and the logical address after garbage collection is completed is cell 90 in the work area referenced by cell 89. Retained. Therefore, in cell 88 referred to by location pointer 7, the gc bit is un and the tag is vect.
(tag part of cell 89) and value write the value part of cell 90, respectively.

FIG. 18 shows the process of step S35 when the gc bit of the read data is en in FIG. 14. In the data type handled in this example, gc
The only data written to the cell whose bit is en before the garbage collector starts is CDSC. The logical address of the cell 91 referred to by the location pointer 7 is written in the cell 93 in the work area referred to by the cell 92, and the pointer is extended from the cell 93 to the cell 91. In the cell 91, the tag part of the cell 92 is set to CDSC only in this embodiment, and the gc bit is set to UN.
The value written in cell 93 is written. FIG. 19 shows the process of step S36 in FIG. 14 when the gc bit of the read data is rev. Processing of the inverted pointer is similar to the Morris algorithm described above. In this example, the contents of the cell referenced by the reverse pointer are:
The GC bit is set to EN, and the tag part is determined to be CDSC. In the cell 94 referred to by the reverse pointer, the gc bit is un, the tag part is the tag of the reverse pointer, and the value is the logical address of the cell 95 referred to by the location pointer 7. The value written in cell 95 is assumed to be that sweep pointer 1 referred to cell 94, and the process of step S35 in FIG. 14 is performed.

According to the above embodiment, a work area for the garbage collector is set in an area shared between each process, and this work area is used to transfer pointers from each process-specific area to the inter-process shared area and a pointer within the shared area. By performing maintenance, sliding compaction of the process shared area can be performed in one memory sweep.

Note that in the above embodiment, restrictions are imposed such that the data structure allowed on the shared area is a tree structure. However, even if a looped structure or the structure itself is nested in the shared area, the work area for garbage collection is set to the total number of cells that can be referenced by other cells in the shared area. By taking up more workspace in proportion to the cells that can be referenced, instead of
It is possible to mark it so that it can be terminated with a pass. Further, in the above embodiment, the structure is marked with breadth priority (breath first), but depth priority (depth first) marking can also produce the same effect as in the above embodiment. . Further, in the above embodiment, the process of passing the pointer from the program execution unit specific area to the shared area via the work area is an internal process of garbage collection. These processes may be performed during normal program execution, rather than as internal garbage collection processing.

〔Effect of the invention〕

As described above, according to the present invention, a work area for the garbage collector is set in a shared area on real memory shared among all processes, and this work area is used to change the direction of the pointer in the shared area. When the direction of the real memory sweep matches the real memory sweep direction at the time, the pointer direction is left as is, and when the direction is opposite to the sweep direction, the real memory cells are marked so that all the pointer directions point toward the work area. Since the real memory sweep for the shared area is completed in one time,
The memory sweep of the sliding compaction target area can be completed in one go, and there is no need to count the total number of marked cells during marking, which reduces garbage collection processing time and improves efficiency. This has the effect that memory can be reused.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of operations before garbage collection is executed, after marking is completed, and after compaction of a shared area according to a garbage collection method according to an embodiment of the present invention. FIGS. FIG. 4 is a flowchart showing the marking procedure starting from the route pointer in this embodiment, FIG. 5 is an operation explanatory diagram showing the process of step S4 in FIG. 4, and FIG. 4 is an explanatory diagram showing the process of step S5, FIG. 7 is an explanatory diagram of pointers that control the work area in this embodiment, and FIG.
9 is a flowchart showing the process of step S6 in FIG. 4, FIG. 9 is a flowchart showing the process of step S16 in FIG. 8, and FIG. 10 is an operation explanatory diagram showing the process of step S26 in FIG. Figure 11 is the 9th
Operation explanatory diagram showing the process of step S27 in the figure, 1st
2 is an operational explanatory diagram showing the process of step S28 in FIG. 9, FIG. 13 is an operational explanatory diagram showing the process of step S8 in FIG. 4, and FIG. 14 is an explanatory diagram of the process of compaction of the shared area in this embodiment. 15 is a flowchart showing the process of step S34 in FIG. 14, and FIGS. 16 and 17 are
15 is an operational explanatory diagram showing the process of step S43 in FIG. 15, FIG. 18 is an operational explanatory diagram showing the process of step S35 in FIG. 14, and FIG. 19 is an operational explanatory diagram showing the process of step S36 in FIG. 14. Figures, Figures 20-2
FIG. 3 is an explanatory diagram of the operation of compaction known as Morris' algorithm as a conventional garbage collection method. 18, 19, 27, 28, 29, 30, 31...
...Real memory cell, 20...Process shared area, 2
1...Work area.

Claims (1)

[Claims] 1. Allocate memory so that each process, which is the execution unit of a program, is given an independent logical space, and the real memory corresponding to a portion of this logical space is shared between each process. Real memory shared between processes in a garbage collection method that sweeps and packs the marked cell contents to one end of real memory after marking valid cells. A work area is set up for the garbage collector in the upper area, and this work area is used to ensure that during the marking process, the direction of the pointer in the shared area matches the real memory sweep direction during the above-mentioned compaction. When the direction is opposite to the sweep direction, the direction of the pointer is kept as is, and when the direction is opposite to the sweep direction, the pointer is directed to the work area. This allows the real memory sweep for the shared area during compaction to be completed in one operation. Features a garbage collection method.