Garbage Collection: Memory Management in .Net

Garbage Collection: Memory Management in .Net

During the days, when I was working with C++, as a basic rule for design and development, it was required to track all the memory usage and then carefully release all the memory acquired. Implementing proper resource management for our applications was always very difficult and a tedious task. It always distracted our concentration from the real problems that we were trying to solve. It was such a painful and disliked task that at times we used to wonder if we could have a mechanism that simplified this mind-numbing task of memory management.

Then came the Garbage Collection in the Microsoft .NET common language runtime environment, which completely relived the developer from the task of all this memory management. However, the irony is the developers were still not happy.

Of all of the technologies to be found in .NET, the most controversial, seems to be garbage collection. This was because; the managed heap and the garbage collection mechanism, which are a key part of the .NET framework, have always appeared as foreign ideas to many of us. We often criticize the memory management and the garbage collector, as implemented by the .Net CLR, but the criticisms are typically based on a lack of understanding and nothing more.

Let’s try and look at the mechanics of the Garbage Collection and the Memory Management. Let’s try and understand the steps of how the garbage collection algorithm works. I guess if we are able to explain how the resources are allocated and managed, then we would be in a better position to appreciate the importance and usefulness of the Garbage Collection.

Memory management using the Garbage Collector

The Garbage Collector is an important process in the .Net CLR. The Microsoft .NET common language runtime requires that all resources be allocated from the managed heap. Objects are automatically freed when they are no longer needed by the application.

The CLR performs Non-deterministic finalization: i.e. it cannot be predicted, when the Garbage Collector will be called to clean up unnecessary objects from memory. Non deterministic finalization is performed when the CLR foresees a memory deficiency.

In all kinds of programs, resources are used. These resources could be in the form of ‘memory buffers’, ‘screen space’, ‘network connections’, ‘database resources', and so on. Moreover, we should realize that in an object-oriented environment, every type is actually a resource available for our program to use. To use any of these resources requires that memory be allocated to represent the type. The bare minimum, steps required to access a resource are as follows:

1. Allocate memory for the resource. (Resource Allocation – explained below)
2. Initialize the memory to set the initial state of the resource.
3. Use the resource by accessing the instance members of the type.
4. Reset the state of the resource for cleanup.
5. Free the memory. (Garbage Collection – explained below)

Resource Allocation

There are two data types that the Garbage collector bifurcates into: Value types and Reference types

1. Value types
In C#, all the "things" declared with the following list of type declarations are Value types (because they are from System.ValueType):
• bool                                            • byte                                            • char
• decimal                                      • double                                        • enum
• float                                            • int                                               • long
• sbyte                                          • short                                          • struct
• uint                                             • ulong                                          • ushort

These Value Types reside on the stack. The CLR does not care about this type of data with reference to memory management.

The Stack is self-maintaining, meaning that it basically takes care of its own memory management.  When the top box is no longer used, it's thrown out.


2. Reference Types
All the "things" declared with the types in this list are Reference types. They inherit from System.Object
 
• class                                             • interface                                             • delegate
• object                                            • string
 
These Reference Types exist on a managed heap. This is where the Garbage Collector comes into the picture.

Managed Heap

A Managed Heap is a pool of memory where all the instances of Reference Types (classes and arrays etc.) are created and allocated space.

When an object is initialized, the CLR simply allocates an address space in the Managed Heap. There is actually no storage space allocated at this point of time. However a pointer to this heap is maintained to keep track of the next object within this heap. The memory space on this heap is allocated only when an object is created using the new operator.
 Mechanics of Resource Allocation - Object creation, initialization and instantiation
Initially, the next object pointer is set to the base address of the reserved address space region.
When we create an object i.e. declare a type, the runtime reserves a contiguous region of address space that initially has no storage allocated for it, when we create an object. The Jitter (Just-in-time Compiler) updates the manage heap and also maintains the addresses of all objects that are allocated within this managed heap.

