Downloaded 419 times
Garbage collection algorithms
- 1. Garbage Collection AlgorithmsByAchinth Anand Gurkhi
- 2. What is GarbageCollection?Garbage Collection is the process by which unused objects are deleted to reclaim memory spaceInvented by John McCarthy around 1959 to solve problems in LispIt is used in Lisp, Smalltalk, Eiffel, Haskell, ML, Schema, Modula-3, Java and .NET
- 3. GC AlgorithmsReference CountingMark-SweepCollectorCopying CollectorMark-Compact CollectorGenerational Collector
- 4. Reference CountingNeeds helpfrom compiler and the program to maintain a reference countCompiler adds code to increment/decrement reference count when the object is referenced/dereferencedIf reference count is zero it is garbage collected and reference count of all objects it references is decremented by oneUsed by ANSI C++ library classes like string
- 5. Reference CountingAdvantages: Garbagecollection can be immediateDisadvantages:Cannot handle cyclic references Need extra memory for the reference counterIncrementing and decrementing reference counts every time a reference is created or destroyed can significantly impede performance. Example: array processing
- 6. Mark-Sweep CollectorAll applicationthreads are stoppedMark: from the roots (objects referenced directly) every referenced object is visited and markedSweep: entire heap is scanned and all unmarked objects are collected. Next all marked objects are reset
- 7. Mark-Sweep CollectorAdvantages:Can handlecyclic referencesNo burden on the compiler or the applicationDisadvantagesAs entire heap is scanned, pauses would be longerIf heap is paged can have performance issuesCauses heap fragmentation which could lead of out of memory errors
- 8. Copying CollectorThe heapis divided into two equal spacesOne contains active data and the other is inactiveWhen the active half gets full, the world is stopped, live objects are moved to the inactive half and then the active half is clearedFor the next cycle, roles are reversed, the inactive half becomes the active half
- 9. Copying CollectorAdvantages:Only liveobjects are visited, garbage objects are not visitedData compaction is achieved which reduces cost of object allocation and out of memory errorsDisadvantages:Requires twice the heap size than other collectorsOverhead of copying objects from one space to anotherOverhead of adjusting all references to the new copyLong lived objects are copied back and forth on every collection
- 10. Mark-Compact CollectorAll applicationthreads are stoppedMark: from the roots (objects referenced directly) every referenced object is visited and markedCompact: entire heap is scanned and all unmarked objects are collected. Next all marked objects compacted at the bottom of the heap and then the flags are reset
- 11. Mark-Compact CollectorAdvantages:Compaction isachieved Without the hassle of long lived objects being copied back and forthWithout the need for double the heap size DisadvantagesOverhead of copying objects (for compaction)Overhead of adjusting all references to the new copy
- 12. Generational Collector98% ofthe objects die young Copying Collectors perform well with short-lived objectsMark-Compact Collectors perform well with long-lived objectsCan we use different GC algorithms based on object’s age?
- 13. Generational CollectorThe heapis divided into generations (usually 2 or 3)Objects are created in the young generation (gen 0)When memory is needed, a GC of gen 0 is performed & live objects are moved to the next generation (gen 1) & dead objects are collected (Copying Collector). If enough memory is now available GC is stoppedElse the next older generation (gen 1) is collected. This goes on till enough memory is released or till the last (oldest) generation is reached. The last generation (old objects) uses Mark-Compact Collector algorithm
- 14. Generational CollectorAdvantages:GC cyclesare small as all objects are not collectedOnly old objects are copied from one generation to anotherEntire heap is not scannedDisadvantagesOverhead of copying objects (for compaction)Overhead of adjusting all references to the new copy