Non-disruptive Garbage Collection
To be able to provide non-disruptive garbage collection, it is
necessary to use an incremental algorithm that runs for a fixed amount
of time and ensures that further memory allocation requests won't
fail. Unfortunately, real-time algorithms [1,2] usually rely on
additional processors or huge amounts of memory so that they can run
copying type collectors. The Wallace-Runciman [3] algorithm combines
mark-during-sweep where portions of the heap are marked and then swept
as the mark phase works on the next region, and stack collect, a
modified mark-sweep where states of the marking phase are pushed on a
stack. Stack-collect avoids mark-during-sweep worst case execution
time behavior which is quadratic to the size of the heap. This
algorithm has a small 3 bits per cell overhead, can operate with very
small stack depth, and its execution time is bounded. Unfortunately,
its execution time accounted for 30%-45% of an application run time in
early implementations, targeting a functional language and assuming a
heap exclusively made of binary cells.
Baker's [5] incremental copying algorithm is a popular real-time
collector that doesn't really fit in a embedded environment. It
requires at least twice the minimum amount of memory in order to be
implemented. Wilson and Johnstone [4] devised a incremental
non-copying implicit reclamation collector that meets real-time
constraints. It uses a write barrier to mark pointers to non-examined
objects stored in cells that have already been examined so they are
later re-examined by the collector. This is combined with a
non-copying implicit reclamation strategy where unreached objects
don't need to be traversed in order to be reclaimed. The main cost
resides in the necessity of maintaining data structures used to keep
track of reachable cells in order to deduce unreachable (garbage)
objects. The algorithm can be altered in order to fight the
fragmentation it naturally induces and requires a strong cooperation
from the runtime system side (or the compiler) to implement the write
barriers efficiently.
|
