In-depth understanding of JVM (xii) – garbage collection related algorithms

Mark phase

Almost all Java object instances are stored in the heap, and before the GC can perform garbage collection, it first needs to distinguish between alive and dead objects in memory. Only objects marked as dead are freed by GC during garbage collection, so this process can be referred to as the garbage marking phase.

An object is declared dead when it is no longer referenced by any living object. There are two ways to judge the survival of objects: reference counting algorithm and reachability analysis algorithm.

Reference counting algorithm

  • The Reference Counting algorithm is relatively simple and stores a Reference counter attribute of an integer for each object. Used to record when an object is referenced.

  • For an object A, if any object references A, then A’s reference counter is incremented by 1. When a reference is invalid, the reference counter is decayed by one. As long as the reference counter of object A has A value of 0, it indicates that object A can no longer be used and can be reclaimed.

  • Java does not choose a reference counting algorithm

The advantages and disadvantages

  • Advantages:
    • The implementation is simple and the garbage object is easy to identify. High judgment efficiency and no delay in recovery.
  • Disadvantages:
    • It requires separate fields to store counters, which adds to the storage overhead.
    • Each assignment requires updating the counter, along with addition and subtraction, which adds time overhead.
    • Reference counters have a serious problem, namelyCircular references cannot be handled. This is a fatal flaw that prevents such algorithms from being used in the Java garbage collector.

A circular reference

The p pointer is broken, but because some objects have circular references, the counter is not zero and the circular object cannot be reclaimed.

Usage scenarios

  • Reference counting algorithms are the recycle of choice for many languages, such as Python, which has become more popular due to artificial intelligence, and supports both reference counting and garbage collection.

  • Which is optimal depends on the scenario, and there are large-scale attempts to retain only reference counting mechanisms in practice to improve throughput.

  • Java did not choose reference counting because of the basic difficulty of handling circular reference relationships.

  • How does Python solve circular references?

    • Manual dereference: It is well understood that when appropriate, the dereference relationship.
    • Use weakreference WeakRef, a standard library provided by Python that is designed to address circular references.

Accessibility analysis algorithm

  • Reachable analysis (or root search algorithm, traceable garbage collection)

  • Compared with reference counting algorithm, reachability analysis algorithm not only has the characteristics of simple implementation and efficient execution, but also can effectively solve the problem of cyclic reference in reference counting algorithm and prevent the occurrence of memory leakage.

  • In contrast to the reference counting algorithm, the reachability analysis is chosen by Java and C#. This type of Garbage Collection is often referred to as Tracing Garbage Collection.

  • A collection of GC Roots is a set of references that must be active.

The basic idea

  • The reachability analysis algorithm takes GC Roots as the starting point and searches whether the target object connected by the root object set is reachability from top to bottom.
  • After using the reachability analysis algorithm, the living objects in memory are directly or indirectly connected by the root object set, and the path searched is called the Reference Chain.
  • If the target object is not connected by any reference chain, it is unreachable, which means that the object is dead and can be marked as a garbage object.
  • In the reachability analysis algorithm, only the objects that can be connected directly or indirectly by the root object set are the viable objects.

GC Roots

In the Java language,GC Roots includes the following classes of elements:

  • Object referenced in the virtual machine stack
    • For example: parameters, local variables, etc. used in methods called by each thread.
  • Objects referenced by JNI (commonly referred to as local methods) in the local method stack
  • The object referenced by the class static property in the method area
    • Example :Java class reference type static variable
  • The object referenced by the constant in the method area
    • For example, a reference in the String constant pool (String Table)
  • All objects held by synchronized
  • Internal references of the Java VIRTUAL machine.
    • For example, Class objects corresponding to basic data types, some resident exception objects (NullPointerException, OutOfMemoryError), and system Class loaders.
  • Jmxbeans that reflect Java virtual machine internals, callbacks registered in JVMTI, local code caches, and so on.
  • In addition to these fixed COLLECTION of GC Roots, other objects can be added “temporarily” to form a complete collection of GC Roots, depending on the garbage collector selected by the user and the memory region currently reclaimed. Examples are: Generational collection and Partial GC
    • If you do garbage collection for only one area of the Java heap (for example, typically only for the new generation), you must consider that the memory area is an implementation detail of the virtual machine itself, and not isolated.The objects in this region are completely likely to be referenced by objects in other regions, so it is necessary to add the associated region objects into GC Roots to ensure the accuracy of the accessibility analysis.

