An Overview on Garbage Collector Algorithms

Before we move into the details of algorithms that are used in Java Virtual Machine (JVM), let’s have a common understanding of what GC Roots are. These are the objects which are directly accessible from outside the heap memory.
(1) Active Threads
(2) Static Variables
(3) Local Variables (Accessible via Stack of a Thread)
(4) JNI References

There are three basic types of algorithms that are used in Java Virtual Machine (JVM):-
(1) Mark-sweep
(2) Mark-sweep-compact
(3) Mark-copy

Mark:- All of the algorithms discussed have the same mark phase. Marking phase is about traversing the whole object graph, starting from GC Roots. When GC visits the object, it marks it as accessible and thus alive. All the objects which are not reachable from GC Roots are garbage. Marking requires Stop-The-World (STW) pauses, because the running application threads could interfere. How long the STW pause is, depends mostly on the number of visited objects.

Mark-Sweep:-After marking phase, we have the memory space which is occupied by visited (accessible via GC Roots) and unvisited objects. Sweep phase releases the memory fragments which contains unreachable objects. It is simple, but because the dead objects are not necessarily next to each other, we end up having a fragmented memory. That’s not bad but trying to fit a too large object into the memory could potentially lead to OutOfMemoryError.

Mark-Sweep-Compact:-This algorithm fixes the problem with fragmented memory. After all alive objects are marked, they are moved to the beginning of the memory space. That helps to avoid having too fragmented (split) memory, but compacting the heap isn’t for free. Copying objects and updating all references to them take time and it all happens during STW pause.

Mark-Copy:- Mark-copy algorithm copies all alive objects to a new memory region. The previously occupied region is considered to be free. Next time mark-copy is executed, all the alive objects are moved back to the previous memory region. As you can imagine, this, of course, leads to a memory compaction. Unfortunately, it requires additional extra region large enough to fit all live objects at any given point in time.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s