CN102023896A - Dispatcher of Java virtual machine-based concurrent garbage collector - Google Patents

Abstract

The invention belongs to the technical field of Java virtual machine garbage collection, and specifically relates to a scheduler of a Java virtual machine-based concurrent garbage collector. The scheduler of the present invention mainly enables the garbage collection process to be triggered at an appropriate time point by dynamically analyzing the running conditions of the current application program. The scheduler uses a simple time reckoning method to determine whether garbage collection needs to be triggered every time the application requests memory. The scheduler also handles the exhaustion of system memory resources. As a part of the unified framework of concurrent garbage collection, the present invention provides a low-overhead high-performance garbage collection scheduler, optimizes the trigger point of garbage collection, not only improves the operating efficiency of the garbage collector, but also greatly reduces the consumption of system resources to the extent possible.

Description

Scheduler of Concurrent Garbage Collector Based on Java Virtual Machine

technical field

The invention belongs to the technical field of Java virtual machine garbage collection, and in particular relates to a scheduler of a Java virtual machine-based concurrent garbage collector.

Background technique

With the rise of high-level programming languages such as Java, how to make reasonable use of memory has become one of the most critical considerations when providing environmental support for various high-level languages. As the main means of memory utilization, garbage collection technology plays an increasingly important role in system security and resource management.

Concurrent garbage collection (Concurrent GC) has emerged as modern applications use increased amounts of memory, the number of objects increases, and the pauses caused by reducing the "stop the world" garbage collection seriously affect the response time of the application. This technology enables the garbage collector to perform garbage collection while the application thread is executing, that is, the garbage collector and the application thread are executed in parallel. Through tests, the concurrent garbage collection technology has significantly improved operating efficiency compared with the "stop the world" garbage collection, so this concept has begun to be accepted by more and more people.

However, when the concurrent garbage collector is triggered becomes a problem: because if the garbage collection occurs when the system memory is still free, the system memory resources will not be fully utilized and the frequency of garbage collection will be too high, which will affect the application instead. Program performance; if it occurs when the system memory is already relatively tight, the system heap memory is likely to be exhausted before the concurrent garbage collection is completed, which forces the garbage collector to perform "exhaustion processing", and the application needs to be forced to Stopping, which undoubtedly increases the pause time of the application. Especially for programs with large memory requirements, the scheduling method of concurrent garbage collection will have a significant impact on the stability and efficiency of its operation. So how to properly find out the time point of this GC trigger becomes very critical. Of course, for conventional garbage collection techniques (such as "stop the world" garbage collection), a good scheduling method can also significantly improve the operating efficiency of the garbage collector.

Contents of the invention

The purpose of the present invention is to design a scheduler about the concurrent garbage collector that can trigger the concurrent garbage collector at an appropriate time point in order to improve the operating efficiency of the garbage collector and even the entire program, and use the scheduler to collect garbage Threads are dynamically scheduled to make more efficient use of system resources.

The present invention mainly enables the garbage collection process to be triggered at an appropriate time point by dynamically analyzing the running conditions of the current application program. In the implementation of the garbage collector, we record factors such as the current heap memory space occupancy and the memory allocation speed of the application, and estimate the appropriate trigger point of the garbage collector by calculation.

First, define the ideal GC trigger time point, that is, after the garbage collector's tracking process is completed, the system's memory resources are completely exhausted before the cleanup process starts. But obviously, since the concurrent garbage collector is executed at the same time as the application program, the uncertainty of program operation determines that it is impossible for the concurrent garbage collector to reach the ideal GC trigger point, but we can still make the scheduler The selected GC trigger point is as close to this ideal point as possible.

In the present invention, the system information that the scheduler needs to record mainly includes the overall size M ₀ of the heap, the memory consumption situation M ₁ in the current heap (Heap), the average rate V ₁ of the memory consumption of the current application program, and the current garbage The average rate _V2 of processing is tracked by the collector. The most ideal situation is when the time t ₁ required for the tracking process of garbage collection is the same as the time t ₂ when the application program finally exhausts the system memory resources. According to the above conditions, we can get the following three equations:

t ₁ = t ₂ ; ①

t ₁ = M ₁ /V ₂ ; ②

t ₂ = (M ₀ – M ₁ )/V ₁ ;; ③

According to the above three equations, we can calculate the best GC trigger point, that is, whenever the system memory consumption reaches M ₂ , [M ₂ = M ₀ *V ₂ /(V ₁ + V ₂ )], The garbage collector should be triggered to work, because at the end of the garbage collection tracking process, the system's memory is just exhausted, that is, fully used. In other words, in theory, this can approach the optimal GC trigger point as much as possible. However, in actual operation, due to the uncertainty of concurrent programs, such a setting is likely to cause system memory resources to be exhausted before the GC tracking process ends. At this time, once the system resources are exhausted, the garbage collector will be forced to stop the application program for processing, which will reduce the operating efficiency of the application program. The scheduler solves this problem by replacing the total _size of the heap M with a memory usage limit of M ^* . After actual testing, our scheduler uses 90% of the total heap size for memory usage,

