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.