Reference counting done correctly
By Frans
Why did Microsoft choose for garbage collection in their
new .Net platform? Is their an alternative?
It is a fact that the Java is also using garbage collection
for freeing the memory used by object that are no longer
accesible. And it is also a fact that .Net is Microsofts
version of Java.
Problems with garbage collection
But what are the problems with garbage
collection? In .Net the destructor is only called when the
object is removed during garbage collection. Because the
destructor is only called long after the object has
become unreachable from the program (execution unit), it
cannot be used to perform certain tasks. This means that
in some cases a finish method needs to be implemented.
Especially for Managed C++ this has great implications,
because the destructor is no longer called when the delete
operator is called, as it is in normal C++. (This is one
of the reasons why Managed C++ does no longer adhere to
the ANSI C++ standard.)
In C# the finish method is called Dispose, and with
the using statement, calling of the Dispose methode can be
enforced. Forgetting to use the using method, can lead to
introduce tricky bugs.
Another problem with garbage collection is that it is
an expensive operation, which cannot performed parallel
to normal program execution. It is usually initiated when
system resources are running out or when the system is
idle. This means that at undeterministic moments the
execution is delayed for a short time to give room for
a garbage collection to be taken place. This is the reason
why garbage collections in a real-time environment are
avoided.
Why is garbage collection used at all?
A good question is, why is garbage collection implemented
at all. Why not simply free the memory of an object that
is being deleted (as it is done in C++)? There is one good
reason, and that is that it is still possible that some
other object is still referencing the object. And that causes
serious problems in case you want to create a safe execution
environment, because it creates a reference to a pointer
to a piece of memory which is no longer in use, and is
likely to be used for some other object in the future.
Memory should thus only be deleted when it is no longer
referenced to.
Reference counting
One of the most simply ways of keeping track if a piece
of memory is being referenced, is to count the number
references to it. (A problem with this is that one has to
establish a upper limit of the maximum number of
simultanious references to a piece of memory. In most
cases it is possible to establish such an upper limit.)
But simple reference counting can keep memory allocated
that cannot be reached any more. This is the result of
circular references. Take for example a tree structure
where the children contain a reference to their parent
(which is a very common thing to happen). Now when a
node with child node is removed, it is not freed because
all child nodes still have a reference to the parent node.
A garbage collection algorithm would free such objects,
because it will discover that the node and all the child
nodes (and all all possible other nodes below it) cannot
be reached anymore, and can be flagged for deletion.
The reference from a parent node to a child node is a
different kind of reference then that of the child node
to its parent. Actually, there are three kinds of
references:
- Component references (from parent to child nodes)
- Reverse component references (from child nodes to
on of their parents)
- Aggregration references (between nodes that do
not have a component relationship)
Because a component cannot be a part of itself, the
component references form an acyclic directed graph or tree,
depending on whether a child can have more than one
parent or not. (The case that each child has at most one
parent, does offer a number of important advantages will
be discussed below.) It is obvious
that an object can be deleted if it only has reverse
component references to it. Thus reverse component references
do not need to be counted. But excluding them from the
count does not solve the problem. Although component
references do not form cycles, the combination of
component and aggregation reference still can.
The aggregration references can be divided into claiming
and non-claiming. A claiming aggregration reference,
means that the object being referenced should not be
deleted as long as the reference still exists.
A non-claiming aggregration reference should be removed
(or made null) whenever the object being referenced is
deleted.
Implementation of non-claiming aggregration references
The most obvious implementation keeps with each object
a list of places that have a non-claiming aggregration
reference to it. For performance reasons, it can be
wise to use a double-linked list. That would
introduce two additional pointers for each place where a
non-claiming aggregration reference occurs, and one
additional pointer for the object being referenced.
This implementation is rahter expensive in use
of memory and in terms of execution time, because
several pointers need to be updated whenever references
are made or removed.
An alternative implementation, is to make us of delayed
deletion. The idea is not to remove the non-claiming
aggregration reference immediately, but only when it is
followed. For this to work, the object should be marked
as deleted, and the memory it uses should not be freed
until all aggregration references have been removed.
For this we need a counter again. For this implementation
two counters need to be used for each object that is
being referenced. One counter for the composite and
claiming aggregration references, and one for the
non-claiming aggregration references. When the first
counter is zero, it means that the object has been
deleted, and that non-claiming aggregration references
should be deleted. Only when both counters are zero,
the memory is freed.
A disadvantage of this approach is that it can take a
very long time, until memory is freed of objects which
have already been deleted, because non-claiming aggregration
references are only freed when they are followed.
(A solution would be a garbage-collection like algorithm
that would check all non-claiming aggregration references
to see if they need to be removed.)
Cleaning-up
Of course, the above strategy only works if all
references are nicely removed, otherwise the counters
never are reset to zero, and the memory is never freed.
This means that whenever an object is deleted, all
references it has to other objects should be removed.
In practice claiming aggregration references are quite
common. An object may not be deleted, when one of its
components still has a claiming aggregration reference
to it. One can either check this on deletion or to propagate
each claiming aggregration reference up to all its
parents (in the component hierarchy). Which of the two
methods should be used, depends on the nature of the
object model and the possible number of child objects
an object can have. For the latter methode to work,
objects need to have a reference to their parent objects.
If an object have at most one parent, this can be easily
stored in the object. If more than one parent object is
allowed, a list is needed of reverse component references
to the parents. Note that only the object to which there,
or to one of its (nested) children, a claiming aggregration
reference can occur, needs to have reverse component
references to its parents.
In case objects can have multiple parents, there is a
need for splitting the counter for the component references
and the claiming aggregration references into two separate
pointers. The (recursive) procedure to check if a
component reference to an object can be removed, can
conclude it is okay, if the object still has another parent.
If this is not the case, it is not okay if there is a
claiming aggregration reference to the object. If this
is also not the case, then the procedure has to be
called on all the child objects it has component references
to.
Preventing cyclic component references
Above it was assumed that if the
component references form an acyclic directed graph
(or tree). But something has to be done to prevent
cyclic component references to occur. The most easy
way to prevent them is to enforce that each object
has at most one parent, and that child objects may
not switch parents.
Without these restrictions, it is difficult to prevent
cyclic component references automatically. Just blindly
checking if a cyclic is introduced with a mutation,
can be very expensive. Assiging level numbers to objects
such that all child objects have a lower number than
their parents could help. Keeping the numbering consistent
during updates is not trivial, but doable.
Smart pointers
More software engineering stories