Understanding Garbage Collection in Microsoft.NET

Garbage collection in Microsoft.NET is based on Mark and Compact algorithm and concept of generations.

Mark and Compact Algorithm

When an application is started a given amount of address space is allocated to the application which is called managed heap. We can make use of GetTotalMemory method of GC class to get the number of bytes currently allocated in managed memory. When a new object has to be instantiated and there isn’t enough space in the application’s managed heap, the garbage collection process runs.

Garbage collector generates a list of all the application’s objects that are still in scope.

The garbage collector steps through the managed heap, looking for any object that is not present in this list.

The garbage collector marks the objects that are out of scope. The space these objects were taking up is freed.

After the garbage collector has iterated through the managed heap, it moves the references to all the objects down to the beginning of the heap. All the object references are therefore stored contiguously in the heap.

Let’s take a simple example

Suppose when an application is started, objects A, B, C and D are instantiated, and references to these objects are placed on the managed heap.

Object D

Object C

Object B

Object A

Suppose later in the life of application, object E needs to be instantiated. Now there isn’t enough space in the managed heap so garbage collection needs to be performed. Objects B and C have gone out of scope.

When garbage collection is started, a list of all the objects that are still in scope is generated, here the list will contain object A and D, than it iterates through the managed heap, looking for the objects that are not present in the list. These objects are marked as unreachable and the managed heap is compacted. A reference to Object E is then placed on the heap.

Object D

Object C

Object B

Object A

Object E

Object D

Object A

Generations

Here in the above case it could be very expensive to step through the entire heap, looking for marked objects. To make this process more efficient, Microsoft.NET implements concept of generations. The theory of generations assumes that the older an object is, the less likely it is out to be out of scope during garbage collection. Therefore, it is most efficient to check the newest objects first and then check the older objects if space is still needed.

There are three generations: Generation 0, 1 and 2. When a garbage collection is performed, it collects only objects in Generation 0. If there is still not enough space to allocate a new object, then garbage collector moves on to Generation 1, and then if necessary, it moves to Generation 2 objects.

For e.g. consider an application that has object A in generation 2, B and C in generation 1 and D, E, F in Generation 0.

Object F	Gen 0
Object E	Gen 0
Object D	Gen 0
Object C	Gen 1
Object B	Gen 1
Object A	Gen 2

Now the application attempts to allocate space to Object G, but it cannot, so a garbage collection is required.

Say objects C, D and E have gone out of scope.

After the garbage collection, objects D and E are collected. Even though Object C had gone out of scope, the garbage collector only collected from Generation 0. If more space had been required than Object C, from Generation 1, would also have been collected.

And one more thing, the Object F will be moved to Generation 1 because it has survived one garbage collection. The garbage collector did not collect from Generation 1; therefore Object C is still within generation 1.

Now the managed heap would look something like this