JP2010015223A - Method for isolating object in memory area - Google Patents

Abstract

An object of the present invention is to prevent an access speed from being lowered even if there is an operation of a garbage collection (GC) process due to the presence of an object that is not accessed for a long period of time.
When garbage collection is performed on a computer, an object that is not accessed for a predetermined long period of time is detected as a non-accessed object in order to isolate an object that exists in a virtual memory space and is not accessed for a predetermined long period A second step of moving the non-access object to a newly reserved virtual memory area when a predetermined period has elapsed after detecting the non-access object, and a move to the newly reserved virtual memory area Then, when a predetermined period of time elapses, the newly secured virtual memory area is set as the inaccessible area 15 and the third step of preventing the garbage collection from accessing the inaccessible area is executed.
[Selection] Figure 1

Description

  The present invention relates to a method for effectively using a memory area by isolating an object that exists in a memory area and is not accessed for a predetermined period, and more particularly to a method for isolating an object existing in a heap memory.

  Generally, in a computer such as a personal computer, if all the virtual memory space of a process is held on a physical memory, many memory modules are required, which is very inefficient in terms of economy and energy. For this reason, virtual memory pages that hold valid data but have not been accessed for a long period of time are preferably swapped out to disk or mapped to slower but more energy efficient memory (hereinafter “ "Holding valid data" is called "alive").

  In a process such as Java (registered trademark), the size of many objects is smaller than the page size. Therefore, objects that live in the same page in the heap memory but are not accessed for a long time are mixed with other objects. Will do.

  FIG. 13 is a diagram illustrating how objects are mixed in a virtual memory page. In FIG. 13, an object 11 with an X mark is accessed, and an object 12 without an X mark is not accessed for a long period of time. As shown in the figure, in all virtual memory pages 13, there is at least one object (access object) 11 to be accessed, so that these virtual memory pages 13 are swapped out or a low-speed memory (see FIG. It is not preferable to map to (not shown).

  Furthermore, in a process such as Java (registered trademark), a so-called garbage collection (GC) process accesses every living object every few seconds to several minutes (this GC process is This is a function that automatically releases the memory area that the program dynamically allocates when it is no longer needed. Therefore, even if there is an object (non-access object) that has not been accessed for a long time from the user program, it is not preferable to swap out the non-access object or map it to a low-speed memory.

  Therefore, in a process such as Java (registered trademark), when reducing the physical memory usage, an object that is not accessed for a long time by the user program is separated from other objects and placed in another virtual memory page. Is desirable.

  In this case, if an object that is not accessed for a long period of time with a high probability is selected, the user program will access a virtual memory page that is swapped out to a disk or the like or mapped to a low-speed memory, and the access speed is reduced. It will drop significantly.

  In addition, in a process such as Java (registered trademark), a GC process operates. Therefore, when an object is isolated, it is necessary to make the GC process access to the isolated object unnecessary.

  Incidentally, as a technique for monitoring and rearranging recently accessed objects, one disclosed in Patent Document 1 is known. Here, a set of recently accessed objects is detected, and the same virtual memory page is detected. Data locality is improved by arranging. In the method described in Patent Document 1, an object that is frequently accessed is isolated from other objects.

  On the other hand, Non-Patent Document 1 proposes a method of isolating objects that are alive but have not been accessed for a long time in a virtual memory space and swap them out to a disk for a program that leaks memory.

In this method, 1 is set in the 1 bit in the header of all objects and the lower 1 bit of the pointer in all objects in the GC process, and a barrier code is inserted immediately before accessing all objects in the user program. Thus, by setting the pointer and header bits to 0, an object that is not accessed between GCs is detected.
JP 2006-92532 A M.M. D. Bond and K.D. S. McKinley. Tolerating memory leaks. UT Austin Technical Report TR-07-64, 2007.

  However, in the method described in Patent Document 1, an object that has not been accessed for a long time is not expelled (isolated) from the physical memory, but is simply rearranged. There is a problem that the access speed cannot be increased because the live object is accessed.

  Further, in the method described in Patent Document 1, it is difficult to effectively reduce the physical memory usage amount because objects that are not accessed for a long time are not selected from objects that are not frequently accessed. There is also a problem of being.

  On the other hand, in the method described in Non-Patent Document 1, due to the overhead of the barrier code, the execution speed of the program is reduced by about 9% on average, and in particular, the barrier code is necessary in the user program. Only when the amount of physical memory becomes insufficient, there is a problem that it is extremely difficult to perform a flexible response to activate a detection mechanism for detecting an object that is not accessed for a long period of time.

  An object of the present invention is to provide an object isolation method in which the access speed does not decrease even when the GC process operates.

  Another object of the present invention is to provide an object isolation method capable of effectively reducing physical memory usage.

  Still another object of the present invention is to provide an object that can detect and isolate an object that is not accessed for a specified period (a period longer than a predetermined threshold in which memory is reserved) according to the amount of physical memory used. To provide an isolation method.

  In view of the above problems, the present invention provides the following solutions.

  (1) The present invention is a method for isolating an object that exists in a virtual memory area and is not accessed for a specified period of time, and is executed by a computer on which garbage collection is performed, and the object that is not accessed for a specified long period of time is hidden. A first step of detecting as an access object; a second step of moving the non-access object to a newly reserved virtual memory area after a predetermined period of time has elapsed after detecting the non-access object; A third step of making the newly reserved virtual memory area an inaccessible area and preventing the garbage collection from accessing the inaccessible area after a predetermined period of time has passed after moving to the reserved virtual memory area. It is characterized by having .

  In the method described in (1), after a non-access object is detected, the non-access object is moved to a newly secured virtual memory area when a predetermined period elapses, and is newly secured when a predetermined period elapses. Since the virtual memory area is set as an inaccessible area so that garbage collection does not access the inaccessible area, the access speed does not decrease even if the garbage collection is operated.

  (2) In the method according to (1), in the first step, the first step sets an access flag for the object considered to be accessed within the specified period, and distinguishes it from the object that is not accessed. The detection is performed by the following.

  In the method described in (2), since the access flag is used to distinguish the object that is not accessed, the object can be easily distinguished.

  (3) In the method according to (2), the present invention is characterized in that the first step is started when it is necessary to reduce the amount of use of physical memory.

  In the method described in (3), since the first step is started when it is necessary to reduce the usage amount of the physical memory, the physical memory usage amount is effectively reduced as necessary. be able to.

  (4) In the method according to (2), the present invention is characterized in that, in the first step, an access flag is set for an object to be processed at each load / store instruction.

  In the method described in (4), since an access flag is set for the target object at every load / store instruction, an object that is not accessed for a long time with a high probability among objects that are not frequently accessed. Can be selected.

  (5) In the method according to (2), in the first step, in the first step, an object that has caused a cache miss, an object accessed by a load / store instruction that has been hit by sampling at regular intervals, and garbage collection Objects that were directly pointed to from the register or stack at the time of activation, newly created objects, objects in the new generation area when using generational garbage collection, or when using generational garbage collection When at least one of objects in the old generation area but directly pointing to the new generation area is generated, the object is accessed.

  In the method described in (5), an object that caused a cache miss, an object that was accessed by a load / store instruction that was hit by sampling at regular intervals, or was pointed directly from a register or stack when garbage collection was started Objects, newly created objects, objects in the new generation area when using generational garbage collection, and pointing to the new generation area directly in the old generation area when using generational garbage collection When at least one of the objects occurs, it is assumed that there is an access to the object. Therefore, an object that is not accessed for a long time can be selected from objects that are not frequently accessed.

  (6) In the method according to (1), in the method according to (1), in the second step, the newly reserved virtual memory area is set as a semi-inaccessible area, and the non-accessed object is moved to a semi-inaccessible area. After that, the physical memory that has become unnecessary is released.

  In the method described in (6), the newly allocated virtual memory area is set as a semi-inaccessible area, and after moving an unaccessed object to the semi-inaccessible area, the unnecessary physical memory is released. The amount of physical memory required for program execution can be reduced.

  (7) In the method according to (6), in the method according to (6), in the third step, an object in the semi-inaccessible area is accessed from a user program while a predetermined period has elapsed. Otherwise, the semi-inaccessible area is set as an inaccessible area, and when accessed from the user program, the accessed object is returned to the outside of the semi-inaccessible area. .

  In the method described in (7), the semi-inaccessible area is set as an inaccessible area, and when there is an access from the user program, the access target object is returned to the outside of the semi-inaccessible area. There is no inconvenience in processing by the user program.

  (8) In the method according to (7), the present invention is characterized in that, in the third step, the contents of the inaccessible area are stored in a memory other than a physical memory.

  In the method described in (8), since the contents of the inaccessible area are stored in a memory other than the physical memory, the amount of use of the physical memory can be effectively reduced.

  (9) In the method according to (7), in the method according to (7), in the third step, a part of a pointer pointing out from the inaccessible area is added to a root set of garbage collection, and the garbage collection It is characterized in that access to the inaccessible area is not performed.

  In the method described in (9), since the alternation of the pointer pointing outside from the inaccessible area is added to the root set of the garbage collection, it is possible to reliably prevent the garbage collection from accessing the inaccessible area.

  (10) In the method according to (7), the present invention is characterized in that, in the third step, the garbage collection algorithm is changed to prevent access to the inaccessible area. Is.

  In the method described in (10), since the garbage collection algorithm is changed so that the inaccessible area is not accessed, it is possible to reliably prevent the garbage collection from accessing the inaccessible area.

  (11) The present invention is a program for isolating an object which is executed by a computer on which garbage collection operates and which is present in a virtual memory area and is not accessed for a specified period of time. A first instruction for detecting the non-access object, a second instruction for moving the non-access object to a newly reserved virtual memory area after a predetermined period of time has elapsed after detecting the non-access object, and the newly reserved A third instruction for making the newly reserved virtual memory area an inaccessible area and preventing the garbage collection from accessing the inaccessible area when a predetermined period elapses after moving to the virtual memory area. It is a feature.

  In the program according to (11), after a non-access object is detected, the non-access object is moved to a newly secured virtual memory area when a predetermined period elapses, and is newly secured when a predetermined period elapses. Since the virtual memory area is set as an inaccessible area so that garbage collection does not access the inaccessible area, the access speed does not decrease even if the garbage collection is operated.

  (12) In the program according to (11), the present invention sets an access flag for the object that is considered to be accessed within the specified period in the first instruction, and distinguishes it from the object that is not accessed. The detection is performed by the following.

  In the program described in (12), an object is not easily accessed using an access flag, so that the object can be easily distinguished.

  (13) In the program described in (12), the present invention is characterized in that the first instruction is started when it is necessary to reduce the amount of use of physical memory.

  In the program described in (13), the first instruction is started when it is necessary to reduce the amount of physical memory used. Therefore, the amount of physical memory used can be effectively reduced as necessary. be able to.

  (14) In the program according to (12), the present invention is characterized in that, in the first instruction, an access flag is set for an object as a target for each load / store instruction. is there.

  In the program described in (14), since an access flag is set for the target object at every load / store instruction, an object that is not accessed for a long time with a high probability among objects that are not frequently accessed. Can be selected.

  (15) In the program according to (12), in the program according to (12), in the first instruction, an object that causes a cache miss, an object that is accessed by a load / store instruction that is hit by sampling at regular intervals, and a garbage collection Objects that were directly pointed to from the register or stack at the time of activation, newly created objects, objects in the new generation area when using generational garbage collection, or when using generational garbage collection When at least one of objects in the old generation area but directly pointing to the new generation area is generated, the object is accessed.

  In the program described in (15), an object that caused a cache miss, an object that was accessed by a load / store instruction that was hit by sampling at regular intervals, or was pointed directly from a register or stack when garbage collection was started Objects, newly created objects, objects in the new generation area when using generational garbage collection, and pointing to the new generation area directly in the old generation area when using generational garbage collection When at least one of the objects occurs, it is assumed that the object is accessed. Therefore, an object that is not accessed for a long time can be selected from objects that are not frequently accessed with a high probability.

  (16) In the program according to (11), according to the second instruction, in the second instruction, the newly reserved virtual memory area is set as a semi-inaccessible area, and the object that is not accessed is moved to the semi-inaccessible area. After that, the physical memory that is no longer needed is released.

  In the program described in (16), the newly allocated virtual memory area is made a semi-inaccessible area, and after moving an unaccessed object to the semi-inaccessible area, the unnecessary physical memory is released. The amount of physical memory required for program execution can be reduced.

  (17) In the program according to (16), in the program according to (16), the third instruction may access an object in the semi-inaccessible area from a user program while a predetermined period has elapsed. Otherwise, the semi-inaccessible area is set as an inaccessible area, and when accessed from the user program, the accessed object is returned to the outside of the semi-inaccessible area. .

  In the program described in (17), the semi-inaccessible area is set as an inaccessible area, and when there is an access from the user program, the object to be accessed is returned to the outside of the semi-inaccessible area. There is no inconvenience in processing by the user program.

  (18) In the program according to (17), the present invention is characterized in that, in the third instruction, the contents of the inaccessible area are stored in a memory other than a physical memory.

  In the program described in (18), the contents of the inaccessible area are stored in a memory other than the physical memory, so that the amount of physical memory used can be effectively reduced.

  (19) In the program according to (17), in the third instruction, in the third instruction, an alternation of a pointer pointing out from the inaccessible area is added to a garbage collection root set, and the garbage collection performs the above-described garbage collection. It is characterized in that access to the inaccessible area is not performed.

  In the program described in (19), since the alternation of the pointer pointing outside from the inaccessible area is added to the root set of the garbage collection, it is possible to reliably prevent the garbage collection from accessing the inaccessible area.

  (20) In the program according to (17), the present invention is characterized in that, in the third instruction, the garbage collection algorithm is changed to prevent access to the inaccessible area. Is.

  In the method described in (20), since the garbage collection algorithm is changed so that the inaccessible area is not accessed, it is possible to reliably prevent the garbage collection from accessing the inaccessible area.

  As described above, according to the present invention, in a computer in which garbage collection operates, an object that exists in a virtual memory area and is not accessed for a predetermined long period of time is defined as a non-accessed object. After detecting and detecting this non-access object, when a predetermined period elapses, the non-access object is moved to the newly allocated virtual memory area, moved to the newly allocated virtual memory area, and then for a predetermined period. When this occurs, the newly allocated virtual memory area is set as an inaccessible area so that garbage collection does not access the inaccessible area, so the physical memory usage can be effectively reduced and the object is isolated. When Garbage collection of access to the object and is no longer needed, the access speed is not reduced. In addition to effectively reducing the physical memory usage, it is possible to detect and isolate objects that have not been accessed for a long period of time according to the physical memory usage.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a diagram illustrating a state in which an object that has not been accessed for a predetermined long time is isolated. First, when it becomes necessary to reduce the amount of physical memory used in a computer, an object isolation function (not shown) operates, and an access flag is set for an object considered to be accessed within a predetermined period.

  For example, if the execution speed does not decrease greatly even if the access flag is set for the target object at every load / store instruction to the heap memory (not shown), this is the most accurate method. Since the execution speed is greatly reduced, the following object is considered to be accessed as an approximate method.

  (1) Object that caused a cache miss, (2) Object accessed by load / store instruction hit by sampling every predetermined time, (3) Directly pointed from register or stack when GC process started Objects, (4) newly created objects, (5) objects in the new generation area when using a generational GC, and (6) objects in the old generation area when using a generational GC. When at least one of the objects directly pointing to the generation area (objects included in the light set of the generational GC) is generated, it is assumed that the object isolation function has accessed the object. Since these methods do not require a barrier code in the user program, they can be activated for a specific period.

  When the predetermined period has elapsed, the object isolation function moves an object for which an access flag is not set to a newly reserved virtual memory page. Here, this virtual memory page is called a semi-inaccessible area. If the period is not long enough, there may be objects that are accessed but not flagged. In this case, interpolation is performed by setting a flag on an object connecting between objects with a flag set.

  At this point, the physical memory is still mapped to the semi-inaccessible area, and at the same time, the object that is flagged can be released into the smaller area by releasing the unnecessary physical memory (in the figure). Region 14) indicated by a broken line. Then, the object flag is cleared.

  Further, during the elapse of a predetermined period, the object isolation function confirms that the user program does not access the object in the semi-accessible area. Here, the entire semi-inaccessible area is made inaccessible by the page protection mechanism (that is, the semi-inaccessible area is set as the inaccessible area 15 in the shaded area in the figure), and the access is detected by the signal handler. Note that an object that has been accessed from the user program is evicted from the semi-inaccessible area and returned to the normal heap memory.

  As described above, the semi-inaccessible area is defined as the inaccessible area 15 when a predetermined period has elapsed. The inaccessible area 15 is not mapped to the physical memory, and its contents are stored in a place other than the physical memory. For example, it can be written to disk or mapped to a slow but energy efficient memory.

  Here, so that the GC process does not have to access the inaccessible area 15, a clone 17 of a pointer pointing outside from the inaccessible area 15 is added to the GC root set. Also, the GC algorithm is changed so that the pointer to the inaccessible area is not traced.

  Next, each function described above will be described in detail with reference to the drawings.

  As described above, when the physical memory usage needs to be reduced, the object isolation function detects an object that is considered to be accessed within a predetermined period and sets an access flag. One bit in the header of each object can be used as this access flag. Further, a table for access flag bits may be secured in a memory area different from the heap memory.

  In this embodiment, as described above, (1) an object that has caused a cache miss, (2) an object accessed by a load / store instruction that has been hit by sampling every predetermined time, and (3) a GC process is started The object that was pointed directly from the register or stack at the time, (4) the newly created object, (5) the object in the new generation area when using the generational GC, and (6) the generational GC When used, an object that is in the old generation area but directly points to the new generation area (an object in the light set of the generational GC) is regarded as being accessed.

  (1) Object that caused a cache miss

  It is certain that the object that caused the cache miss has been accessed. In recent processors, a virtual memory address can be recorded when a data cache miss occurs as part of the function of taking a runtime profile. It is also possible to transfer control to the profiling function only once for the specified number of cache misses.

  In the profiling function, it is possible to identify an object including the virtual memory address by using a method described later after determining whether all the virtual memory addresses recorded so far are in the heap memory. .

  In this method, using the fact that there is a pointer to the virtual function table at the beginning of all objects, a word that can be regarded as a pointer to the virtual function table by scanning the memory from the acquired virtual memory address downward. Will find.

  (2) Object accessed by load / store instruction hit by sampling every predetermined time

  Similar to the cache miss profiling described above, many processors can transfer control to a profiling function at predetermined intervals. Many profiling functions can obtain the instruction and register contents that were executed immediately before.

  If the load / store instruction was executed immediately before, the virtual memory address accessed by the load / store instruction can be obtained from the contents of the register, and the object can be identified by the same method as described above.

  (3) An object that was pointed directly from the register or stack when the GC process was started

  An object pointed directly from a register or stack can be considered accessed in the near past or accessed in the near future. When a GC occurs, the object pointed to from the register or the stack is traced, so that an access flag to the object pointed directly can be set at a low additional execution cost.

  (4) Newly created object

  Newly created objects are likely to be accessed in the near future. Therefore, an access flag corresponding to the time of object generation is set up.

  (5) If a generational GC is used, objects in the new generation area

  Since objects in the new generation area are likely to be accessed in the near past and collected by the GC in the near future, they should not be isolated in the inaccessible area. Whether or not an object is in the new generation area can generally be determined from the address, so there is no need to actually set a flag.

  (6) When a generational GC is used, an object in the old generation area but directly pointing to the new generation area (an object in the generational GC light set)

  Objects in the new generation area are collected by the GC in the near future or moved to the old generation area. Therefore, the field directly pointing to the new generation area in the object in the old generation area is accessed and rewritten in the near future. Since such a field is included in the light set of the generational GC, an object including the field can easily set an access flag at the time of the GC.

  FIGS. 2A and 2B are diagrams for explaining the movement of an object without increasing the amount of physical memory. When a predetermined period elapses, an object for which an access flag is not set is quasi-accessed. It is moved to the impossible area. It is desirable to use this movement if the GC has a mechanism for moving an object. Therefore, the above movement may be performed simultaneously with the GC, and all the access flags are cleared when the movement is completed.

  From the next stage onward, it is necessary to be able to easily determine whether an object is included in the semi-inaccessible area from the address. Therefore, it is preferable to reserve a continuous large virtual memory area to be used as a semi-inaccessible area in the future with a system call similar to a memory map at the time of activation.

  The semi-inaccessible area needs to be mapped to physical memory at this stage. Therefore, the amount of physical memory required temporarily increases with a simple implementation. However, since the object with the access flag set is packed into a narrower area, the heap memory area that is no longer necessary when the object has been moved can be released.

  As an implementation that does not increase the amount of required physical memory, first, as shown in FIG. 2A, an object 11 with an access flag set in an ordinary heap memory area, an object 12 with no access flag set, To different virtual memory pages 13

  Subsequently, as shown in FIG. 2B, the page containing the object 12 with no access flag is mapped to the virtual memory page reserved as the semi-inaccessible area 16 by the support of the operating system (OS). Try again. That is, only the virtual memory address is changed without changing the physical memory address of the object 12 as indicated by the bold line in the figure.

  At this time, if the period for setting the access flag for the object 11 is not sufficient, the access flag is insufficient as shown in FIG. In the example shown in FIG. 3, assuming that the access flag is not raised even though the objects 11a and 11b are accessed, the object without the access flag is moved to the semi-inaccessible area in this state. Then, as will be described later, the execution time is greatly increased in the next stage.

  In this case, an access flag may be set and interpolation may be performed for an object connecting between objects having an access flag set.

  Here, an algorithm for interpolating access flags using heuristics will be described.

  FIG. 4 is a flowchart illustrating an algorithm for interpolating access flags using heuristics. In FIG. 4, a virtual object having a route set of R = GC (a machine register having a pointer value or an entry in the machine stack) as a field is set (step S1).

  Mark_pointer_fields () is called with R as an argument. The function of mark_pointer_fields () is to perform depth-first search on the graph of the object, and mark a field far from the other object for which the access flag is set among the pointer fields of each object (step S2). . The mark uses the least significant 1 bit of the field.

  Interpolate_accessed_objects () is called with R as an argument. The function interpolate_accessed_objects () is a depth-first search of the object graph again, and when an object with an access flag is set for the first time, the access flag is set for all objects in the path up to that point. is there. When searching for the tip of each object, priority is given to an unmarked field (step S3).

  FIG. 5 is a flowchart showing the function of mark_pointer_fields (object). In FIG. 5, when mark_pointer_fields (object) is started, the object object is received as an argument (step S4), and it is determined whether or not the object has been processed (step S5).

  If the object has been processed, it is then determined whether or not the object access flag is set (step S6). If the access flag is set, the approximation to the closest object with the access flag set is made. In this case, zero is returned as the distance (step S7). On the other hand, if the access flag is not set, it corresponds to the case where the distance is not known, so an arbitrary integer of 1 or more is returned (step S8).

  If the object has not been processed in step S5, a processed flag is set in the object in step S9, and the array distances is initialized to zero. Then, it is determined whether or not processing has been performed for all pointer fields of the object (step S10). If not, mark_pointer_fields (object) is called with the object pointed to by the pointer field p as an argument, and the result is obtained. Stored in distances [p] (step S11). Then, the process returns to step S10.

  If all the pointer fields of the object have been processed in step S10, then one threshold value is selected from the array distances (step S12). Note that the minimum value is selected as the simplest algorithm.

  Further, it is determined whether or not all pointer fields of the object have been processed (step S13). If not, it is determined whether or not the value distances [p] corresponding to the pointer field p is greater than the threshold value. (Step S14). If it is larger, the least significant bit of this pointer field is set and marked (step S15), and the process returns to step S13. If the value distances [p] corresponding to the pointer field p is equal to or smaller than the threshold value, the process returns to step S13.

  On the other hand, if all the pointer fields of the object are processed in step S13, it is determined whether or not the object access flag is set (step S16). If the access flag is set, zero is returned (step S16). S17). If the object access flag is not set in step S16, it is determined whether or not the object has a pointer field (step S18).

  In step S18, if the object has a pointer field, the minimum value +1 of the array distances is returned (step S19). If the object does not have a pointer field, the object is a dead end object, so that the maximum adjustment representing infinity is obtained. A numerical value is returned (step S20).

  FIG. 6 is a flowchart for explaining the function of interpolate_accessed_objects (object). In FIG. 6, when interfere_accessed_objects (object) is started, the object object is received as an argument (step S21), and it is determined whether or not the object has been processed (step S22).

  If the object has been processed, the process returns to the caller (step S23). If the object has not been processed, a processed flag is set for the object (step S24). Subsequently, it is determined whether or not the object access flag is set (step S25). If the access flag is set, the flag of the argument object for which the access flag is not set by tracing back the interpolated_accessed_objects (object) recursive call stack. (Step S26).

  Subsequently, it is determined whether or not processing has been performed for all pointer fields of the object (step S27). If the access flag is not set in step S25, the process proceeds to step S27.

  If all the pointer fields of the object have been processed in step S27, it is determined again whether or not all the pointer fields of the object have been processed (step S28). S29).

  In step S28, if processing has not been performed for all pointer fields of the object, it is determined whether or not the pointer field is marked (step S30). The bit is set to zero, and interpolate_accessed_objects (object) is called with the object pointed to by the pointer field as an argument (step S31). Then, the process returns to step S28. If there is no mark in step S30, the process returns to step S28.

  In step S27 described above, if all the pointer fields of the object are not processed, it is determined whether or not the pointer field is marked (step S32). If the mark is added, the process returns to step S27. .

  On the other hand, if there is no mark in step S32, interpolate_accessed_objects (object) is called with the object pointed to by the pointer field as an argument (step S33). Then, the process returns to step S27.

  FIG. 7A shows an example of the result of mark_pointer_fields (). Here, it is assumed that the minimum value of distance is used as threshold. The numbers shown in parentheses are examples of depth priority order, and the thick arrows represent pointers that are not marked. In the next interpolate_accessed_objects (), a depth-first search is performed again with priority given to a pointer without a mark. The result is shown in FIG.

  With this algorithm, the access flag of the object 11a can be set. Although the flag of the object 11b cannot be set, access to the object 11b can be detected at a stage described later.

  Subsequently, it is confirmed that an object in the semi-accessible area is not accessed for a long time. Since the above-described method for setting an access flag is approximate, it is necessary to confirm that an object that has moved to a semi-inaccessible area is not accessed for a long time with a high probability. In view of this, the entire semi-inaccessible area is made inaccessible by the page protection mechanism for a period other than GC for a predetermined period.

  If the user program accesses a semi-inaccessible area, control is transferred to the signal handler. Since the accessed virtual memory address can be acquired in the signal handler, the object is identified and an access flag is set. The object for which the access flag is set at the next GC is returned to the normal heap memory area and the flag is cleared.

  FIG. 8 shows a state following FIG. Since the object 11c has been accessed, it is returned to the normal heap memory area. Further, the link relationship of the objects changes during this period, and an object that is pointed only from the semi-inaccessible area 16 may be generated, such as the object 11b shown in FIG. Such an object 11b is moved to the semi-inaccessible area 16 as will be described later.

  Subsequently, the semi-inaccessible area 16 is set as the inaccessible area 15. When the predetermined period has elapsed, the semi-inaccessible area 16 is actually removed from the physical memory as the inaccessible area 15. However, at this time, if objects of a certain threshold number or more from the semi-accessible area 16 have been returned to the normal heap memory area, they are removed from the physical memory and returned to the normal heap memory area. May be.

  First, as a preparation, an object that is pointed only from the semi-inaccessible area 16 is moved to the semi-inaccessible area 16 as shown in FIG. Specifically, the mark is traced by tracing the object from the root set as in the case of GC, but the pointer to the semi-inaccessible area 16 is recorded without being traced. Next, the remaining objects are traced using the pointer to the semi-inaccessible area 16 as a root set, and when an object in the normal heap area that is not marked is found, the object is recursively moved to the semi-inaccessible area 16.

  During the above search and movement, if a pointer pointing to the outside is found from the semi-inaccessible area 16, the alternation 17 is registered in the GC route set. Here, the clone 17 has information of the reference source and reference destination of the corresponding pointer. If there is no reference to the object from the alternation 17, it will be erroneously collected by the GC when it is pointed only from the inaccessible area 15 in the future.

  When the object search and movement are completed, the semi-inaccessible area 16 is set as the inaccessible area 15. There are three options for setting depending on where the contents of the inaccessible area 15 are stored. However, in either case, the GC does not follow the pointer to the inaccessible area 15.

  FIG. 9B shows a case where the inaccessible area 15 is mapped to a low-speed but energy-efficient memory. In this case, when the user program accesses the inaccessible area 15, it can be read and written as it is at a low speed. However, in order to detect reading and writing from the user program, reading and writing may be prohibited by a page protection mechanism.

  When the GC moves an object pointed to by the alternation 17, it is necessary to rewrite the object field in the inaccessible area 15 as the reference source. However, the objects that need to be rewritten are only a part of all the objects in the inaccessible area 15. This setting requires writing to the inaccessible area 15 every time the object is moved, and is not suitable for swapping out to a disk.

  In order to avoid rewriting of an object by GC, one of the two types of settings shown in FIGS. 10A and 10B is used.

  In the setting shown in FIG. 10A, the object pointed to by the alternate 17 is not allowed to move. For this reason, fragmentation of the heap memory area may occur. When mapping the inaccessible area 15 to a low-speed but energy-efficient memory, the user program can be read and written as it is. When swapping out to disk, read / write is prohibited by the page protection mechanism, and when accessed from a user program, it is necessary to temporarily swap in physical memory.

  In the setting shown in FIG. 10B, when the semi-inaccessible area 16 is changed to the inaccessible area 15, the pointer pointing from the inside to the outside is rewritten so as to point to the corresponding alternation 17. Since the position of the alternation 17 in the virtual memory space does not change, it is not necessary to rewrite the object in the inaccessible area 15 even if the object pointed to by the alternation 17 is moved.

  Instead, since the user program cannot read and write the inaccessible area 15 as it is, the page protection mechanism prohibits reading and writing. When there is an access from the user program, it is necessary to temporarily swap in the physical memory and rewrite the pointer correctly using the information of the alternation 17.

  No new object is added to the inaccessible area 15 once set. This is because the existing inaccessible area 15 can be accessed as little as possible. If an object that has not been accessed for a long time is newly detected, a new inaccessible area 15a is set as shown in FIG. Here, with respect to a pointer pointing outside from the new inaccessible area 15a, a part 17 is generated regardless of whether the pointing destination is a normal heap memory or another inaccessible area 15.

  When reading / writing is prohibited in the inaccessible areas 15 and 15a by the page protection mechanism, access from the user program can be monitored. If there is frequent access, all the objects in the inaccessible areas 15, 15a may be returned to the normal heap memory area. An example is shown in FIG. Further, the alternation 17 corresponding to the inaccessible areas 15 and 15a is deleted.

  In this way, in this embodiment, even when a user program accesses, the access speed does not decrease, and when an object is isolated, garbage collection access to the isolated object becomes unnecessary. Thus, the access speed does not decrease. In addition to effectively reducing the physical memory usage, it is possible to detect and isolate an object that is not accessed for a long period of time according to the physical memory usage.

