Garbage
Collection Internals - I |
| |
Author
: Thomas Kurian Ambattu |
| |
| |
| Hope
you all got a basic idea on Garbage Collection from the
previous article. In this article I’ll explain the
Garbage Collection Algorithm. This is the continuation
of the first article Introduction
to Garbage Collection,
so those of you who have not read it I suggest you to
read that before you go through this article. |
| |
| Consider
a situation where there is no space in the heap for the
newly allocated object. If no more memory is available
the new operator throws OutOfMemoryException. Before this
the GC looks for the memory which can be freed to reclaim
the memory. The apt time to perform a collection is decided
by the GC’s optimizing engine. To carryout a collection
the GC has to know the location of application’s
root, which means the GC has to know when an object is
no longer used by the application. This information is
made available to the GC is with the concept called metadata
in .NET. Metadata is nothing but data which describes
data |
| |
| Every
application has set of roots. Roots identify storage locations,
which refer to objects on the managed heap or to objects
that are set to null. All the global and static object
pointers in an application are considered part of the
application's roots. Any local variable/parameter object
pointers on a thread's stack and any CPU registers containing
pointers to objects in the managed heap are also considered
part of the application's roots. The just-in-time (JIT)
compiler and (CLR) Common Language Runtime maintain the
list of active roots and is made accessible to the GC’s
algorithm. Each and every datatype in .NET has a metadata
that describes it. The CLR (Common Language Runtime) makes
a layout of each of the object in memory with the help
of this metadata. This layout helps the GC in the mechanism
of collection. Without this information the GC won’t
be able to know where an object instance ends and the
next one begins. |
| |
| When
the GC starts running it makes a default assumption that
all objects in the heap are garbage that means it assumes
that none of the application’s root refer to any
objects in the heap. The next thing what GC does is it
starts walking down the heap and make a graph of all objects
that is reachable from the heap. |
| |
| The
figure below shows a heap with objects which a referred
by application’s root. As the GC walks down all
these become the part of the graph. Object A, C,E, H is
referred by application’s root. As the GC walk down
when it reached C it found that C refers to another object
G and now GC immediately adds this also to the graph.
The GC continues its journey through all reachable objects
recursively. |
| |
 |
| |
| Now
the GC looks for the next root and start walking though
the objects. As it travels from object to object if the
GC attempts to add an object that is already present in
the graph then it suddenly stops walking further down,
this makes sure that the GC doesn't walk through a set
of objects more than once and also it prevents infinite
loops should you have any circular linked lists of objects. |
| |
| Once
all the roots have been checked the GC now have a layout
of all the objects that are reachable from the application’s
root. GC assumes that the objects that are not in the
graph are garbage. The GC now walks through the heap linearly,
looking for contiguous blocks of garbage objects (now
considered free space). The non-garbage objects are shifted
down in memory removing all gaps (free spaces). We have
a problem the shifting that we told just now causes the
invalidation of pointers to objects, don’t worry
about that, the GC will correct this by modifying the
application’s root. |
| |
| Now
all the garbage have been identified and the pointers
are fixed up and our NextObjPointer (hope you remember
it ! we saw it in the first article) is positioned just
after the non Garbage Object and everything is fine. |
 |
| |
| |
| |
| I’ll
discuss about Finalization& Generations in my next
articles Garbage Collection
Internals II & III. Do mail me your
feedback on this article to feedback@netkidoos.com.
All suggestions & views will be appreciated. |
| |
| |
| |