M ^* = 0.9 * M ₀ ④

Therefore, the final optimal GC trigger point for the scheduler is

M ⁺ =0.9*M ₀ *V ₂ /(V ₁ +V ₂ ). ⑤

But the system really checks the above data in real time, which will have a significant impact on performance. Therefore, the scheduler in the present invention will only perform the above inspection every time the system requests to apply for new memory, so that the performance impact brought by the real-time inspection can be well reduced. Of course, such processing can also satisfy the correctness of the garbage collector. Because only when the application applies for system memory, the system heap memory will increase, and other events will not cause the system heap memory to change.

On the other hand, in order to minimize the impact on the running of the application without losing accuracy, the scheduler uses a simple time calculation method to determine whether garbage collection needs to be triggered every time the application requests memory.

Finally, although the scheduler can greatly reduce the possibility of system resource exhaustion, considering that the GC thread of the concurrent garbage collector runs at the same time as the application, the time required for operations such as tracking and marking of concurrent garbage collection is uncertain However, system resources may still be exhausted. Therefore, the scheduler also needs to deal with the exhaustion of system memory resources, and the scheduler also provides a solution to deal with resource exhaustion.

The beneficial effects of the present invention are: as a part of the unified framework of concurrent garbage collection (state ⑥), the present invention provides a low-overhead high-performance garbage collection scheduler, optimizes the trigger point of garbage collection, and improves the efficiency of the garbage collector. It also greatly reduces the possibility of system resource exhaustion. At the same time, the scheduler also handles the exhaustion of system resources during concurrent garbage collection.

Description of drawings

Figure 1 shows the state transitions for concurrent garbage collection.

Figure 2 shows the implementation process of the bisection approximation method.

Detailed ways

The basic idea of the present invention is to evaluate a more accurate GC trigger point by dynamically collecting system real-time information and calculating a comprehensive evaluation value. Here we will discuss in detail the information that the scheduler needs to collect and how to evaluate the calculation comprehensively.

1) First define the ideal GC trigger point, that is, after the garbage collector's tracking process is completed, the system's memory resources are completely exhausted before the cleanup process starts. But obviously, since the concurrent garbage collector is executed at the same time as the application program, the uncertainty of program operation determines that it is impossible for the concurrent garbage collector to reach the ideal GC trigger point, but we can still make the scheduler The selected GC trigger point is as close to this ideal point as possible.

In the present invention, the system information that the scheduler needs to record mainly includes the overall size M ₀ of the heap, the memory consumption situation M ₁ in the current heap (Heap), the average rate V ₁ of the memory consumption of the current application program, and the current garbage The average rate _V2 of processing is tracked by the collector. The most ideal situation is when the time t ₁ required for the tracking process of garbage collection is the same as the time t ₂ when the application program finally exhausts the system memory resources. According to the above conditions, we can get the following three equations:

t ₁ = t ₂ ; ①

t ₁ = M ₁ /V ₂ ; ②

t ₂ = (M ₀ – M ₁ )/V ₁ ; ③

According to the above three equations, we can calculate the best GC trigger point, that is, whenever the system memory consumption reaches M ₂ , [M ₂ = M ₀ *V ₂ /(V ₁ + V ₂ )], The garbage collector should be triggered to work, because at the end of the garbage collection tracking process, the system's memory is just exhausted, that is, fully used. In other words, in theory, this can approach the optimal GC trigger point as much as possible. However, in actual operation, due to the uncertainty of concurrent programs, such a setting is likely to cause system memory resources to be exhausted before the GC tracking process ends. At this time, once the system resources are exhausted, the garbage collector will be forced to stop the application program for processing, which will reduce the operating efficiency of the application program. The scheduler solves this problem by replacing the total _size of the heap M with a memory usage limit of M ^* . After actual testing, our scheduler uses 90% of the total heap size for memory usage,

M ^* = 0.9 * M ₀ ④

Therefore, the final optimal GC trigger point for the scheduler is

M ⁺ =0.9*M ₀ *V ₂ /(V ₁ +V ₂ ). ⑤

But the system really checks the above data in real time, which will have a significant impact on performance. Therefore, the scheduler in the present invention will only perform the above inspection every time the system requests to apply for new memory, so that the performance impact brought by the real-time inspection can be well reduced. Of course, such processing can also satisfy the correctness of the garbage collector. Because only when the application applies for system memory, the system heap memory will increase, and other events will not cause the system heap memory to change.