After declaring an object, we instantiate the object using the 'new' operator. This ‘new’ operator first makes sure that the bytes required by the new object fit in the reserved region (committing storage if necessary). If the object fits, then pointer points to the object in the heap, this object's constructor is called, and the new operator returns the address of the object. At this point, ‘Next Object Pointer’ is incremented past the object so that it points to where the next object will be placed in the heap.
Similarly, the objects keep adding to the heap, with the instantiation of each new object.

In this process, it might reach to a condition where there is no more space left in the heap to be allocated to a new object, or the available space is not enough to accommodate the new object that has been instantiated. This is to say, when the ‘Next Object Pointer’ reaches beyond the end of the address space, a memory deficiency occurs and therefore the CLR calls the Garbage Collector and gives it this memory heap.

Application Roots
Before we proceed to examine and understand the Garbage Collection process, let’s take a final look at the Managed Heap.

So, we see that the required memory space is allocated on the heap, to all the objects that have been initialized. An Object Pointer is set to the final location and stores the address, where the next object would be allocated the memory space on the heap. Is this all? No it is not.

Many objects on a heap are linked one to the other forming a chain, depending on which object is referenced by whom. There might be multiple such chains in the heap. The reference to the first object, i.e. the memory location to any such chain is called a Root. Every application has a set of such roots. E.g. the global and static object pointers, any local variable/parameter object pointers and any CPU registers containing pointers to objects.

All these roots are stored in the Application stack and identify storage locations, which refer to objects on the managed heap or to objects that are set to null. This list of active roots is maintained by the just-in-time (JIT) compiler and common language runtime, and is made accessible to the garbage collector's algorithm.
In reality, a collection occurs when generation 0 is completely full. Briefly, a generation is a mechanism implemented by the garbage collector in order to improve performance. The idea is that newly created objects are part of a young generation, and objects created early in the application's lifecycle are in an old generation. Separating objects into generations can allow the garbage collector to collect specific generations instead of collecting all objects in the managed heap.

The Garbage Collector

The basic algorithm used by the garbage collector is quite simple:

• Mark all managed memory as garbage
• Look for used memory blocks, and mark them as valid
• Discard all unused memory blocks
• Compact the heap

Once the GC receives this memory heap, The garbage collector checks to see if there are any objects in the heap that are no longer being used by the application. If such objects exist, then the memory used by these objects can be reclaimed. (If no more memory is available for the heap, then the new operator throws an OutOfMemoryException.)

Now there is a very valid question. How does the garbage collector know if the application is using an object or not?

When the garbage collector starts running, it makes the assumption that all objects in the heap are garbage. In other words, it assumes that none of the application's roots refer to any objects in the heap. Now, the garbage collector starts checking the roots and building a graph of all objects reachable from the roots.
In the above figure the Objects A, and E are directly referenced by the Application Roots. The Garbage collector starts from the Root, traversing through all the objects in the chain and stores them, making a graph. This action is repeated for all the chains one by one, and hence all the objects that are either referred directly by the Application Root or are indirectly referred by another object on the heap are added to the Graph.

Here it is important to note that, if while traversing down a chain, the garbage collector reaches an object that it has already added to the Graph, then it stops going further down that path. This is because, it is obvious that the next objects further down the chain would already be there in the Graph. This increases the performance of the process as well as it also prevents infinite loops. In case there are any circular linked lists of objects.

Once all the roots/chains have been checked and added to the Graph, the Garbage Collector assumes that are not in the Graph are not referenced from the application's roots and hence are not accessible by the application, and are therefore considered garbage. The garbage collector now checks the entire heap for contiguous blocks of garbage objects. It shifts the non-garbage objects down in the heap, removing all of the gaps in the heap. It then modifies the application's roots so that all the pointers now point to the objects' new locations. Also, if any object contains a pointer to another object, it corrects these pointers as well. Finally, the Next Object Pointer is positioned just after the last non-garbage object.

Now the heap is ready to allocate the memory space, required by the new object that was initialized and had triggered the Garbage Collection.
However there might be a case where even after the Garbage Collection there is not enough space on the Heap to accommodate the new object. In such a scenario another very important feature of Garbage Collector called; ‘Generations’ comes into action.

