preface
Although CMS has been an ancient garbage collector, and people are now ready to use G1 and ZGC, as far as I know, there are still many companies that mainly use CMS in their production environment, including several large factories I have stayed in.
Therefore, CMS is also the most frequently asked in the JVM interview, including when I ask others about the JVM in my own interview, I also like to start with CMS and gradually go deeper.
Not much nonsense, today we will ask him.
text
1. What is a card table?
Imagine how to judge whether there are references from the old generation to the new generation when YGC is conducted?
A simple solution is to scan the entire old generation, but this cost is too high, so the JVM introduces card tables to solve this problem.
Card lists, also known as card marking, were proposed by Paul R. Wilson and Thomas G. Moher in a paper published in 1989.
The principle is that the space of the elderly is logically divided into several continuous areas of fixed size, and each area divided is called a card. In addition, prepare a corresponding tag bit for each card. The simplest solution is to implement it by byte array, with the card number as the index. The size of each card is usually between 128 and 512 bytes, and generally uses a power byte size of 2. For example, HotSpot uses 512 bytes.
When the reference changes inside the card (pointer write operation), the write barrier will mark the corresponding byte of the card in the card table as dirty.
With the card table, in YGC, only the card marked as dirty in the card table is also used as the scanning range, which can ensure that the entire elderly generation will not be scanned without omission.
2. What is mod union table?
Through the introduction of the card table above, we know that the card table will record the cards of all the objects that have referenced changes in the old age, and CMS needs to record the objects that have referenced changes in the old age for subsequent rescanning in the concurrent marking phase. Can you directly reuse the card table?
The answer is no, because each YGC process involves resetting and rescanning the card table, which meets the requirements of YGC, but destroys the requirements of CMS. The information required by CMS may be reset by YGC. To avoid losing information, a Bitmap called mod union table is added to the card table.
When the CMS concurrency tag is running, every time YGC occurs, when YGC wants to reset a record in the card table, it will update the bit corresponding to the mod union table, which is equivalent to transferring the information in the card table to the mod union table.
In this way, when the final remark is reached, the card table plus the mod union table is enough to record all the reference changes of the old generation in the process of concurrent marking.
3. The process of CMS garbage collection?
There are usually two versions of the CMS garbage collection process online, four step and seven step. Both versions are actually correct.
The four steps should mainly follow the statement of Zhou Zhiming, while the relevant papers of CMS are actually introduced in four steps.
The seven steps should be more derived from the CMS log, and the seven steps actually include the above four steps, which can be understood as the seven steps are more detailed.
Personally, I prefer the seven steps, so here we introduce the next seven steps.
1) Initial Mark
STW (stop the world), traverses GC Roots, and marks the objects that are directly reached by GC Root.
2) Concurrent Mark
From the initial marking stage, the objects marked as alive are taken as the starting point, traversing down to find all alive objects.
At the same time, because the user thread and the GC thread execute concurrently at this stage, the reference relationship between objects is constantly changing. These objects need to be marked again, or errors will occur. In order to improve the efficiency of re marking, the JVM will use a write barrier to mark the card corresponding to the area of the object where the reference relationship changes as dirty, and then only need to scan these dirty card areas to avoid scanning the entire elderly generation.
3) Concurrent Preclean
The significance of this phase is to reduce the time consumption of the Final Remark phase as much as possible, because the Final Remark phase is STW.
In this phase, the main thing is to rescan and mark the area corresponding to the card marked as dirty in the previous phase, and process the objects with reference changes in the concurrency phase.
4) Interruptible Concurrent Abortable Preclean
This phase is basically the same as the concurrent pre-processing, and mainly deals with dirty cards. The difference is that the concurrent preprocessing is only executed once, and this phase will continue to execute circularly until the termination condition is triggered.
The termination conditions are as follows:
The number of cycles exceeds the threshold CMSMaxAbortablePrecleanLoops, which is 0 by default, that is, there is no limit on the number of cycles. The processing time has reached the threshold CMSMaxAbortablePrecleanTime, which is 5 seconds by default. The memory utilization rate of Eden area has reached the threshold CMSScheduleRemarkEdenPenetration, which is 50% by default.
At the same time, this stage has a triggering premise:
The memory usage of Eden area is greater than the parameter CMSScheduleRemarkEdenSizeThreshold, which is 2M by default.
5) Final Remark
STW (stop the world) mainly does two things:
Traverse GCRoots, rescan tags, traverse cards marked as dirty, and rescan tags
6) Concurrent Sweep
Clean up unused objects and reclaim the space they occupy.
7) Concurrent Reset
Reset the data structure (markBitMap) used for marking by CMS algorithm to prepare for the next collection.
4. Problems in CMS
1) The mark clear algorithm used may contain a large number of space debris.
Tuning: enable CMS compression to check whether the parameters are reasonable.
//Enable CMS compression, and perform compression in FGC. The default value is true
-XX:+UseCMSCompactAtFullCollection
//Compress after executing FGC several times, default is 0
-XX:CMSFullGCsBeforeCompaction=0
2) Concurrent cleanup may fail in "Concurrent Mode Failure", which will lead to another Full GC
Tuning: It may be that the proportion of triggering GC is too high, so lower the value appropriately.
//Percentage of CMS triggering GC
-XX:+UseCMSInitiatingOccupancyOnly
-XX:+CMSInitiatingOccupancyFraction=70
3) Very sensitive to CPU resources. In the concurrency phase, the application will slow down and the total throughput will decrease due to the use of a part of threads (or CPU resources). The number of recycling threads started by CMS by default is (number of CPUs+3)/4.
Tuning: The number of concurrent threads may be set too high, so lower the value appropriately.
//Number of CMS concurrent threads
-XX:ConcGCThreads=X
The above tuning is just a suggestion for some problems with high probability. It needs to be analyzed in combination with the scenario and the complete JVM parameters. Each parameter may affect the overall GC efficiency.
5. Why do we need to traverse GCRoots in the Final Remark stage?
This is because the CMS write barrier is not effective for all bytecodes that will lead to reference changes. For example, astore_X (storing the value at the top of the stack to the local variable table) is not supported.
As for why not add a write barrier to astore_X, R thinks that stacks and young generations belong to areas with rapid data changes, and the benefits of using write barriers in these areas are relatively poor.
6. In the Final Remark phase, GC Roots needs to be traversed, so the previous marking work is not in vain?
no, it isn't.
In the three color marking method (see the following introduction), if the scanned object is marked as black, it will be terminated. The previous concurrent marking and pre-processing have completed the marking of most objects, that is, most objects are already black at this time, so the work of the Final Remark stage will actually be reduced a lot. To put it simply, the breadth of traversal remains the same, but the depth becomes shallow.
7. Three color marking algorithm?
The tricolor marking algorithm was proposed by Edsger W. Dijkstra and others in 1978. It is an incremental garbage collection algorithm. Incremental means that changes slowly, that is, GC and mutator (application program) run alternately.
On the contrary, it is a stop type GC, that is, during GC, the mutator stops completely, and then resumes operation after the GC ends.
The tricolor marking algorithm, as its name implies, divides objects in GC into three colors. The meanings of the three colors are as follows:
White: Objects that have not been searched. At the beginning of the recycling cycle, all objects are white. At the end of the recycling cycle, all white objects are unreachable objects, that is, objects to be recycled.
Gray: The object being searched. Objects that have been searched, but the objects referenced by this object have not been searched completely.
Black: Search completed objects. The black object will not point to the white object, and the black object will not be searched again unless the color changes.
Let's take the GC mark clear algorithm as an example to briefly illustrate.
All objects are white before GC starts running. As soon as GC starts running, all objects that can be reached from the root will be marked in gray and then put on the stack. GC has only found such objects, but has not searched them completely, so these objects become gray objects.
Gray objects will be removed from the stack in turn, and their sub objects will also be painted gray. When all its sub objects are painted gray, the object will be painted black. When the GC ends, there are no gray objects. All active objects are black, and garbage is white.
The following is an example dynamic graph of the three color marking algorithm for your reference.
After understanding the three color marking algorithm, turn back to question 5, and see if you can understand it immediately.
8. What are the problems of the three color labeling algorithm?
The tricolor marking algorithm is an incremental garbage collection algorithm. Mutator may change the object reference relationship at any time, so there will be missing labels and wrong labels (multiple labels) under concurrency.
1) Missing mark
Let's take a simple example:
Suppose that when the GC thread executes to time 1, the application thread first executes steps 1 and 2, that is, the scenario of time 3, and the GC thread continues to execute.
At this time, object Z is only referenced by black object X, and black objects will not be scanned further. Therefore, after scanning, Z is still a white object, that is, time 4. At this time, white object Z will be recycled as garbage.
2) Wrong mark (multi mark)
Let's take a simple example:
Suppose that when the GC thread executes to time 1, the application thread executes step 1 first, that is, the scenario of time 2, and the GC thread continues to execute.
At this time, object Z is a gray object. The GC thread searches it and marks it as black after the search, that is, time 3. At this time, object Z does not actually have a reference to GC Roots and should be recycled. However, because it is incorrectly marked as black, it survives in this GC.
Mislabeling and missing labeling are both problems of the three color labeling algorithm, but their consequences are essentially different.
Error marking makes dead objects be regarded as alive, resulting in floating garbage, which does not affect the correctness of the program. These objects can be recycled at the next GC.
Missing labels make the living objects be regarded as dead, which will lead to program errors and unpredictable consequences. This is unacceptable. Therefore, missing labels are a problem that the three color marking algorithm needs to solve.
Through experimental tracking, Wilson found that the missing label problem would occur only when the following two conditions were met at the same time:
1) Write a reference to a white object to a black object
2) Starting from the gray object, all the paths to the white object are destroyed
9. Incremental update and starting snapshot
In order to solve the problem of missing labels in the three color marking algorithm, two well-known solutions have been produced: incremental update and initial snapshot. CMS and G1 adopt these two solutions, the incremental update used by CMS and the initial snapshot used by G1.
The occurrence of missing bid must meet the above two conditions at the same time, so the solution only needs to destroy one of the two conditions.
1) Incremental update
Use a write barrier to intercept all newly inserted reference relationships, record them, and finally use the source of these reference relationships as the root, and scan again to solve the problem of missing labels.
The incremental update breaks condition 1. When inserting a reference from a black object to a white object, the write barrier will record the reference and rescan it later.
Take the missing label above as an example, that is, intercept step 1: X. b=Y. a, record X, and then rescan object X.
2) SATB, snapshot at the beginning
Use the write barrier to intercept all deleted reference relationships and record them. Then, the object pointed to by the deleted reference relationship will be regarded as a live object (not white) and the object will be rescanned.
SATB abstractly means that if an object is alive at the beginning of a GC, it will be treated as a live object in this GC. At this time, the object forms a logical "snapshot", which is the origin of the name of the starting snapshot.
The initial snapshot destroys condition 2. When the reference to the white object is broken, the write barrier will record the reference, treat the object as a live object, and then continue to scan the reference of the object.
Take the missing label above as an example, that is, intercept step 2: Y. a=null, take Z as the live object, and then rescan object Z.
10. The Final Remark phase in CMS is slow. How to analyze and solve it?
In the whole garbage collection process of CMS, there are only two stages: stop the world. One is the initial mark, and the other is the re mark. The initial mark only marks the objects that are directly reached by GC Roots, so it generally does not take too long. However, the re mark takes too long. Usually, if the CMS GC is slow, it is mostly due to the slow re mark stage.
The Final Remark phase is relatively slow. The common reason is that the reference relationship changes frequently in the concurrent processing phase, resulting in many dirty cards and many young generation objects.
It is a common practice to perform a YGC before the Final Remark stage, so that the remaining objects to be marked in the young generation will decrease a lot, and the number of objects regarded as GC root will sharply decrease, so the workload of Final Remark will be much less.
//Attempt to clean before remark. The default value is false
-XX:+CMSScavengeBeforeRemark
Generally, adding - XX:+CMSScavengeBeforeRemark can solve the problem. However, if the optimization is still time-consuming, you need to further see which stage is time-consuming.
Final Remark specifically includes several sub stages: weak refs processing, class unloading, and scrub string table. The time consumption of each sub stage can be seen from the log. According to the time consumption stage, targeted analysis can be carried out again. You can consult the source code or relevant data to help with the analysis.
Take the common weak refs processing as an example:
The weak references here do not only refer to WeakReference, but also include SoftReference, WeakReference, FinalReference, PhantomReference, JNI Weak Reference. Here, all references except strong references are classified as weak.
Therefore, we first add the following configuration to print out more detailed logs related to references during GC.
//Print GC details
-XX:+PrintGCDetails
//Print the time when reference objects are processed during GC (enabled only when PrintGCDetails)
-XX:+PrintReferenceGC
Then, according to the time consumption of each reference, locate the reference type with serious time consumption, and check whether there is unreasonable use of this reference type in the project.
Another simple and crude method is to try to solve the problem by adding parallel processing of references, which usually has good results.
//Enable parallel reference processing. The default value is false
-XX:+ParallelRefProcEnabled
If the scrub string table phase is time-consuming, you can analyze whether there is unreasonable use of connected strings in the project, and others are similar.