One of The causes of Stop The World

  • If the reachability analysis lead algorithm is used to determine whether memory can be reclaimed, the analysis must be performed in a snapshot that guarantees consistency. If this is not satisfied, the accuracy of the analysis results cannot be guaranteed.
  • This is also an important reason why GC must “Stop The World”.
    • Even in CMS collectors, which claim to be (almost) pauses free,You must also pause when enumerating the root node.

Finalization mechanisms for objects

  • The Java language provides an object finalization mechanism that allows developers to provide custom processing logic for objects before they are destroyed.
  • When the garbage collector finds that there is no reference to an object, that is, before garbage collection of the object, the Finalize () method of the object is always called.
  • The Finalize () method allows to be overridden in subclasses for resource release when objects are reclaimed. This method usually does some resource freeing and cleaning, such as closing files, sockets, and database connections.
  • Never actively call a Finalize () method of an object. Instead, let the garbage collector call it. There are three reasons:
    • Objects may be resurrected when finalize(). (Chapter 11: Concepts related to garbage Collection)
    • The execution time of Finalize () method is not guaranteed. It is completely determined by GC thread. In extreme cases, if GC does not happen, Finalize () method will have no chance to execute.
    • A bad Finalize () can seriously impact GC performance.
  • In terms of function, finalize() method is similar to the destructor in C++, but Java adopts automatic memory management mechanism based on garbage collector, so finalize() method is fundamentally different from the destructor in C++.
  • Objects ina virtual machine generally have three possible states, thanks to finalize().

Three states

If an object is unreachable from all root nodes, it is no longer in use. In general, this object needs to be reclaimed. But in fact, they are not necessarily dead. They are on probation. An unreachable object may “resurrect” itself under certain conditions, and if so, it is unreasonable to reclaim it. To this end, define three possible states for an object in a virtual machine. As follows:

  • palpable: The object can be reached from the root node.
  • Can the resurrection: All references to objects are released, but objects may be resurrected in Finalize ().
  • untouchableWhen the finalize() of: object is called and is not resurrected, it will enter the untouchable state. Untouchable objects cannot be resurrected, because Finalize () will only be called once.

The above three states are distinguished by finalize() method. Objects can only be reclaimed if they are not reachable.

Determines whether an object is recyclable

To determine whether an object objA is recyclable, we must go through at least two marking processes:

  1. If the object objA to GC Roots has no chain of references, proceedFirst mark.
  2. Filter to determine if this object needs to be finalize()
    1. If the object objA does not override the Finalize () method, or if the Finalize () method has already been called by a virtual machine, then the virtual machine considers it “unnecessary to execute” and objA is judged untouchable.
    2. If the object objA overrides the Finalize () method and has not yet executed it, then the object will be inserted into the F-Queue and its Finalize () method will be triggered by a low-priority Finalizer thread automatically created by the virtual machine.
  3. The Finalize () method is the last chance for objects to escape death, which is later performed by Gc on objects in the F-queueSecond mark. If objA is linked to any object in the reference chain in the Finalize () method, then on the second markup, objA is removed from the “to be collected” collection. After that, the object will again have no references. In this case, the Finalize method will not be called again, and the object will directly become the untouchable state, that is to say,The Finalize method of an object will only be called once.

Finalize () method test

