Reference Counting
The main difficulty in garbage collection is actually locating the garbage. In this simple strategy called Reference Counting, each object keeps track of the total number of references to that object. Call this special field reference_count.
This reference_count field needs to be updated every time one reference variable is assigned to another. If a reference is lost you decrement the reference_count and if a reference is added you increment the reference_count. So this is an added overhead per assignment statement. The garbage collector just needs to examine the reference_count field of all created objects. If objects refer to other objects then reference_counts for all referred objects needs to adjusted.
Reference counting fails to work when there is a cycle of references.
Mark and Sweep Garbage Collection
This takes care of cyclic references. It keeps track of all objects that the program can access. The objects referred to by any local variables or any global variables. These objects are called "roots", analogous to roots in trees. If an object is reachable from any of the roots it is considered live.
In mark and sweep algorithm unreferenced objects are not reclaimed immediately. The algorithm proceeds in two phases. In the first phase all live objects are marked. In the second phase called the sweep phase all unmarked objects are released. The main problems with the Mark and Sweep algorithm is long GC pauses and fragmentation of the heap.
Stop and Copy Garbage Collection
The heap is divided into two regions. The active region and the inactive region. Initially all allocations are done from the active region. When the active region fills up the program is suspended and all live objects are copied to the inactive region. During copying objects are placed next to each other so this solves the problem of fragmentation. However you require twice as much memory. Note that copy is invoked recursively for objects referring to other objects.
Mark and Compact Garbage Collection
In this phase all live objects are marked in the first phase and then in the second phase the garbage collector compacts the heap by moving all live objects into contiguous heap locations.
