A hard look at hard real-time garbage collection

The author reviews the literature on the use of garbage collection in real-time systems. The author concentrates on hard real-time systems, where we ideally construct mathematical proofs of correctness and of timing properties. In particular, the author examines the interaction of overheads imposed on mutator operations by garbage collection algorithms on worst-case execution time analyses of real-time threads performing those operations. In recent years there has been a shift from work-based to time-based approaches. This paper explains and motivates this shift, and reviews examples, problems, and advantages of example algorithms from each approach. Finally, the author examines what extensions to programming verification technology might be necessary to prove that sufficient memory space exists to run a real-time system with the same rigor that one proves that sufficient time exists in a real-time schedule