Generations

Though this feature of the garbage collector resolves the issue where even after the garbage collection, there is not enough space on the heap to accommodate the new object. But, then it is absolutely wrong to say that the feature of Generations address and was developed only to address the memory accommodation issue. In fact this feature of the garbage collector exists purely to improve the performance.

The Garbage Collector with this feature is known as an ‘Ephemeral Garbage Collector’, and it makes the following assumptions:

•  The newer an object is, the shorter its lifetime will be.
•  The older an object is, the longer its lifetime will be.
•  Newer objects tend to have strong relationships to each other and are frequently accessed around the same time.
•  Compacting a portion of the heap is faster than compacting the whole heap.

In order to understand, physically the Generations are nothing more than the identification of the Heap area into 3 categories. Once the Garbage Collector receives the memory heap, it divides/distributes the contents in the heap into three categories of objects and stores these objects into three tables:

•  Generation 0 this stores short lived objects.
•  Generation 1 this stores older objects.
•  Generation 2 this stores the oldest objects.

Generation 0
At first when there are no objects on the Heap, then every time a new object is added, it goes into Generation 0. , as discussed above. Hence the objects in the Generation 0 are all latest objects that have never been examined by the Garbage Collector.

Generation 1
Here Objects A, C, E, F and I are free objects, i.e. they do not have any reference, neither from a Root nor from any other object on the heap.  When this Generation 0 is completely full, i.e. there is no more space for a new Object then the garbage collection occurs. All the objects that survive the collection (Objects B, D, G and H) are compacted into the left most portion of the heap. These objects are the old objects and are now said to be in Generation1.
Now any new object added on the heap, goes to the Generation 0. So we see that in Generation 0 we have New Objects and in Generation 1 we have relative older objects.

Generation 2
Same as before, if again the Generation 0 is full, then again the heap is subjected to Garbage Collection. However, this time first all the objects in Generation 1, that survive the collection (Objects B, G & H) are compacted and are now considered to be in Generation 2.

Then, all the objects in Generation 0 are compacted as before and are now considered to be in Generation 1. This clears the space in Generation 0 for new objects.

Hence, we see that in Generation 2 we have the oldest objects (objects B, G & H), in generation we have relatively older objects (objects K & N) and in generation we have the most recently added i.e. the newest objects (objects O, P, Q & R).
Currently, generation 2 is the highest generation supported by the runtime's garbage collector. When future collections occur, any surviving objects currently in Generation 2 simply stays in generation 2.

But now the question is, how exactly does this feature of generations, help in improving the performance?

1)  When the heap fills and a collection occurs, the garbage collector first examines and collects the objects in the Generation 0. The assumption is that the newer an object is, the shorter its lifetime is expected to be. Hence, we hope that, collecting and compacting the Generation 0 objects would free enough space on the heap to accommodate the new object. We can see that, examining and collecting objects from just the Generation 0 is much faster than if the collector had examined the objects in all the generations.

However, even if collecting objects from Generation 0 doesn't provide the required amount of space, then the collector attempts to collect the objects from generations 1 and 0.

Similarly, if the collection from both the generations 1 & 0, fails to create the required space, then the objects are collected from all the Generations-2, 1, and 0.

2) A generational collector can offer more optimizations by not traversing every object in the managed heap. If a root or object refers to an object in an old generation, the garbage collector can ignore any of the older objects' inner references, decreasing the time required to build the graph of reachable objects. Of course, it is possible that an old object refers to a new object. So that these objects are examined, the collector can take advantage of the system's write-watch support (provided by the Win32 GetWriteWatch function in Kernel32.dll). This support lets the collector know which old objects (if any) have been written to since the last collection. These specific old objects can have their references checked to see if they refer to any new objects.

Garbage Collection in Multithreaded Applications
While understanding the mechanism of Garbage Collection, as above, we made a big assumption that, only one thread is running. Though in fact under normal circumstances, there would be multiple threads accessing the managed heap or manipulating objects allocated space on the managed heap.

