Talk about SATB of Garbage Collector

  java, jdk, jvm

Order

This article mainly studies the SATB of Garbage Collector.

CMS, G1 and Shenandoah all adopted SATB technology in concurrent marking.

Shenandoah

Shenandoah’s garbage collector for low-pause-time mainly includes

  • Snapshot-at-the-beginning concurrent markIncluding Init Mark(Pause), Concurrent Mark, Final Mark(Pause)
  • Concurrent evacuation(Brooks Pointers (object version change with additional atomically changed indirectionCopy)
  • Concurrent update references (optional)Including Init update Refs(Pause), Concurrent update Refs, Final update Refs(Pause)

Shenandoah adopted SATB’s technology when carrying out concurrent marking.

SATB

SATB is called Snapshot At The Beginning, and its main points are as follows:

  • Mark’s process is to traverse the heap tag live object, using a three-color tag algorithm, these three colors are white (Indicates that it has not been accessed yet.)、gray(Access to but references it uses have not yet been fully scanned.)、black(References accessed and used have been completely scanned), the whole three-color marking algorithm traverses heap from GC roots, marking white as gray and gray as black; for reachable objects; After the traversal is completed, all reachable objects are black and all white are recyclable.
  • SATB only applies to “snapshot” (marked all reachable at mark startHowever, concurrent modification during concurrent may cause the object to leak marks, such as

    • A white object is newly referenced to black, and then the reference to the white object is deleted from gray object, which will cause the white object to miss the mark.
    • A white object is newly referenced to black, and then a white object referencing the white object is deleted from gray object, which will also cause the white object to miss the mark.
    • A new white object is newly referenced to black, and no other gray object references the white object, which will also cause the white object to leak marks.
  • For the problem of missing marking that may occur when the three-color algorithm is concurrent, SATB marks gray for the target reference object removed from gray object and black for the newly generated object referenced by Black in the marking p hase. Because snapshot is taken at the beginning, there may be Floating Garbage.

Summary

  • CMS, G1 and Shenandoah all adopted SATB technology in concurrent marking. SATB concurrent mark is the first cycle of Shenandoah GC.
  • Traversal heap tag live object, using a three-color tag algorithm, these three colors are white (Indicates that it has not been accessed yet.)、gray(Access to but references it uses have not yet been fully scanned.)、black(References accessed and used have been completely scanned), the whole three-color marking algorithm traverses heap from GC roots, marking white as gray and gray as black; for reachable objects; After the traversal is completed, all reachable objects are black and all white are recyclable.
  • SATB only applies to “snapshot” (marked all reachable at mark start); In the marking phase, the target reference object removed from the gray object is marked gray, and the newly generated object referenced by black is marked black; Because snapshot is taken at the beginning, there may be Floating Garbage.

doc