/** * Tests the Finalize () method of the Object class, the finalization mechanism for objects. * /
public class CanReliveObj {
    public static CanReliveObj obj;// Class variable, belonging to GC Root


    // This method can only be called once
    @Override
    protected void finalize(a) throws Throwable {
        super.finalize();
        System.out.println("Call finalize() method overridden by the current class");
        obj = this;// The current object to be collected is linked to obj, an object on the reference chain, in finalize()
    }


    public static void main(String[] args) {
        try {
            obj = new CanReliveObj();
            // The object successfully saves itself for the first time
            obj = null;
            System.gc();// Call the garbage collector
            System.out.println("First GC");
            // Because the Finalizer thread has a low priority, pause for 2 seconds to wait for it
            Thread.sleep(2000);
            if (obj == null) {
                System.out.println("obj is dead");
            } else {
                System.out.println("obj is still alive");
            }
            System.out.println("Second GC");
            // The following code is exactly the same as the above, but the self-rescue fails
            obj = null;
            System.gc();
            // Because the Finalizer thread has a low priority, pause for 2 seconds to wait for it
            Thread.sleep(2000);
            if (obj == null) {
                System.out.println("obj is dead");
            } else {
                System.out.println("obj is still alive"); }}catch(InterruptedException e) { e.printStackTrace(); }}}Copy the code

The results

GC Roots tracing of MAT and JProfiler

dump

Two heap files were exported at different stages to compare GC Roots

public class GCRootsTest {
    public static void main(String[] args) {
        List<Object> numList = new ArrayList<>();
        Date birth = new Date();

        for (int i = 0; i < 100; i++) {
            numList.add(String.valueOf(i));
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println("Data added, please do:");
        //1. Dump dump
        new Scanner(System.in).next();
        numList = null;
        birth = null;

        System.out.println("NumList, birth have been null, please operate:");
        Dump dump dump dump dump dump dump dump
        new Scanner(System.in).next();

        System.out.println("The end"); }}Copy the code
  1. Export the dump file using commands

Jmap-dump :format=b,live,file= File name Process ID

  1. Export dump files using JVisualVM

  • The captured heap dump file is a temporary file that is automatically deleted when JVisualVM is shut down. To save it, you need to save it as a file.

  • Heap dump can be captured by:

    • In the Application subwindow on the left, right-click the Application and select Heap Dump.
    • Click the Heap Dump button in the Monitor subtab.

  • Heap DUMPS for the local application opens as a subtab of the application TAB. Also, the heap dump corresponds to a time-stamped node in the Application (Application) column on the left. Right click on this node and select Save as to save the heap dump locally.

Idea install VisualVM, Jprofiler, jclasslib

MAT

MAT, short for Memory Analyzer, is a powerful Java heap Memory Analyzer. Used to find memory leaks and view memory consumption.

MAT is based on Eclipse development, is a free performance analysis tool download

  1. MAT Displays commands to export dump files

Check that the number of GC Roots collection objects of main thread 1 is 21

Check the number of GC Roots set objects of main thread 2 is 19

  1. MAT view JVisualVM export dump file

Check that the number of GC Roots collection objects of main thread 1 is 21Check the number of GC Roots set objects of main thread 2 is 19

JProfiler

View the entire GC Roots call chain for an object in isolation

Check the oom

/** * -Xms8m -Xmx8m -XX:+HeapDumpOnOutOfMemoryError */
public class HeapOOM {
    byte[] buffer = new byte[1 * 1024 * 1024];//1MB

    public static void main(String[] args) {
        ArrayList<HeapOOM> list = new ArrayList<>();

        int count = 0;
        try{
            while(true){
                list.add(newHeapOOM()); count++; }}catch (Throwable e){
            System.out.println("count = "+ count); e.printStackTrace(); }}}Copy the code

Operation parameters: – Xms8m – Xmx8m – XX: + HeapDumpOnOutOfMemoryError

– XX: + HeapDumpOnOutOfMemoryError: OOM when export heap snapshot file path to the current project. Opened by JProfiler

An ArrayList object was found to have eaten most of the memory

Check the main thread error cause and location

Sweep phase

After successfully separating live and dead objects in memory, the next task of the GC is to perform garbage collection to free up the memory space occupied by the unused objects so that there is enough available memory to allocate memory for the new objects.

Three garbage collection algorithms that are common in JVMS today are Mark-sweep, Copying, and Mark-compact

Mark-sweep algorithm

When available memory in the heap is exhausted, the entire program (also known as stop the world) is stopped and two tasks are performed, the first is marked and the second is cleared.

  • Tag: The Collector starts by referencing the root node and marks all referenced objects (not garbage objects). It is usually recorded as reachable in the Header of an object.

  • Cleanup: The Collector traverses the heap memory linearly from beginning to end and reclaims an object if it is not marked as reachable in its headers.

disadvantages

  • Not very efficient
  • During GC, the entire application needs to be stopped, resulting in a poor user experience
  • The amount of free memory cleared up in this way is discontinuous,Generate memory fragmentation. A free list needs to be maintained

Clear meaning

This does not mean that the object addresses need to be cleared are stored in the free address list. The next time a new object needs to be loaded, determine whether there is enough space for garbage, and if so, store it.

Copying algorithms

An algorithm was proposed to solve the memory fragmentation defect of Mark-Sweep algorithm

The living memory space is divided into two parts, and only one part is used at a time. During garbage collection, the living objects in the used memory are copied to the unused memory block. After that, all objects in the used memory block are cleared, the roles of the two memory blocks are swapped, and finally garbage collection is completed.

