When a system has a garbage collector it is usually part of the language run-time system and integrated into the language. The language is said to be garbage collected. Garbage collection was invented by John McCarthy as part of the first Lisp system. It is a bit sloppy to talk of a garbage collected language just as it is slightly incorrect to talk of a compiled language. Being garbage collected is a property of an implementation of a language.
|
(liveness vs reachability)
Garbage collectors use a reachability-based criterion for determining whether a data object will be needed (but see note about reference counting below).
In other words a reachable object is one that the program could get to by following a chain of pointer references.
The tricolour invariant is an important property of the objects and their colours. It is simply this:
Notice that the algorithm above preserves the tricolour invariant. The initial partition has no black objects, so the invariant trivially holds. Subsequently whenever an object is made black any white objects that it references are made grey, ensuring that the invariant remains true. When the last step of the algorithm is reached, because the tricolour invariant holds, none of the objects in the black set point to any of the objects in the white set (and there are no grey objects) so the white objects must be unreachable from the roots, and the system calls their finalisers and frees their storage.
Some variations on the algorithm do not preserve the tricolour invariant but they use a modified form for which all the important properties hold.
Mark and sweep
Collectors can also be divided by considering how the three sets (of white, grey, and black objects) are implemented. A Mark sweep GC[?] maintains a bit (or two) with each object to record whether it is white or black; the grey set is either maintained as a separate list or using another bit. A Copying GC[?] identifies grey and black objects by copying them to another area of memory (the copy space) and often distinguishes black from grey objects by dividing the copy space into two portions (in the simple case by maintaining a single pointer that marks the division between black and grey objects).
Generational GC
There is the issue of when to perform a cycle and what objects to place in the initial grey set. A simple collector will always put only the roots in the initial grey set, and everything else will be initially white.
Statistically speaking, the objects most recently created in the runtime system are also those most likely to quickly become unreachable. A Generational GC[?] divides objects into generations and will generally only place the objects of a subset of all the generations into the initial white set (the grey set being everything else). This can result in faster cycles.
Reference counting
Reference counting is commonly referred to as garbage collection, but this usage is not accepted by all. It could probably be argued that reference counting is a class of conservative garbage collection. Some punters like to reserve the term garbage collection for algorithms and systems that determine the liveness of data based on reachability.
Reference counting has serious problems anyway, such as a general inability to deal with circular references and a high overhead in both space and time. On the other hand, it does dispose of most garbage fairly promptly, which can have advantages if there are finalisers to be run to free up scarce resources other than heap memory. Hybrid systems that use reference counting to achieve (mostly) immediate freeing of resources, and occasionally call a mark-sweep collector to free stuff containing reference loops, have been proposed and occasionally implemented. This gives the best of both worlds in some ways, but still has a performance overhead.
Search Encyclopedia
|
Featured Article
|