When the space is requested by a new object from one thread and the Collection is triggered, then it becomes important that other threads must not access any objects (including object references on its own stack) since the collector is likely to move these objects, changing their memory locations. Hence, when the garbage collector starts a collection, all threads executing managed code are suspended.

The runtime employs different mechanisms to safely suspend threads so as to keep the threads running as long as possible before the collection is performed. This is to reduce overhead as much as possible. The mechanisms that the garbage collector employs when applications have multiple threads are:

1.  Fully Interruptible Code
When a collection starts, the collector suspends all application threads and determines –
(i)   Where the thread was suspended, i.e. where in a method the thread stopped,
(ii)   What object references the code is currently accessing, and
(iii)  Where those references are held in a variable or a CPU register, etc.

2. Hijacking
When a collection occurs, the collector modifies the thread's stack, such that when a method returns, a special function is executed, to suspend the thread. When the collection is complete, the thread resumes and returns to the method that originally called it. This is called Thread Hijacking.

This thread hijacking allows threads that are executing unmanaged code to continue execution while a garbage collection is occurring. Please note, this does not cause any problem, since unmanaged code is not accessing objects on the managed heap unless the objects do not contain object references. If a thread that is currently executing unmanaged code returns to managed code, the thread is hijacked and is suspended until the Garbage Collection completes.

3. Safe Points
While compiling a method, if the just-in-time compiler finds that a Garbage Collection is pending –
(i)    It inserts a call to a function that suspends the thread,
(ii)   First the Garbage Collection is completed, and
(iii)  Then the thread is resumed.

This position where the compiler inserts these method calls is called a Safe Point.

4. Synchronization-free Allocations
On a multiprocessor system, generation 0 of the managed heap is split into multiple memory areas using one area per thread. This allows multiple threads to make allocations simultaneously so that exclusive access to the heap is not required.

5. Scalable Collections
On a multiprocessor system running the server version of the execution engine (MSCorSvr.dll), the managed heap is split into several sections, one per CPU. When a collection is initiated, the collector has one thread per CPU; all threads collect their own sections simultaneously. The workstation version of the execution engine (MSCorWks.dll) doesn't support this feature.

Finalization

Say if you want to execute a piece of code for an object, just before it is subjected to Collection by the Garbage Collector. This has been made possible by a feature of the Garbage Collector called ‘Finalization’.

Finalization allows a resource to be gracefully cleaned when it is being collected. By using finalization, a resource like a file or network connection, is able to clean itself up properly when the garbage collector decides to free the resource's memory. This is made possible by an override void Finalize () with clean up resource code in it. When the Garbage Collector recognizes that the class object is pretty much going to be a piece of garbage, it calls the Finalize() method.

public class objBase 
                      {
                              public objBase() 
                              {
                              }
                      
                              protected override void Finalize() 
                              {
                                      // Resource Cleanup Code 
                              }
                      }

Select all Open in new window

Let’s try and understand, how the Finalization works.

When we create and then instantiate an object using the 'new' operator. This ‘new’ operator first makes sure that the bytes required by the new object are available on the heap, i.e. the new object could fit on the heap. It then not only puts the object on the heap, but also checks if the object's type contains a Finalize method. If yes then a pointer to the object is placed on the Finalization Queue.
 
The Finalization Queue is an internal data structure (Queue) controlled by the garbage collector. Each entry in the queue points to an object that should have its Finalize method called before the object's memory can be reclaimed.

E.g. when the objects K, O and P were created, the system detected that these objects had Finalize methods; hence after adding these objects to the heap, the pointers to these objects were added to the Finalization Queue.
 
When the garbage collector finds the objects B, K, O, Q and S to be garbage, it scans the Finalization Queue looking for pointers to these objects. If a pointer is found, it is removed from the Finalization Queue and added to the Freachable Queue.

