Go up. Go to department page.

Real-Time Compacting Garbage Collection Algorithms


M. Bengtsson

Licentiate thesis, Lund University, Lund, Sweden, 1990.


Many programming languages provide garbage collection to reduce the need for memory management related programming. Traditional garbage collection techniques do, however, lead to long and unpredictable delays and can therefore not be used in real-time programs. In a real-time program, the maximum time for elementary operations (e.g., allocating an object and accessing an object) must be small. In order to guarantee this, garbage collection must be performed in parallel with the program and must be scheduled in such a way that the free memory never becomes exhausted.

This study deals with compacting real-time garbage collection algorithms. The first part discusses the basic algorithms mark-and-sweep, copying, and reference counting. A mark-and-sweep and a copying algorithm are analyzed and compared. The comparison is highly dependent on the ratio of reachable memory. When the ratio is small, a copying algorithm is probably more efficient in most systems while a mark-and-sweep algorithm is superior when the ratio is large. This holds for traditional batch versions of the algorithms too, but, in a real-time garbage collection system, the interval where a copying algorithm is more efficient is smaller.

The second part treats generation-based garbage collection. A generation-based algorithm intended for programs with strict real-time requirements is presented. In many systems, the algorithm is expected to have better performance than nongeneration-based algorithms. The worst-case performance, however, is worse. In order to evaluate and tune the algorithm, measurements of object lifetimes and number of references between object generations have been performed on Simula programs. The measurements confirm that the average lifetime of objects is very short and that there are few references from older to younger generations.