2) In order to further improve the operating efficiency of the application, we have further optimized the scheduler. It is not difficult to see that it is quite redundant to check whether garbage collection is required every time an application requests memory. For example, when a garbage collection has just ended, the remaining memory in the system should be sufficient. The check operation at this time is redundant. The overhead of tracking and scanning the entire heap memory cannot be ignored. In this case, the scheduler replaces the scanning of the heap memory with a simple time calculation, thereby greatly reducing the overhead.

The basic idea of this time calculation is to use the previously collected current system memory usage and the rate at which the application consumes memory to calculate the time when the next garbage collection needs to be performed. For example, at the end of a garbage collection (assuming the current time is t ₀ ), according to the remaining situation M of the heap memory at the end of the garbage collection and the average rate V of memory consumed by the application, then we can calculate the approximate time when the next GC occurs for t ₁ ,

And t ₁ = t ₀ + M/V ⑥

The scheduler considers that the memory application between t ₀ and t ₁ is legal, and does not check it. In this way, the scheduler greatly reduces the number of redundant checks, thereby further improving the operating efficiency of the application.

As in 1), it is necessary to determine the upper limit of memory usage. If you simply use t ₁ calculated in formula ⑥ as the trigger point of the next garbage collection time, it is likely that the system memory will be exhausted before the garbage collection ends. . This requires the garbage collector to additionally handle the system exhaustion situation, which in turn affects the operating efficiency of the application. Therefore, in actual implementation, the scheduler will adopt some conservative strategies to slowly approach the time point of the next garbage collection. There are many such conservative algorithms, and the core idea is to avoid exhaustion of system memory resources at the cost of several more scans. Here we introduce the simpler and more intuitive binary approximation method.

The schematic diagram of the binary approximation method is shown in Figure 2. The scheduler now uses this method to approach the GC trigger point. As in the above case, the scheduler re-detects the heap memory situation at the end of each garbage collection, and records the remaining situation M ₀ of the heap memory after the garbage collection and the average rate V ₀ of memory consumption by the application. What is different from the former is that in order to prevent the system from running out of resources in advance due to the large consumption of memory resources by the application program, the scheduler adopts a binary approach,

That is, t ₁ ^' selected for the first time is:

t ₁ ^' = t ₀ + M ₀ /2V ₀ ⑦

And the t ₂ ^' selected for the second time is:

t ₂ ^' = t ₁ ^' + M ₁ /2V ₁ . ⑧

It is not difficult to see from Equation ⑦ and Equation ⑧ that the scheduler has the following iterative method (Equation ⑨) to approach the final GC trigger point, and only when the memory consumption at the current t _n+1 ^' time exceeds 1) When the introduced memory comes online, the iteration terminates and garbage collection begins. This approach better avoids resource exhaustion in the system before or during garbage collection, because the scheduler checks halfway through the theoretical time of each GC trigger point, which is beneficial to avoid the application The impact of a large amount of memory consumption in a certain period of time.

t _n+1 ^' = t _n ^' + M _n /2V _n . ⑨

(Note: In the above formulas, M ₀ represents the size of the heap at time t ₀ , V ₀ represents the average rate of memory consumption at time t ₀ , and so on, M _n represents the size of the heap at time t _n , V _n represents t _n Average rate of memory consumption over time.)

As shown in Figure 2, at a certain garbage end time t ₀ , the scheduler uses formula ⑨ to calculate time t ₁ , and then ignores the inspection of the heap memory application during the time period from t ₀ to t ₁ . When time t ₁ is reached, first check whether the upper limit of heap memory usage that needs to be garbage collected has been exceeded. If not, continue to iteratively calculate t ₂ , t ₃ , etc. with formula ⑨; if it has been exceeded, t in the figure _{At 4} moments, the iterative process is stopped and garbage collection begins.

According to experiments, it usually takes 5 to 8 iterations to approach the GC trigger point using the dichotomy method, that is to say, only 5 to 8 overall scans of the heap memory are required. However, with the original inspection every time memory is allocated, the number of scans to memory between two garbage collection processes may be hundreds or even thousands of times. Therefore, the scheduler uses time calculation to reduce redundant scanning, which has great positive significance for the operating efficiency of the application.

3) This part will introduce the scheduler's response strategy to the exhaustion of system memory resources. Although the time calculation method mentioned in the above 2) improves the operating efficiency of the application, because it omits a lot of verification of the application memory, it can improve the operating efficiency for applications with unstable memory consumption. Processing in turn increases the possibility of exhausting system memory resources. Therefore, it becomes more important to deal with the exhaustion of system memory resources here. For a mature parallel garbage collector, the exhaustion of system memory resources is itself an important separate module, and the scheduler we implemented integrates the exhaustion of system resources into the scheduler, making the concurrent garbage collector Both triggering and disaster handling are done by the scheduler. Let's briefly talk about the realization idea of system resource exhaustion processing.

