The main goal of concurrent collectors is to reduce GC pause times. They were developed due to the growing demands for reduced application pause time. GC threads run in conjunction with application threads doing most of the GC work before pausing. Truly concurrent collectors are very hard to achieve as mutator threads keep modifying the state of the heap. Thus concurrent collectors are generally mostly concurrent implementation. A Collector is termed "mostly/partly concurrent" where the majority of the garbage collection work is done in conjunction with application execution. Mostly/partly concurrent collectors do require stop-the-world pauses to do a small portion of their work some of its work.
There are two main aspects to concurrent collectors, i.e. concurrent marking and concurrent compaction. Initial implementations of concurrent collector just did concurrent marking and sweeping. Compaction was either ignored (CMS) or was done using a stop the world pause (G1GC). Newer algorithms such as Shenandoah, ZGC do both concurrent marking as well as concurrent collection. None the less both these algorithms still employ minor STW pauses.
Central to all concurrent collectors is tricolor marking. Tricolor marking has one important advantage: it can be performed without the need to halt the system for significant periods of time. The algorithm works as follows:
- A GC cycle starts off by marking all GC root objects as gray while all other objects are marked as white.
- The GC marking thread randomly selects a gray node and inspects its children.
- All children are colored gray.
- Once all its children are colored gray, it then colors itself black.
- The above process is repeated until there are zero gray nodes. When there are zero gray nodes, the scan is complete.
- All black nodes are live objects and must not be collected.
- All white nodes are dead objects and are eligible for collection
The simple mark-and-sweep algorithm cannot work with concurrent algorithms. Mark-and-sweep algorithms essentially assign objects two states or colors (dead or alive). Incremental or concurrent approaches require three colors to help identify the states of objects and to identify changes in object reachability. The tri-color algorithm enables the system to collect garbage periodically rather than when needed. Essentially, tri-color marking enables us to identify white nodes (dead objects) that are not attached to black nodes during the course of a garbage collection cycle.
A central problem with all concurrent collectors is that garbage collection (GC) and mutator threads may create race conditions because both threads are competing for the same object. For example, the GC may be moving an object whose reference is being modified by the application. In order for tri-color incremental/concurrent GC to work, mutator threads must coordinate with the GC collector to identify unreachable objects that have become reachable. GC and mutator threads coordinate via read and/or write barriers. A read or write barrier is simply a small piece of code that the Java Virtual Machine (JVM) injects into application code. This piece of code simply performs a task when an object is accessed or updated. In the case of tri-color marking, a read barrier detects when a white object is read and immediately colors it gray. A write barrier traps modifications to an object reference and processes it appropriately. There are two main approaches to write barriers:
- Snapshot-at-the-beginning (SATB) - The SATB algorithm works on a heap snapshot. The SATB algorithm ensures that no object pointers are destroyed while the collector is traversing the object graph. All pointer modifications are stored in buffers to determine if a white object should be collected.
- Incremental update - This write barrier turns a black object into a gray object if it modifies any of its pointers. This gray object will be re-scanned before the collection is complete. Unlike SATB, no extra data structures are required to track reference modifications. Now that we have covered the basics, let's dig into various concurrent collector implementations. There are a number of mostly concurrent collector implementations.
No comments yet.