Marking phase: reference counting algorithm

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.

So how exactly do you mark a dead object in the JVM? Simply put, 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.

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.

  • Advantages: simple implementation, garbage object easy to identify; High judgment efficiency and no delay in recovery.

  • Cons: It requires a separate field to store counters, which increases storage overhead.

Each assignment requires updating the counter, along with addition and subtraction, which adds time overhead. A serious problem with reference counters is that they cannot handle circular references. This is a fatal flaw that prevents such algorithms from being used in the Java garbage collector.

A circular reference

When p’s pointer breaks, internal references form a loop, known as a circular reference, causing a memory leak. As shown in the figure below

For example,

Let’s use an example to test whether a reference counting algorithm is used in Java

/** * Test reference counting algorithm * @author: huangshuai * @create: Public class RefCountGC {private byte[] bigSize = new byte[5*1024*1024]; private byte[] bigSize = new byte[5*1024*1024]; // Object reference = null; public static void main(String[] args) { RefCountGC obj1 = new RefCountGC(); RefCountGC obj2 = new RefCountGC(); obj1.reference = obj2; obj2.reference = obj1; obj1 = null; obj2 = null; Obj1 and obj2 are collected? System.gc(); }}Copy the code

The running results are as follows:

[GC (system.gc ())] [PSYoungGen: 15490K->808K] 15490K->816K, 0.0061980 secs] [Times: User =0.00 sys=0.00, real= 0.36secs] [Full GC (system.gc ()) [PSYoungGen: 808K->0K(76288K)] [ParOldGen: [Times: 328k -> 328K] 328K -> 328K [Times: 328K -> 328K] 328K -> 328K [Times: 328K -> 328K] 328K -> 328K [Times: 328K] User =0.00 sys=0.00, real=0.00 SECS] Heap PSYoungGen Total 76288K, used 655K [0x000000076B500000, 0x0000000770a00000, 0x00000007c0000000) eden space 65536K, 1%, informs [x000000076b500000 0, 0 x000000076b5a3ee8, 0 x000000076f500000) from space 10752 k, 0%, informs [x000000076ff80000 x000000076f500000 0, 0 x000000076f500000, 0) to space 10752 k, 0%, informs [x000000076ff80000 0, 0 x000000076ff80000, 0 x0000000770a00000) ParOldGen total 175104 k, used 672K [0x00000006c1e00000, 0x00000006cc900000, 0x000000076b500000) object space 175104K, 0%, informs [x00000006c1e00000 0, 0 x00000006c1ea8070, 0 x00000006cc900000) Metaspace informs the 3486 k, capacity 4496 k, committed 4864K, reserved 1056768K class space used 385K, capacity 388K, committed 512K, reserved 1048576KCopy the code

We can see that the above behavior of GC collection recycles both objects from the above generation

PSYoungGen: 15490K->808K(76288K)] 15490K->816K(251392K)
Copy the code

If the reference counting algorithm is used, the two objects will not be recycled. Now that both objects are reclaimed, Java does not use a reference counting algorithm for markup. As shown in the figure below

summary

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.

Marking stage: Reachability analysis algorithm

concept

Reachability analysis algorithm: also known as 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 called Tracing Garbage Collection

Train of thought

The “GCRoots “root collection is a set of references that must be active.

Basic idea:

  • The reachability analysis algorithm is a collection of root objects(GCRoots)Is the starting point to search from top to bottom for reachable target objects connected by the root object collection.
  • After using the reachabability 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(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.

What can GC Roots be?

  • Object referenced in the virtual machine stack. For example: parameters, local variables, etc. used in methods called by each thread.

  • Objects referenced by class static properties in the method section of objects referenced by JNI (commonly referred to as local methods) in the local method stack. Example: Java class reference type static variable

  • The object referenced by the constant in the method area. For example, references in the string constant pool

  • All objects held by synchronized

  • Internal references of the Java VIRTUAL machine. Class objects corresponding to basic data types, some resident exception objects (such as Nu11PointerException, outofMemoryError), system Class loaders.

  • Jmxbeans that reflect Java virtual machine internals, callbacks registered in JVMTI, local code caches, and so on.

conclusion

In conclusion, some structures other than heap space, such as virtual machine stack, local method stack, method area, string constant pool, etc. can be used as GC Roots for reachabability analysis

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. For example: generational collection and partial recovery (PartialGC).

If you do garbage collection for only one area of the Java heap (for example: Typical only for new generation), must consider the memory region is a virtual machine implementation details, more is not isolated, sealed the area of the object can be referenced in other parts of the object, then you need will be along with all the associated region object also add to the collection of GC Roots to consider, to ensure the accuracy of the accessibility analysis.

tip

Since Root stores variables and Pointers on a stack, a pointer that holds objects in the heap but is not in the heap itself is Root.

Pay attention to

If a reachability analysis algorithm is used to determine whether memory is retrievable, the analysis must be performed in a consistent snapshot. 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 CMS collectors, which claim to be (almost) non-pausing, are required to pause when enumerating root nodes.

Finalization mechanisms for objects

Java provides an object finalization mechanism that allows developers to provide custom processing logic prior to object destruction. When the garbage collector finds that no reference points to an object, that is, it always calls the object’s finaliza() method before garbage collection. The finaliza() method is overridden in subclasses to release resources when objects are reclaimed, and usually does some resource release and cleanup in this method, such as closing files, sockets, and database connections.

We should never call the Finalize () method of an object. Instead, we should call the finalize() method of an object.

  • infinalize()May cause the object to be resurrected.
  • infinalize()Method execution time is not guaranteed, it is entirely determined by the GC thread, and in extreme cases, if it does not occurGC,finalize()Methods will have no chance of execution.
  • A bad onefinalize()Can seriously affectGCPerformance.

To be or not to be?

If an object is not reachable from all root nodes, it is no longer in use. Generally, objects need to be reclaimed, but in fact, they are not “dead”, and they are temporarily on “probation”. An unreachable object may “resurrect” itself under certain conditions, and if so, it is unreasonable to reclaim it. For this purpose, three possible states of an object in a virtual machine are defined as follows:

  • Accessible: This object can be reached from the root node

  • Resurrectible: All references to objects are released, but objects may be resurrected in Finalize ().

  • Untouchable: When Finalize () of objects is called and there is no resurrection, then finalize() of objects 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, and can only be recycled when objects are unreachable.

The specific process

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

  • The first mark is made if the object objA to GC Roots has no chain of references.

  • Filter to determine if this object needs to be finalize()

    • 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

    • If the object objA overrides the Finalize () method and has not yet executed it, either the objA will be inserted into the F-Queue, automatically created by a virtual machine, and its Finalize () method will be triggered by the low-priority Finalizer thread.

    • The Finalize () method is the last chance for objects to escape death. Later, GC will tag objects in the F-queue a second time. If objA connects with any object in the reference chain in Finalize () method, then on the second tag, objA will be removed from the collection of “to be collected”. If there is no reference chain in the object again, finalize() method will not be called again, and the object will be directly become untouchable state, that is to say, the Finalize () method of an object will be called only once.

Finalize method code demo

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

Clear stage: mark-clear algorithm

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. The three garbage collection algorithms that are common in the JVM today are

  • Mark-sweep algorithm
  • Copying algorithms
  • Mark-compact algorithm

Mark-sweep is a very basic and common garbage collection algorithm, which was proposed by J.McCarthy et al in 1960 and applied to Lisp.

Implementation process

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: Collector traverses from the reference root node, marking all referenced objects. It is usually recorded as reachable in the Header of an object. Mark referenced objects, not garbage!!

  • 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

What is clearance?

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 the garbage location space is enough, if so, store overwrite the original address.

The free list was mentioned when allocating memory for objects

  • If the memory is neat. Memory is allocated by means of pointer collision

  • If the memory is not tidy

    • The virtual machine needs to maintain a list
    • Free list allocation

disadvantages

  • The efficiency of the tag – clearing algorithm is not high
  • During GC, the entire application needs to be stopped and the user experience is poor
  • The free memory cleared in this way is discontinuous, resulting in internal fragmentation and the need to maintain a free list

Cleanup phase: copy algorithm

background

In order to address the shortcomings of mark-sweep algorithms in garbage collection efficiency, M.L. Insky published a famous paper in 1963, Lisp Garbage Collector CA Lisp Garbage Collector Algorithm Using Serial Secondary Storage. The algorithms m.L. Insky described in this paper are known as Copying algorithms, which m.L. Insky himself successfully introduced into an implementation of Lisp.

core idea

The living memory space is divided into two pieces and only one piece is used each 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

After copying reachable objects directly to another area, area A is no longer useful, the objects in it can be deleted directly, in fact, the new generation in it uses the copy algorithm.

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.

disadvantages

  • The disadvantage of this algorithm is also obvious, that is, it requires twice the memory space.
  • forG1This fragmentation became massiveregiontheGCCopying rather than moving meansGCNeed to maintainregionThe object reference relationship between the memory or time is not small

Pay attention to

If there are a lot of junk objects in the system, the number of live objects to be copied by the replication algorithm will not be too large, or very low (in the old days, a large number of live objects will be copied, which will be very inefficient).

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.

Clear stage: mark-tidy algorithm

background

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.

Around 1970, g.L. Steele, C.J.Chene, D.S. Ise and other researchers published mark-compression algorithms. In many modern garbage collectors, mark-compression algorithms or improved versions of them are used.

Implementation process

  • The first stage marks all referenced objects from the root node, as in the mark-clearing 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 difference between clear and rounded

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. This way, 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.

Advantages and disadvantages of integration

advantages

  • Eliminating the fragmentation of memory in the mark-clear algorithm, when we need to allocate memory to a new object,JVMYou only need to hold the starting address of one memory.
  • Eliminates the high cost of halving memory in the replication algorithm.

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. That is:STW

summary

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

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.

Mark clear Tag to sort out copy
rate medium The slowest The fastest
The space overhead Less (but will pile up debris) Less (do not accumulate debris) Usually requires twice as much space as live objects (no shards)
Moving objects no is is

We can find that there is no best algorithm, only the most appropriate algorithm

Generational collection algorithm

None of these algorithms can completely replace other algorithms, they all have their own unique advantages and characteristics. Generational collection algorithm came into being.

The generational collection algorithm is based on the fact that 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.

At present, almost all GC uses generational mobile algorithm to perform garbage collection

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.

  • Characteristics of Young Gen: The area of Young Gen is smaller than that of old generation, with short object life cycle, low survival rate and frequent recycling. 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: The old age is characterized by larger regions, longer life cycles, higher survival rates and less frequent recycling than the young. 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 Serial Old collector based on Mark-Compact algorithm as a compensation measure: When memory collection is poor (due to a Concurrent Mode Failure due to fragmentation), serial Old is used to perform Full GC to defragment old 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 collection algorithm

An overview of the

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.

If processing all the garbage at once requires a long system pause, alternate the garbage collection thread with the application thread. Each time, the 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 heap space into two parts according to the life cycle of the object, and the partition algorithm divides the whole heap space into continuous different cells. 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.