According to the time period when system resource exhaustion occurs, the exhaustion situation can be divided into three types:

a) Occurs when the application is running, and the garbage collection thread is not started.

b) Occurs during the tracing phase after the garbage collection thread starts.

c) Occurs in the collection cleanup phase after the garbage collection thread starts.

From the perspective of maximizing the operating efficiency of the application, the scheduler uses the characteristics of concurrent garbage collection to handle these three situations respectively.

a) For the first case, because the garbage collection thread has not started yet, there is no available information, so all the threads can only be stopped and a "stop the world" garbage collection process is performed. Then let the program continue running.

b) When the exhaustion of system resources occurs in the tracking phase after the garbage collection thread starts, the tracking information in the concurrent garbage collection phase can be reused. The scheduler's approach is to stop the threads of other applications, let the garbage collection thread complete the tracking phase, and get the object tracking information first. Then use this object tracking information to do a "stop the world" garbage collection process to free the memory. This saves one tracking process.

c) It is easier to deal with system resource exhaustion in the collection and cleanup phase after the garbage collection thread starts. Because the previous tracking and cleaning processes are still applicable, scheduling only needs to stop the threads of other applications and let the garbage collection thread complete the collection and cleaning phase.

Claims (3)

1. scheduler based on the concurrent garbage collector of Java Virtual Machine, the information that it is characterized in that the scheduler records system comprises the size of population M of heap ₀, the memory consumption situation M in the current heap ₁, current application program the mean speed V of memory consumption ₁, and current garbage collector is followed the tracks of the mean speed V that handles ₂And the time t that needs is handled in the tracking of refuse collection ₁Exhaust the time t of system memory resource at last with application program ₂Identical, promptly obtain following three equatioies:

t ₁?=?t ₂；

t ₁?=?M ₁/V ₂；

t ₂?=?(M ₀?–?M ₁)/V ₁；

So the final best GC triggered time point of scheduler is:

M ^+?=0.9*M ₀*V ₂/(V ₁?+?V ₂)。

2. the scheduler of the concurrent garbage collector based on Java Virtual Machine according to claim 1 is characterized in that described scheduler adopts two fens approximatiosses to approach GC triggered time point, i.e. the time t that chooses for the first time ₁ ^'For:

t ₁ ^’=?t ₀?+?M ₀/2V ₀ ⑦

And the time t that chooses for the second time ₂ ^'For:

t ₂ ^’=?t ₁ ^’?+?M ₁/2V ₁ ⑧

And calculate by following formula:

t _n+1 ^’=?t _n ^’?+?M _n/2V _n ⑨

Above various in, M ₀Expression t ₀The size of moment heap, V ₀Expression t ₀The mean speed of moment memory consumption, by that analogy, M _nExpression t _nThe size of moment heap, V _nExpression t _nThe mean speed of moment memory consumption;

At certain the rubbish t finish time ₀, 9. scheduler calculates t with formula ₁Constantly, ignore t afterwards ₀To t ₁In time period to the check of the application of heap memory; When arriving t ₁In the time of constantly, at first whether check has surpassed the heap memory SC service ceiling that need carry out refuse collection, if also do not surpass, continues with 9. iterative computation t of formula ₂, t ₃If surpass, just stop iterative process, begin to carry out refuse collection work.

3. the scheduler of the concurrent garbage collector based on Java Virtual Machine according to claim 2 is characterized in that described scheduler also comprises system resource is exhausted processing: exhaust the moment section of generation according to system resource, the resource exhaustion situation is divided into 3 kinds:

A) it is in service to occur in application program, and the refuse collection thread is not activated;

B) tracking phase after occurring in the refuse collection thread and starting;

C) the collection clean-up phase after occurring in the refuse collection thread and starting;

Scheduler utilizes the characteristics of concurrent refuse collection, and these three kinds of situations are carried out following processing respectively:

A) for first kind of situation, only all threads are all stopped, do once the garbage collection process of " stopping the world ", allow program continue operation afterwards again;

B) exhaust tracking phase after appearing at the refuse collection thread and starting when system resource, the trace information in so concurrent refuse collection stage gives multiplexing; Scheduler is cut off the thread of other application programs, allows the refuse collection thread that tracking phase is finished, and obtains the object trace information earlier; The garbage collection process of doing once " stopping the world " with this object trace information comes releasing memory afterwards;

C) exhaust the collection clean-up phase that appears at after the refuse collection thread starts for system resource, scheduler is cut off the thread of other application programs, allows the refuse collection thread finish collecting clean-up phase.

Images