The high efficiency of the replication algorithm is based on the premise of fewer live objects and more garbage objects.

The advantages and disadvantages

  1. Advantages:
  • No marking and cleaning process, simple implementation, efficient operation
  • After copying the past to ensure the continuity of space, there will be no “fragmentation” problem.
  • If there are many junk objects on the system, the number of live objects that the replication algorithm needs to copy is not very large (fewer objects copied, shorter STW).
  1. Disadvantages:
  • It takes twice as much memory.
  • For GC with a large number of regions, such as G1, replication rather than movement means that the GC needs to maintain object reference relationships between regions, which is not a small amount of memory or time.

Application Scenarios:

In the new generation, garbage collection for conventional applications can typically reclaim 70 to 99 percent of memory space at a time. Recycling is cost-effective. So now commercial virtual machines are using this collection algorithm to recycle the new generation. The From and To areas are replication algorithms

Mark-compact algorithm

The high efficiency of the replication algorithm is based on the premise of fewer live objects and more garbage objects. This happens a lot in the new generation, but in the old age, it’s more common for most objects to be living objects. If the replication algorithm is still used, the cost of replication will be high due to the large number of living objects. Therefore, due to the nature of old-time garbage collection, other algorithms need to be used.

It is true that the tag-one cleanup algorithm can be used in the old days, but it is not only inefficient, but also generates memory fragmentation after a collection is performed, so JVM designers need to improve on this. The mark-compact algorithm was born.

Execution process:

  • The first stage marks all referenced objects, starting from the root node, as in the mark-clear algorithm

  • The second phase compresses all living objects to one end of memory and discharges them in sequence. After that, clean up all the space outside the boundary.

The end result of the mark-sweep-compact algorithm is the same as the memory defragmentation once the mark-sweep-compact algorithm is complete, so it can also be called a Mark-sweep-compact algorithm.

The essential difference between them is that the mark-sweep algorithm is a non-mobile recovery algorithm, while the mark-compression algorithm is mobile. Whether or not to move a reclaimed live object is a risky decision with both advantages and disadvantages.

As you can see, marked living objects are sorted by memory address, while unmarked memory is cleaned up. When we need to allocate memory for new objects, the JVM only needs to hold the starting address of memory, which is significantly less overhead than maintaining a free list.

The advantages and disadvantages

  1. Advantages:
  • Eliminating the fragmentation of memory in the mark-clean algorithm, the JVM only needs to hold the starting address of memory when allocating memory to a new object.
  • Eliminates the high cost of halving memory in the replication algorithm.
  1. Disadvantages:
  • In terms of efficiency, the mark-collation algorithm is lower than the copy algorithm.
  • When you move an object, you need to adjust the address of the reference if it is referenced by another object. You need to pause the user application throughout the movement. Namely: STW

Comparison of three algorithms

indicators Mark-sweep Copying algorithms Mark-compact
speed medium The fastest The slowest
The space overhead Less (but will pile up debris) Usually twice the size of a live object (no shards) Less (do not accumulate debris)
Moving objects no is is

In terms of efficiency, the replication algorithm is the leader, but it wastes too much memory. (Space conversion efficiency)

In order to take into account the three indicators mentioned above, the mark-collation algorithm is relatively smoother, but its efficiency is not satisfactory. It has one more mark stage than the copy algorithm, and one more memory collation stage than the mark-clean algorithm.

Generational Collecting

Different objects have different life cycles. Therefore, objects with different life cycles can be collected in different ways to improve collection efficiency. Typically, the Java heap is divided into the new generation and the old generation, so that different collection algorithms can be used according to the characteristics of each generation to improve the efficiency of garbage collection.

In the running process of Java programs, a large number of objects will be generated, some of which are related to business information, such as Session objects, threads and Socket connections in Http requests. Such objects are directly linked to business, so their life cycle is relatively long. But there are some objects, mainly temporary variables generated in the process of running the program, the life cycle of these objects will be relatively short, such as: String object, because of its invariable class characteristics, the system will produce a large number of these objects, some objects can even be recycled only once.

Almost all current GCS perform garbage collection using Generational collection algorithms.