It is a figure which shows the state which isolated the object which is not accessed for a long period of time by the object isolation method by embodiment of this invention. FIG. 2A is a diagram for explaining the movement of an object without increasing the physical memory amount in the object isolation method according to the embodiment of the present invention, and FIG. 2A collects non-accessed objects in one virtual memory page. FIG. 2B is a diagram showing a state, and FIG. 2B is a diagram showing a state in which the virtual memory is moved in a state mapped to the same physical memory. It is a figure which shows a state with an insufficient access flag. It is a flowchart which shows the algorithm which interpolates an access flag using heuristics. It is a flowchart which shows the function of mark_pointer_fields (object). It is a flowchart explaining the function of interpolate_accessed_objects (object). FIG. 6A is a diagram illustrating a result of interpolation of access flags using heuristics. FIG. 6A is a diagram illustrating a result of mark_pointer_fields (), and FIG. 6B is a diagram illustrating a result of interpolated_accessed_objects (). It is a figure which shows the detection by the page protection mechanism of the access with respect to the object in a semi-access impossible area | region. It is a figure for demonstrating the setting of an inaccessible area | region, (a) is a figure which shows the setting of a semi-inaccessible area | region, (b) makes a semi-inaccessible area | region an inaccessible area | region, and is a low-speed but energy efficient memory It is a figure which shows a map. It is a figure which shows the setting of the inaccessible area | region for preventing rewriting by GC, (a) is a figure which shows the example which maps an inaccessible area | region to the memory which is low-speed but energy efficient, (b) is pointed from the alternation It is a figure which shows the example which makes the object which cannot be moved. It is a figure which shows the example which added the inaccessible area | region newly. It is a figure which shows the example which moves the object in an inaccessible area | region to a normal heap memory area. It is a figure which shows a mode that an object is mixed in a virtual memory page.

