A preface.
Garbage collection algorithms and garbage collectors are summarized and shared today. As we’ve seen in the previous articles, this knowledge is a prerequisite for Jvm tuning and is the focus of frequent interview questions. To put it bluntly, Jvm tuning is about minimizing Full GC because it’s very time consuming. Full gc is usually triggered when the heap is Full, so we need to keep most objects out of the old age by selecting the garbage collector, adjusting the size of the Jvm memory generation area, and so on, so that they are collected during the Minor GC.
Garbage collection algorithm
There are four garbage collection algorithms in the Jvm: replication algorithm, tag cleaning algorithm, tag collation algorithm, and generational collection algorithm
1. Replication algorithm
Personal habits, above:
As you can see, the copy algorithm takes a chunk of memory and splits it in half. When used, only one of them is used, and when garbage collection is done, the useful objects are copied directly into the other half of memory, and then the previously used half of memory is emptied.
Advantages: High efficiency Disadvantages: Low memory space usage, only half of the available memory, 1 GB only 512 MB.
2. Mark clearing algorithm
Graph:
Our tag removal algorithm is straightforward, which is to mark useless objects and then remove them.
Advantages: Simple disadvantages: ① Low space usage (after several garbage collection, a large number of discontinuous memory fragments will be generated) ② Efficiency problem (if the memory is large and there are many objects to be collected, then marking and collection will be time-consuming)
3. Mark sorting algorithm
Graph:
In fact, the tag decluttering algorithm is similar to the tag clearing algorithm, except that it marks useful objects and then moves those objects towards one end of memory. Not advantages and disadvantages, but certainly, the efficiency is not high copy algorithm.
####4. Generational collection algorithm
This is not really an algorithm, but rather the idea of dividing memory into different areas and using different garbage collection algorithms for those areas. Sub-region refers to the young generation and the old generation. The young generation is divided into 3 blocks, Eden area and 2 survivor areas. In general, the young generation will use the replication algorithm, because there are multiple regions, the replication algorithm is efficient. Since the two survivor zones together only take up 2/10 of the young generation (by default), there is no big problem with space. In the old days, the algorithm of tag sorting or tag clearing is generally adopted.
Garbage collector
There are five common garbage collectors: Serial, Parallel, ParNew, CMS, and G1. The CMS and G1 collectors are the focus of the interview questions. Here I will describe the characteristics of these garbage collectors.
1. Serial garbage collector
Graph:
The Serial garbage collector collects garbage, stops the world (STW), stops all of the user’s worker threads, and then starts a thread to collect garbage. After the collection is complete, the user thread is resumed.
Serial garbage collector can be used in the younger generation as well as the older generation. This is a garbage collector that was used many years ago because it stops the user thread and then leaves only one thread open to collect garbage, which is surprisingly efficient.
If you want to use this garbage collector, you can configure the following parameters: Young generation algorithm: replication algorithm; Parameter of young generation: -xx :+UseSerialGC Old age algorithm: mark collation algorithm; Old age parameter: -xx :+UseSerialOldGC
Parallel garbage collector
Graph:
To optimize the performance of the Serial garbage collector, the Parallel garbage collector emerged. But it doesn’t provide very advanced optimization, and as you can see, the Serial garbage collector process is almost the same, but with a few more threads for garbage collection.
It can be used in the younger generation as well as the older generation
If you want to use this garbage collector, you can configure the following parameters: Young generation algorithm: replication algorithm; Young generation parameter: -xx :+UseParallelGC Old generation algorithm: mark collation algorithm; Old age parameter: -xx :+UseParallelOldGC
ParNew garbage collector
Graph:
There might be some guys who are confused… Ah? Isn’t your graph the same as Parallel collector? Ha ha ha, indeed. The process for the ParNew collector is the same as for the Parallel collector. The difference is that ParNew can only be used in the young generation and, apart from the Serial collector, only ParNew can be used in conjunction with the CMS garbage collector.
If you want to use this garbage collector, you can configure the following parameters: Young generation algorithm: replication algorithm; Young generation: -xx :+UseParNewGC
4. CMS garbage collector (emphasis)
CMS garbage collector, short for Concurrent Mark Sweep. As the name suggests, it’s not simple, concurrent tag clearing. It was the first truly concurrent garbage collector, not that it didn’t stop the world. Rather, it can collect garbage and run applications at the same time. Let’s look at the picture and explain:
This is much more complex than the previous garbage collector, and the entire garbage collection process is divided into five stages: initial marking, concurrent marking, re-marking, concurrent cleaning, and concurrent resetting.
1. Initial tag: Stop the application thread and open a recycle thread tag non-garbage object. It uses the reachability analysis algorithm (described in previous articles), but only marks GC Roots, so it’s very fast. Concurrent flags: The recovery worker thread executes concurrently with the reclaim thread. Then the GC Roots of the previous stage continue to mark down, which takes a long time, almost accounting for 80% of the whole garbage collection process. Since the worker thread has not been stopped, it is possible that marked non-garbage objects become garbage at the next moment. 3. Re-mark: The worker thread is down again. Because the concurrent tagging phase may produce some tagging errors, this phase focuses on fixing the incorrect tagging. For example, the non-garbage object marked in the previous stage has lost reference at this moment and becomes garbage object again. 4. Concurrent cleanup: Restore the worker thread, start the collector thread, and clean up unmarked garbage objects. If the worker thread is restored, a new object will be created. If the new object is not marked, will it be recycled? The answer is definitely not, otherwise no one would dare to use the CMS collector. At this stage newly generated objects are marked directly. 5. Concurrent reset: This stage is very simple, is to remove the previous mark.
As you can see from the above phases, the CMS collector breaks up the entire garbage collection process. This makes the user’s perception less obvious. To magnify this time by tens of hundreds of times, it means… Instead of waiting for 10 seconds at a time, there’s now a total of 10 minutes, one second per minute. Of course.. The garbage collection process is fast, probably taking about a second, but this is just a magnification of the collection time to make it easier to understand.
The important thing to note about the CMS collector is that it can fail concurrently. What is concurrent failure? Because garbage collection and the application are executed concurrently. There is a chance that garbage collection will occur, and the application will continue to generate new objects, causing the old age to fill up and triggering the full GC. At this point, CMS does not go through the previous phase, but uses the first garbage collector described in this article: the Serial collector to collect garbage. So to avoid this, you can use parameters to adjust the percentage of memory that triggers the full GC in the old generation, such as 80%, so that during concurrent cleanup, the application’s new objects will be much less likely to fill up the remaining memory.
CMS collector can only be used in the old era, using the mark clearing algorithm (will produce memory fragments, memory fragments can be sorted through parameter Settings) advantages: scattered garbage collection process, good user experience. Disadvantages: The collection thread grabs CPU resources. Unable to handle floating garbage (garbage generated during concurrent collection) Memory fragmentation (discontinuous memory space) is generated by using the tag clearing algorithm.
CMS core parameters:
- -xx :+UseConcMarkSweepGC: enable the CMS
- -xx :ConcGCThreads: indicates the number of concurrent GC threads
- – XX: + UseCMSCompactAtFullCollection: FullGC compress after finishing
- FullGC – XX: CMSFullGCsBeforeCompaction: how many times after compression, the default is 0, on behalf of each FullGC was followed by compression
- – XX: CMSInitiatingOccupancyFraction: triggered when use the old s reached the proportion FullGC (default is 92, this is the percentage)
- – XX: + UseCMSInitiatingOccupancyOnly: use only set recycling threshold value (the value of a parameter set), if not specified, the Jvm is only used for the first time set data, follow-up will automatically adjust again.
- -xx :+CMSScavengeBeforeRemark: Performs a minor GC before the CMS GC. The purpose is to reduce references from the older generation to the younger generation and reduce the overhead of the CMS GC during the tagging phase, which usually takes 80% of the GC time.
- – XX: + CMSParallellnitialMarkEnabled: said at the time of initial tag multithreaded execution
- -xx :+ CMSPARallelEnabled: Multi-threaded execution during re-marking
- More parameters please baidu ^^
5. G1 garbage collector
On second thought, I’ll write it in the next article. Let’s start with the marking algorithm for the collector.
Garbage collector bottom algorithm – three color marking algorithm
The reachability analysis algorithm is used to mark non-garbage objects. This reachability analysis algorithm has been described in detail. It is used to look down and mark non-garbage objects according to GC roots. So how exactly does this mark work? In fact, the bottom layer is the next to the three-color marking algorithm, as usual, the first picture:
According to the scan integrity of the object, the three-color marking algorithm is divided into black and white colors:
- Black: All member variables of an object have been scanned.
- Gray: The object has been scanned, but not all variables of the object have been scanned.
- White: The object has not been scanned yet.
The diagram above illustrates:
- Object A contains two member variables of object B and object C, and both B and C are scanned, so object A is marked black.
- Object B has no member variables and is marked directly in black
- Object C contains two member variables of object D and object E. However, only D object is scanned, but E object is not scanned, so the color of C object is marked as gray.
- Object E has not been scanned yet, so the initial color is white (it will be scanned later)
- Therefore, the main collection color of garbage collection is white, which is the object that is not marked after the scan of the reachability analysis algorithm.
It looks pretty well designed, but there are a few problems:
We said earlier that the CMS collector is a… A garbage collector that collects threads and application threads executing concurrently will inevitably produce some “floating garbage.” Floating garbage is a phenomenon in which non-garbage objects lose their references and become garbage again after the reachability analysis algorithm marks them because the application threads run synchronously. The CMS cannot completely clean up this part of the object. This phenomenon is also known as **” multi-marking “**.
In fact, there is also a case of undermarking, also known as **” missing marks “**. Multiple marks are fine, but some of the garbage can’t be cleaned up in the current garbage collection and will be fine in the next garbage collection. For missing marks, however, this is a serious problem because our reachability analysis algorithm does not recycle marked objects. So, the missing non-garbage object is recycled… As you can imagine, our program is full of null-pointer exceptions.
How did the missing mark come about? Suppose we have two types of objects, A and B… Look at the picture…
To sum up, missing labeling is due to parallelism between the application thread and the collection thread, which leads to a reference to an unmarked object that has been marked black.
How to solve multiple bids and missed bids?
The Jvm provides two workarounds for multi-marking and missed marking: incremental updates and raw snapshots.
Incremental update: During concurrent collection, objects that reference changes are relabeled so that they are rescanned and marked at the end of the concurrent marking phase and at the beginning of the relabelling phase. Since remarking stops the user thread, there are no white non-garbage objects in memory at the end of the remarking. Note: new objects are marked black directly.
Raw snapshot: During a concurrent collection, every white object that references a change is marked black. This completely avoids missing labels, but may result in a lot of floating garbage.
What about incremental updates and raw snapshots at the bottom?
In fact, the UNDERLYING Jvm uses read and write barriers, which are not in memory. Rather, the idea is aOP-like, with some manipulation done to the reference before and after the reference changes. For example, save it in another form.
Incremental update: Use write barriers to save references before referencing changes. Rescan the root node where the reference object resides during the relabeling phase.
Raw snapshot: Use write barriers to save references until they change. The saved reference object is marked black directly during the re-marking phase.
Different garbage collectors with different underlying implementations:
- CMS uses incremental updates
- The G1 in the next article uses raw snapshots
- And why? This may be due to the scattered memory of G1 and objects in different regions. Incremental updates require higher scanning performance. In the old CMS era, the object referenced by the change will be rescan with incremental update, but the performance cost is much less than G1, and more floating garbage can be disposed of.
Ok, that’s all for today’s summary. If there is something wrong, I still hope you can give me some advice