In HotSpot, based on the concept of generation, the memory reclamation algorithm used by GC must combine the characteristics of both the young generation and the old generation.

  • Young Gen
    • Characteristics of the young generation: the area is smaller than that of the old generation, the object life cycle is short, the survival rate is low, and the recycling is frequent.
    • In this case, the recovery of the replication algorithm is the fastest. The efficiency of the replication algorithm depends only on the size of the current living object, so it is suitable for young generation recycling. The problem of low memory utilization of the replication algorithm is alleviated by the two survivor designs in hotspot.
  • Tenured Gen
    • Characteristics of the old age: large area, long life cycle of objects, high survival rate, recycling less frequent than the young generation.
    • In this case, there are a large number of objects with high survival rates, and the replication algorithm becomes obviously unsuitable. It is usually implemented by mark-clean or a mixture of mark-clean and mark-clean.
      • The cost of the Mark phase is proportional to the number of viable objects.
      • The overhead of the Sweep phase is positively related to the size of the area managed.
      • The overhead of the Compact phase is proportional to the data of the living object.

Take the CMS collector in HotSpot as an example. CMS is implemented based on Mark-sweep and has a high recycling efficiency for objects. For the fragmentation problem, CMS uses the Serial Old collector based on the Mark-Compact algorithm as a compensation measure: when the Concurrent Mode Failure caused by fragmentation occurs, Serial Old will be used to perform Full GC to defragment older memory.

The generational idea is widely used by existing virtual machines. Almost all garbage collectors distinguish between the new generation and the old generation.

Incremental Collecting

With the existing algorithm, the application will be in a stop the World state during garbage collection. In the Stop the World state, all threads of the application are suspended, suspending all normal work and waiting for the garbage collection to complete. If garbage collection takes too long, the application will be suspended for a long time, which will seriously affect user experience or system stability.

In order to solve this problem, the research on real-time garbage collection algorithm directly led to the birth of Incremental Collecting algorithm.

The basic idea

  • If processing all the garbage at once requires a long pause in the system, you can alternate between the garbage collection thread and the application thread. Each garbage collection thread collects only a small area of memory space and then switches to the application thread. Repeat until garbage collection is complete.

  • In general, incremental collection algorithms are still based on traditional mark-sweep and copy algorithms. Incremental collection algorithms allow garbage collection threads to mark, clean, or copy in a phased manner by properly handling conflicts between threads.

disadvantages

Using this approach reduces system downtime because application code is also intermittently executed during garbage collection. However, the overall cost of garbage collection increases due to the consumption of thread switches and context transitions, resulting in a decrease in system throughput.

Partitioning algorithm

In general, under the same conditions, the larger the heap space, the longer the time required for a GC and the longer the pauses associated with GC. To better control the pauses generated by GC, reduce pauses generated by a GC by splitting a large memory area into smaller chunks and reasonably reclaiming several cells at a time, rather than the entire heap space, based on the target pause times.

The generation algorithm divides the whole heap space into two parts according to the life cycle of the object. Contiguous intersections. Each area is used independently and recycled independently. The advantage of this algorithm is that it can control how many cells are recycled at a time.

Pointer collisions and free lists

The choice of how to allocate object allocation memory depends on whether the Java heap is clean or not, which in turn depends on whether the garbage collector used has collation capabilities.

Bump the Pointer

If the memory space is distributed in a regular and orderly manner, that is, the used and unused memory are on opposite sides of each other with a marker pointer that records the starting point of the next allocation. When allocating memory for a new object, it is only necessary to change the offset of the pointer to allocate the new object to the first free memory location. This is called Bump the Pointer

Free List

The virtual machine maintains a list of memory blocks that are available, finds a large enough space from the list to allocate to object instances, and updates the list. This method of allocation is called the Free List.

In-depth understanding of the JVM family

  • 1. In-depth understanding of the JVM (I) – Introduction and architecture
  • 2. In-depth understanding of the JVM II – 1 classloader subsystem
  • 3. In-depth understanding of THE JVM (III) – Runtime data area (virtual machine stack)
  • 4. In-depth understanding of THE JVM (IV) – runtime data area (program counter + local method stack)
  • 5. In-depth understanding of THE JVM (V) – Runtime data area (heap)
  • 6. In-depth understanding of THE JVM (VI) – Runtime data area (methods area)
  • 7. In-depth understanding of the JVM (vii) – execution engine (interpreter and JIT compiler)
  • 8. An in-depth understanding of the JVM (8) – string constant pool
  • 9. In-depth understanding of JVM (IX) – object instantiation and memory layout
  • 10. In-depth understanding of JVM (x -) – bytecode level profiler execution
  • 11. In-depth understanding of concepts related to JVM (xi) garbage collection