The Freachable Queue is another internal data structure (Queue) controlled by the garbage collector. Each pointer in the Freachable Queue identifies an object that is ready to have its Finalize method called.

Hence, we see that when the collection occurs, the memory occupied by objects B, O, and S is reclaimed because these objects did not have a Finalize method that needs to be called. However, the memory occupied by objects K and Q could not be reclaimed because their Finalize method has not been called yet and the pointers to both these objects are moved from the Finalization Queue to the Freachable Queue.
With this we reach to an understanding that, when an object is not reachable, the garbage collector considers the object garbage. Then, when the garbage collector moves an object's entry from the Finalization Queue to the Freachable Queue, the object is no longer considered garbage and its memory is not reclaimed. At this point, the garbage collector has finished identifying garbage. Some of the objects identified as garbage have been reclassified as not garbage. The garbage collector compacts the reclaimable memory and the special runtime thread empties the Freachable Queue, executing each object's Finalize method.

There is a special runtime thread dedicated to calling Finalize methods. Normally when the Freachable Queue is empty, this thread sleeps. But when the pointers are added to this queue, this thread awakes, removes each entry from the queue, and calls each object's Finalize method. Because of this, you should not execute any code in a Finalize method that makes any assumption about the thread that's executing the code. For example, avoid accessing thread local storage in the Finalize method.

In our example, we see that the pointers to objects K and Q have been moved to the Freachable Queue and their Finalize() method has been called by the thread.

Now the next time the garbage collection occurs, the Garbage Collector finds the pointers to objects K and Q in the Freacheble Queue and realizes that these finalized objects are truly garbage, and hence it goes ahead and reclaims the memory held by the objects K and Q. Please note that two iterations of the Garbage Collection process are required to free the memory space occupied by the objects that require finalization. In reality, more than two collections may be necessary since the objects could get promoted to an older generation.

 
So, we see that the Finalization process is quite fascinating, but I personally feel, it is not advisable to use this feature --
      

What about External Resources?

The garbage collector efficiently handles freeing resources from the managed heap, but a collection is only initiated when memory pressure triggers a collection. What about classes that manage limited external resources such as database connections, Windows handles or External files etc.? Waiting until a garbage collection is triggered to clean up database connections or file handles can severely degrade system performance.

Dispose Method
Microsoft has provided another alternative whereby we could use the IDisposable interface. When we implement this interface, we get a Dispose() method which can be used to convey a message to the CLR to take care of objects that are no longer required by the application.

This method can be used to close or release unmanaged resources such as files, streams, and handles held by an instance of the class that implements this interface. This method is, by convention, used for all tasks associated with freeing resources held by an object, or preparing an object for reuse.

When implementing this method, objects must seek to ensure that all held resources are freed by propagating the call through the containment hierarchy. For example, if an object A allocates an object B, and object B allocates an object C, then A's Dispose implementation must call Dispose on B, which must in turn call Dispose on C. Objects must also call the Dispose method of their base class if the base class implements IDisposable.

If an object's Dispose method is called more than once, the object must ignore all calls after the first one. The object must not throw an exception if its Dispose method is called multiple times. Dispose can throw an exception if an error occurs because a resource has already been freed and Dispose had not been called previously.

Because the Dispose method must be called explicitly, objects that implement IDisposable must also implement a finalizer to handle freeing resources when Dispose is not called. By default, the garbage collector will automatically call an object's finalizer prior to reclaiming its memory. However, once the Dispose method has been called, it is typically unnecessary for the garbage collector to call the disposed object's finalizer. To prevent automatic finalization, Dispose implementations can call the GC.SuppressFinalize method.

Using the System.GC Class

The System.GC type allows your application some direct control over the garbage collector. It is used to access the garbage collection mechanism exposed by the .NET framework. This class includes the following useful methods:
 

Reference

I have taken some references from MSDN article; ‘Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework’ by Jeffrey Richter
http://msdn.microsoft.com/en-us/library/bb985010.aspx
I found this article quite informative and hence tried to build upon it.

Garbage-Collection-Memory-Manage.docx