Explanation of symbols

11, 11a, 11b, 11c, 12 Object 13 Virtual memory page 15 Inaccessible area 16 Semi-inaccessible area 17

Claims (20)

A method for isolating objects that exist in a virtual memory area and are not accessed for a specified period of time, executed by a computer running garbage collection,
A first step of detecting an object that is not accessed for the specified period as a non-access object;
A second step of moving the non-access object to a newly reserved virtual memory area after a predetermined period of time has elapsed after detecting the non-access object;
A third step of preventing the garbage collection from accessing the inaccessible area by setting the newly reserved virtual memory area as an inaccessible area after a predetermined period of time has elapsed after moving to the newly allocated virtual memory area An object isolation method comprising:   2. The object isolation according to claim 1, wherein in the first step, detection is performed by setting an access flag for the object that is considered to be accessed within the specified period, and distinguishing the object from the object that is not accessed. Method.   3. The object isolation method according to claim 2, wherein the first step is started when it is necessary to reduce the amount of use of physical memory.   3. The object isolation method according to claim 2, wherein, in the first step, an access flag is set for the target object for each load / store instruction.   In the first step, an object that caused a cache miss, an object accessed by a load / store instruction that was hit by sampling at regular intervals, an object that was directly pointed to from the register or stack when garbage collection started, Newly generated objects, objects that are in the new generation area when using generational garbage collection, and objects that are in the old generation area but are directly pointing to the new generation area when using generational garbage collection 3. The object isolation method according to claim 2, wherein when at least one of them occurs, the object is accessed.   In the second step, the newly reserved virtual memory area is made a semi-inaccessible area, and after moving the unaccessed object to the semi-inaccessible area, the unnecessary physical memory is released. The object isolation method according to claim 1.   In the third step, if there is no access from a user program to an object in the semi-inaccessible area while a predetermined period of time elapses, the semi-inaccessible area is set as an inaccessible area, 7. The object isolation method according to claim 6, wherein when there is an access from a user program, the object to be accessed is returned to the outside of the semi-inaccessible area.   8. The object isolation method according to claim 7, wherein in the third step, the contents of the inaccessible area are stored in a memory other than a physical memory.   In the third step, an alternate of a pointer pointing out from the inaccessible area is added to a garbage collection root set so that the garbage inaccessible area is not accessed by the garbage collection. The object isolation method according to claim 7.   8. The object isolation method according to claim 7, wherein in the third step, the garbage collection algorithm is changed to prevent access to the inaccessible area. A program for isolating an object that is executed by a computer on which garbage collection runs and that is present in a virtual memory area and is not accessed for a specified period of time,
A first instruction for detecting an object that is not accessed for the specified period as a non-access object;
A second instruction to move the non-access object to a newly reserved virtual memory area after a predetermined period of time has elapsed after detecting the non-access object;
A third instruction for making the newly reserved virtual memory area an inaccessible area and preventing the garbage collection from accessing the inaccessible area when a predetermined period of time elapses after moving to the newly allocated virtual memory area And an object isolation program.   12. The object isolation according to claim 11, wherein in the first instruction, detection is performed by setting an access flag for the object that is considered to be accessed within the specified period and distinguishing the object from the object that is not accessed. program.   13. The object isolation program according to claim 12, wherein the first instruction is started when it is necessary to reduce the amount of use of physical memory.   13. The object isolation program according to claim 12, wherein, in the first instruction, an access flag is set for the target object for each load / store instruction.   In the first instruction, an object that caused a cache miss, an object accessed by a load / store instruction that was hit by sampling at regular intervals, an object that was directly pointed to from the register or stack when garbage collection started, Newly generated objects, objects that are in the new generation area when using generational garbage collection, and objects that are in the old generation area but are directly pointing to the new generation area when using generational garbage collection 13. The object isolation program according to claim 12, wherein when at least one of them occurs, the object is accessed.   In the second instruction, the newly reserved virtual memory area is set as a semi-inaccessible area, and after the object that is not accessed is moved to the semi-inaccessible area, unnecessary physical memory is released. The object isolation program according to claim 11.   In the third instruction, if there is no access from a user program to an object in the semi-inaccessible area while a predetermined period of time elapses, the semi-inaccessible area is set as an inaccessible area, 17. The object isolation program according to claim 16, wherein when there is an access from a user program, the access target object is returned to the outside of the semi-inaccessible area.   18. The object isolation program according to claim 17, wherein in the third instruction, the contents of the inaccessible area are stored in a memory other than a physical memory.   In the third instruction, a copy of a pointer pointing outside from the inaccessible area is added to a root set of garbage collection so that the inaccessible area is not accessed by the garbage collection. The object isolation program according to claim 17.   18. The object isolation program according to claim 17, wherein in the third instruction, the garbage collection algorithm is changed to prevent access to the inaccessible area.

Images