There are several basic strategies for garbage collection: reference counting, mark-sweep, mark-compact, and copying. In addition, some algorithms can do their job incrementally (the entire heap need not be collected at once, resulting in shorter collection pauses), and some can run while the user program runs (concurrent collectors). Others must perform an entire collection at once while the user program is suspended (so-called stop-the-world collectors). Finally, there are hybrid collectors, such as the generational collector employed by the 1.2 and later JDKs, which use different collection algorithms on different areas of the heap.
Old objects, young objects
In any application heap, some objects become garbage shortly after their creation, some survive for a long time and then become garbage, and others can remain live for the entirety of the program's run. Empirical studies have shown that for most object-oriented languages, the Java language included, the vast majority of objects -- as much as 98 percent, depending on your metric for object youth -- die young. One can measure an object's age in wall-clock seconds, in total bytes allocated by the memory management subsystem since the object was allocated, or the number of garbage collections since the object was allocated. But no matter how you measure, the studies show the same thing -- most objects die young. The fact that most objects die young has significance for the choice of collector. In particular, copying collectors perform quite well when the majority of objects die young, since copying collectors do not visit dead objects at all; they simply copy the live objects to another heap region, then reclaim the whole of the remaining space in one fell swoop.
Of the objects that survive past their first collection, a significant portion of those will become long-lived or permanent. The various garbage collection strategies perform very differently depending on the mix of short-lived and long-lived objects. Copying collectors work very well when most objects die young, because objects that die young never need to be copied at all. However, the copying collector deals poorly with long-lived objects, repeatedly copying them back and forth from one semi-space to another. Conversely, mark-compact collectors do very well with long-lived objects, because long-lived objects tend to accumulate at the bottom of the heap and then do not need to be copied again. Mark-sweep and mark-compact collectors, however, expend considerably more effort examining dead objects, because they must examine every object in the heap during the sweep phase.
algorithms
Reference counting
The most straightforward garbage collection strategy is reference counting. Reference counting is simple, but requires significant assistance from the compiler and imposes overhead on the mutator (the term for the user program, from the perspective of the garbage collector). Each object has an associated reference count -- the number of active references to that object. If an object's reference count is zero, it is garbage (unreachable from the user program) and can be recycled. Every time a pointer reference is modified, such as through an assignment statement, or when a reference goes out of scope, the compiler must generate code to update the referenced object's reference count. If an object's reference count goes to zero, the runtime can reclaim the block immediately (and decrement the reference counts of any blocks that the reclaimed block references), or place it on a queue for deferred collection.
Reference counting is simple, lends itself well to incremental collection, and the collection process tends to have good locality of reference, but it is rarely used in production garbage collectors for a number of reasons, such as its inability to reclaim unreachable cyclic structures (objects that reference each other directly or indirectly, like a circularly linked list or a tree that contains back-pointers to the parent node).
Tracing collector
None of the standard garbage collectors in the JDK uses reference counting; instead, they all use some form of tracing collector. A tracing collector stops the world (although not necessarily for the entire duration of the collection) and starts tracing objects, starting at the root set and following references until all reachable objects have been examined. Roots can be found in program registers, in local (stack-based) variables in each thread's stack, and in static variables.
Mark-sweep collectors
The most basic form of tracing collector, in which the world is stopped and the collector visits each live node, starting from the roots, and marks each node it visits. When there are no more references to follow, collection is complete, and then the heap is swept (that is, every object in the heap is examined), and any object not marked is reclaimed as garbage and returned to the free list.
The big problem with mark-sweep is that every active (that is, allocated) object, whether reachable or not, is visited during the sweep phase. Because a significant percentage of objects are likely to be garbage, this means that the collector is spending considerable effort examining and handling garbage. Mark-sweep collectors also tend to leave the heap fragmented, which can cause locality issues and can also cause allocation failures even when sufficient free memory appears to be available.
Copying collectors
In a copying collector, another form of tracing collector, the heap is divided into two equally sized semi-spaces, one of which contains active data and the other is unused. When the active space fills up, the world is stopped and live objects are copied from the active space into the inactive space. The roles of the spaces are then flipped, with the old inactive space becoming the new active space.
Copying collection has the advantage of only visiting live objects, which means garbage objects will not be examined, nor will they need to be paged into memory or brought into the cache. The duration of collection cycles in a copying collector is driven by the number of live objects. However, copying collectors have the added cost of copying the data from one space to another, adjusting all references to point to the new copy. In particular, long-lived objects will be copied back and forth on every collection.
Mark-compact collectors
The copying algorithm has excellent performance characteristics, but it has the drawback of requiring twice as much memory as a mark-sweep collector. The mark-compact algorithm combines mark-sweep and copying in a way that avoids this problem, at the cost of some increased collection complexity. Like mark-sweep, mark-compact is a two-phase process, where each live object is visited and marked in the marking phase. Then, marked objects are copied such that all the live objects are compacted at the bottom of the heap. If a complete compaction is performed at every collection, the resulting heap is similar to the result of a copying collector -- there is a clear demarcation between the active portion of the heap and the free area, so that allocation costs are comparable to a copying collector. Long-lived objects tend to accumulate at the bottom of the heap, so they are not copied repeatedly as they are in a copying collector.
Generational collection
A generational collector divides the heap into multiple generations. Objects are created in the young generation, and objects that meet some promotion criteria, such as having survived a certain number of collections, are then promoted to the next older generation. A generational collector is free to use a different collection strategy for different generations and perform garbage collection on the generations separately.
Minor collections
One of the advantages of generational collection is that it can make garbage collection pauses shorter by not collecting all generations at once. When the allocator is unable to fulfill an allocation request, it first triggers a minor collection, which only collects the youngest generation. Since many of the objects in the young generation will already be dead and the copying collector does not need to examine dead objects at all, minor collection pauses can be quite short and can often reclaim significant heap space. If the minor collection frees enough heap space, the user program can resume immediately. If it does not free enough heap space, it proceeds to collect higher generations until enough memory has been reclaimed. (In the event the garbage collector cannot reclaim enough memory after a full collection, it will either expand the heap or it will throw anOutOfMemoryError.)
The JDK 1.4.1 default collector
By default, the 1.4.1 JDK divides the heap into two sections, a young generation and an old generation. (Actually, there is also a third section, the permanent space, which is used for storing loaded class and method objects.) The young generation is divided into a creation space, often called Eden, and two survivor semi-spaces, using a copying collector.
The old generation uses a mark-compact collector. Objects are promoted from the young generation to the old generation after they have survived copying a certain number of times. A minor collection will copy live objects from Eden and one of the survivor semi-spaces into the other survivor space, potentially promoting some objects to the older generation. A major collection will collect both the young and old generation. The System.gc() method always triggers a major collection, which is one of the reasons you should use System.gc() sparingly, if at all, because major collections can take much longer than a minor collection. There is no way to programmatically trigger a minor collection.
Different algorithms can be used to perform garbage collection in the different generations, each algorithm
optimized based on commonly observed characteristics for that particular generation. Generational garbage
collection exploits the following observations, known as the weak generational hypothesis, regarding
applications written in several programming languages, including the Java programming language:
• Most allocated objects are not referenced (considered live) for long, that is, they die young.
• Few references from older to younger objects exist.
Below is the table which summarizes the algorithm used by different types of Garbage Collectors in J2SE 5.0:
Parallel Compacting collector - Old Generation:
(Mark - Summary - Compact)
Marking Phase:
Several threads would run.
Heap would be divided into regions.
One thread per region would run.
Each region has data. Data would be updated by thread with information about the size & location of the live objects.
Summary Phase:
(One thread)
Summary phase examines the density of each region & calculates a point after which, space recovered after compacting would be worth. Region left of that point is referred as "Dense Prefix".
Assume, our heap is in following stage(several cycles of GC has already run).
Our heap reached this state after several GC cycles, so, the left side of heap is dense & contains most live objects. If compacting is performed in the left most region, then very little amount of space would be recovered, and which is not worth.
Summary Phase examines the density of regions, starting from the left most, until it reaches a point where the space that could be recovered from a region and those to right of it, is worth. Worth the cost of compactng those regions.
Compaction phase:
(Multiple threads)
Summary phase calculates and stores the new location of the first byte of the live objects, in data associated with each region. Regions to the right have to be compacted. And we have to move all objects within a region to left side of that region.
Compaction phase uses the data prepared by the summary phase to identify, which regions are to be compacted, and which objects to move, and new location of the objects(in case they are to be moved). Multiple threads run independently, one in each region.
Thus, finally a single large empty block would be created at the right end.
CMS Collector - Old Generation
Initial Mark
Identifies the initial set of live objects, directly reachable form application code.
Concurrent Mark
Marks all live objects that are transitively reachable from the set(prepared by initial mark)
Remark
Revisit any object that was modified during the concurrent mark.
(Objects created while Concurrent mark was running, would be marked now)
At the end of markings, it is guaranteed all live objects on the heap have been marked.
Now, Concurrent Sweep Phase, reclaims all the garbage that has been identified.
CMS Collector is not compacting, which means it does not move the live objects to one end of the old generation.
Since the free space is not contigous, the collector can no longer use a simple pointer indicating the next free location into which the next objext can be allocated.
It employs free lists. Lists linking together unallocated regions of memory.
Each time an object needs to be allocated, the appropriate list(based on the amount of memory needed) must be searched for a region large enough to hold the object.
CMS has advantage in term of pause time, in the figure we can see that total pause time is Pause1 + Pause2. When multiple threads( i.e. n) are running, then pause time is reduced by n.
New JDK7 Garbage Collector:
The Garbage First(G1) Garbage Collecor
Like Other HotSpot GC's, G1 is generational means it has concept of old objects and new objects. GC cycles visit new objects very frequently, and old objects less frequently.
Big difference between G1 and other Garbage collector is that now there is no physical difference between young generation and old generation.
Whole heap is divided into multiple regions.
Each region is of same size.
Few set of regions belong to young generation and few set to old generation.
SO, young generation is a non-contiguous set of regions, and similar is old generation. G1 is flexible enough to move objects from new to old and vice versa any time.
Initially, a few st of regions(belonging to young generation) are considered as part of collection set. so all live objects are marked in the regions belonging to collection set. Now there is a evacuation pause, and during this pause, survivor objects from the collection set are evacuated to another set of regions(the to-spaces), and then collection set region is reclaimed.
Evacuation pauses collect the young generation, but sometimes old generations are also collected during the pause time.
In regions belonging to old generation, there is Concurrent marking(similar to CMS old generation collector). Profitable regions are marked, i.e. where performing collection is worth. There is no concurrent sweeping. The most profitable old regions identified by marking phase are collected during the evacuation pause.
Unlike CMS, G1 performs compaction over time. Compaction eliminates fragmentation, which was a big issue with CMS collector.
Reference: http://www.ibm.com/developerworks/java/library/j-jtp10283/
!!!Any Comments would be really appreciated!!!
Old objects, young objects
In any application heap, some objects become garbage shortly after their creation, some survive for a long time and then become garbage, and others can remain live for the entirety of the program's run. Empirical studies have shown that for most object-oriented languages, the Java language included, the vast majority of objects -- as much as 98 percent, depending on your metric for object youth -- die young. One can measure an object's age in wall-clock seconds, in total bytes allocated by the memory management subsystem since the object was allocated, or the number of garbage collections since the object was allocated. But no matter how you measure, the studies show the same thing -- most objects die young. The fact that most objects die young has significance for the choice of collector. In particular, copying collectors perform quite well when the majority of objects die young, since copying collectors do not visit dead objects at all; they simply copy the live objects to another heap region, then reclaim the whole of the remaining space in one fell swoop.
Of the objects that survive past their first collection, a significant portion of those will become long-lived or permanent. The various garbage collection strategies perform very differently depending on the mix of short-lived and long-lived objects. Copying collectors work very well when most objects die young, because objects that die young never need to be copied at all. However, the copying collector deals poorly with long-lived objects, repeatedly copying them back and forth from one semi-space to another. Conversely, mark-compact collectors do very well with long-lived objects, because long-lived objects tend to accumulate at the bottom of the heap and then do not need to be copied again. Mark-sweep and mark-compact collectors, however, expend considerably more effort examining dead objects, because they must examine every object in the heap during the sweep phase.
algorithms
Reference counting
The most straightforward garbage collection strategy is reference counting. Reference counting is simple, but requires significant assistance from the compiler and imposes overhead on the mutator (the term for the user program, from the perspective of the garbage collector). Each object has an associated reference count -- the number of active references to that object. If an object's reference count is zero, it is garbage (unreachable from the user program) and can be recycled. Every time a pointer reference is modified, such as through an assignment statement, or when a reference goes out of scope, the compiler must generate code to update the referenced object's reference count. If an object's reference count goes to zero, the runtime can reclaim the block immediately (and decrement the reference counts of any blocks that the reclaimed block references), or place it on a queue for deferred collection.
Reference counting is simple, lends itself well to incremental collection, and the collection process tends to have good locality of reference, but it is rarely used in production garbage collectors for a number of reasons, such as its inability to reclaim unreachable cyclic structures (objects that reference each other directly or indirectly, like a circularly linked list or a tree that contains back-pointers to the parent node).
Tracing collector
None of the standard garbage collectors in the JDK uses reference counting; instead, they all use some form of tracing collector. A tracing collector stops the world (although not necessarily for the entire duration of the collection) and starts tracing objects, starting at the root set and following references until all reachable objects have been examined. Roots can be found in program registers, in local (stack-based) variables in each thread's stack, and in static variables.
Mark-sweep collectors
The most basic form of tracing collector, in which the world is stopped and the collector visits each live node, starting from the roots, and marks each node it visits. When there are no more references to follow, collection is complete, and then the heap is swept (that is, every object in the heap is examined), and any object not marked is reclaimed as garbage and returned to the free list.
The big problem with mark-sweep is that every active (that is, allocated) object, whether reachable or not, is visited during the sweep phase. Because a significant percentage of objects are likely to be garbage, this means that the collector is spending considerable effort examining and handling garbage. Mark-sweep collectors also tend to leave the heap fragmented, which can cause locality issues and can also cause allocation failures even when sufficient free memory appears to be available.
Copying collectors
In a copying collector, another form of tracing collector, the heap is divided into two equally sized semi-spaces, one of which contains active data and the other is unused. When the active space fills up, the world is stopped and live objects are copied from the active space into the inactive space. The roles of the spaces are then flipped, with the old inactive space becoming the new active space.
Copying collection has the advantage of only visiting live objects, which means garbage objects will not be examined, nor will they need to be paged into memory or brought into the cache. The duration of collection cycles in a copying collector is driven by the number of live objects. However, copying collectors have the added cost of copying the data from one space to another, adjusting all references to point to the new copy. In particular, long-lived objects will be copied back and forth on every collection.
Mark-compact collectors
The copying algorithm has excellent performance characteristics, but it has the drawback of requiring twice as much memory as a mark-sweep collector. The mark-compact algorithm combines mark-sweep and copying in a way that avoids this problem, at the cost of some increased collection complexity. Like mark-sweep, mark-compact is a two-phase process, where each live object is visited and marked in the marking phase. Then, marked objects are copied such that all the live objects are compacted at the bottom of the heap. If a complete compaction is performed at every collection, the resulting heap is similar to the result of a copying collector -- there is a clear demarcation between the active portion of the heap and the free area, so that allocation costs are comparable to a copying collector. Long-lived objects tend to accumulate at the bottom of the heap, so they are not copied repeatedly as they are in a copying collector.
Generational collection
A generational collector divides the heap into multiple generations. Objects are created in the young generation, and objects that meet some promotion criteria, such as having survived a certain number of collections, are then promoted to the next older generation. A generational collector is free to use a different collection strategy for different generations and perform garbage collection on the generations separately.
Minor collections
One of the advantages of generational collection is that it can make garbage collection pauses shorter by not collecting all generations at once. When the allocator is unable to fulfill an allocation request, it first triggers a minor collection, which only collects the youngest generation. Since many of the objects in the young generation will already be dead and the copying collector does not need to examine dead objects at all, minor collection pauses can be quite short and can often reclaim significant heap space. If the minor collection frees enough heap space, the user program can resume immediately. If it does not free enough heap space, it proceeds to collect higher generations until enough memory has been reclaimed. (In the event the garbage collector cannot reclaim enough memory after a full collection, it will either expand the heap or it will throw anOutOfMemoryError.)
The JDK 1.4.1 default collector
By default, the 1.4.1 JDK divides the heap into two sections, a young generation and an old generation. (Actually, there is also a third section, the permanent space, which is used for storing loaded class and method objects.) The young generation is divided into a creation space, often called Eden, and two survivor semi-spaces, using a copying collector.
The old generation uses a mark-compact collector. Objects are promoted from the young generation to the old generation after they have survived copying a certain number of times. A minor collection will copy live objects from Eden and one of the survivor semi-spaces into the other survivor space, potentially promoting some objects to the older generation. A major collection will collect both the young and old generation. The System.gc() method always triggers a major collection, which is one of the reasons you should use System.gc() sparingly, if at all, because major collections can take much longer than a minor collection. There is no way to programmatically trigger a minor collection.
Different algorithms can be used to perform garbage collection in the different generations, each algorithm
optimized based on commonly observed characteristics for that particular generation. Generational garbage
collection exploits the following observations, known as the weak generational hypothesis, regarding
applications written in several programming languages, including the Java programming language:
• Most allocated objects are not referenced (considered live) for long, that is, they die young.
• Few references from older to younger objects exist.
Below is the table which summarizes the algorithm used by different types of Garbage Collectors in J2SE 5.0:
Parallel Compacting collector - Old Generation:
(Mark - Summary - Compact)
Marking Phase:
Several threads would run.
Heap would be divided into regions.
One thread per region would run.
Each region has data. Data would be updated by thread with information about the size & location of the live objects.
Summary Phase:
(One thread)
Summary phase examines the density of each region & calculates a point after which, space recovered after compacting would be worth. Region left of that point is referred as "Dense Prefix".
Assume, our heap is in following stage(several cycles of GC has already run).
Our heap reached this state after several GC cycles, so, the left side of heap is dense & contains most live objects. If compacting is performed in the left most region, then very little amount of space would be recovered, and which is not worth.
Summary Phase examines the density of regions, starting from the left most, until it reaches a point where the space that could be recovered from a region and those to right of it, is worth. Worth the cost of compactng those regions.
Compaction phase:
(Multiple threads)
Summary phase calculates and stores the new location of the first byte of the live objects, in data associated with each region. Regions to the right have to be compacted. And we have to move all objects within a region to left side of that region.
Compaction phase uses the data prepared by the summary phase to identify, which regions are to be compacted, and which objects to move, and new location of the objects(in case they are to be moved). Multiple threads run independently, one in each region.
Thus, finally a single large empty block would be created at the right end.
CMS Collector - Old Generation
Initial Mark
Identifies the initial set of live objects, directly reachable form application code.
Concurrent Mark
Marks all live objects that are transitively reachable from the set(prepared by initial mark)
Remark
Revisit any object that was modified during the concurrent mark.
(Objects created while Concurrent mark was running, would be marked now)
At the end of markings, it is guaranteed all live objects on the heap have been marked.
Now, Concurrent Sweep Phase, reclaims all the garbage that has been identified.
CMS Collector is not compacting, which means it does not move the live objects to one end of the old generation.
Since the free space is not contigous, the collector can no longer use a simple pointer indicating the next free location into which the next objext can be allocated.
It employs free lists. Lists linking together unallocated regions of memory.
Each time an object needs to be allocated, the appropriate list(based on the amount of memory needed) must be searched for a region large enough to hold the object.
CMS has advantage in term of pause time, in the figure we can see that total pause time is Pause1 + Pause2. When multiple threads( i.e. n) are running, then pause time is reduced by n.
New JDK7 Garbage Collector:
The Garbage First(G1) Garbage Collecor
Like Other HotSpot GC's, G1 is generational means it has concept of old objects and new objects. GC cycles visit new objects very frequently, and old objects less frequently.
Big difference between G1 and other Garbage collector is that now there is no physical difference between young generation and old generation.
Whole heap is divided into multiple regions.
Each region is of same size.
Few set of regions belong to young generation and few set to old generation.
SO, young generation is a non-contiguous set of regions, and similar is old generation. G1 is flexible enough to move objects from new to old and vice versa any time.
Initially, a few st of regions(belonging to young generation) are considered as part of collection set. so all live objects are marked in the regions belonging to collection set. Now there is a evacuation pause, and during this pause, survivor objects from the collection set are evacuated to another set of regions(the to-spaces), and then collection set region is reclaimed.
Evacuation pauses collect the young generation, but sometimes old generations are also collected during the pause time.
In regions belonging to old generation, there is Concurrent marking(similar to CMS old generation collector). Profitable regions are marked, i.e. where performing collection is worth. There is no concurrent sweeping. The most profitable old regions identified by marking phase are collected during the evacuation pause.
Unlike CMS, G1 performs compaction over time. Compaction eliminates fragmentation, which was a big issue with CMS collector.
Reference: http://www.ibm.com/developerworks/java/library/j-jtp10283/
!!!Any Comments would be really appreciated!!!
