1. Overview of garbage collection algorithms

  • Mark-clear algorithm: mark unwanted objects, and then clear and reclaim them. Disadvantages: inefficient, unable to remove garbage debris.
  • Copy algorithm: according to the capacity of two equal size of the memory area, when a piece of used up when the living object will be copied to another piece, and then the used memory space once clean up. Disadvantages: Low memory usage, only half of the original.
  • Mark-tidy algorithm: Mark useless objects, move all living objects to one end, and then directly clear memory outside the end boundary.
  • Generation algorithm: The memory is divided into several blocks according to the different life cycle of the object, generally the new generation and the old age. The new generation basically adopts the replication algorithm, and the old age adopts the tag sorting algorithm.

2. Recycle algorithm principle

2.1 Tag clearing algorithm

The algorithm is divided into two stages: “marking” and “clearing” : first, all the objects to be reclaimed are marked, and all the marked objects are reclaimed uniformly after the completion of marking.

Major deficiencies:

  1. One is the efficiency problem, both marking and clearing processes are not efficient;
  2. One is the problem of space. After the flag is cleared, a large number of discontinuous memory fragments will be generated. Too much space debris may cause that when a large object needs to be allocated during the program running, enough continuous memory cannot be found and another garbage collection action will have to be triggered in advance.

The execution of the mark-clear algorithm is shown in the figure below

2.2 Replication Algorithm

In order to solve the defects of mark-Sweep algorithm, Copying algorithm was proposed. It divides the available memory into two equal sized chunks by capacity, using only one chunk at a time. When the memory of this piece is used up, the objects that are still alive are copied to another piece, and then the used memory space is cleared up once, so that memory fragmentation is not easy to occur. The specific process is shown in the figure below

The main deficiency

This solves the memory fragmentation problem, but comes at a high cost in terms of memory usage, as half of the available memory is wasted.

2.3 Tag sorting algorithm

In order to solve the defects of Copying algorithm and make full use of memory space, the Mark-Compact algorithm was proposed. The algorithm performs the same marking phase as Mark-Sweep, but instead of cleaning up the retractable objects directly after marking, it moves all the living objects to one end and then cleans up the memory beyond the end boundary. The specific process is shown in the figure below:

The main deficiency

  • Advantages: Solves the memory fragmentation problem of the mark-clean algorithm.
  • Disadvantages: Local object movement is still required, which reduces efficiency to some extent.

2.4 Generational collection algorithm

Current garbage Collection on commercial virtual machines is based ona “Generational Collection” algorithm, which is nothing new except that it divides memory into chunks based on the lifetime of the object. Generally, the Java heap is divided into new generation and old generation, so that the most appropriate collection algorithm can be adopted according to the characteristics of each generation.

  • In the new generation, when a large number of objects die and a small number survive each garbage collection, a replication algorithm can be used to complete the collection at the cost of copying a small number of surviving objects.
  • In the old days, because the object had a high survival rate and there was no extra space to guarantee its allocation, it had to be reclaimed using the mark-collate algorithm.