Bounding worst case garbage collection time for embedded real-time systems

Execution of programs with various data structures often requires dynamic memory management based on garbage collection for better productivity, robustness and program integrity. In spite of its benefits, garbage collection has not been widely used in embedded real-time systems partly because it often causes unpredictable pause delay. Guaranteeing real-time operations with garbage collection aims to bound and estimate the worst case computation time of a garbage collector as well as application tasks. We introduce a new technique for bounding and estimating the worst case garbage collection time in light of task scheduling. Since the worst case live memory is the dominant factor to determine the worst case garbage collection time, we quantify the worst case live memory using the states of periodic tasks. We also present a predictable real-time copying collection algorithm in order to assess the effectiveness of the proposed approach. Performance evaluation shows that the proposed approach provides a safe and effective bound on the garbage collection time, thus reducing the upper bound of live memory size by up to 35% compared with the trivial bound. It also demonstrates that our algorithm can accomplish 7/spl sim/14% reduction in the memory requirement.