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

Taehyoun Kim, Naehyuck Chang, Heonshik Shin

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations


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.

Original languageEnglish
Article number852450
Pages (from-to)46-55
Number of pages10
JournalReal-Time Technology and Applications - Proceedings
StatePublished - 2000
Event6th IEEE Real-Time Technology and Applications Symposium, RTAS 2000 - Washington, DC, United States
Duration: 31 May 20002 Jun 2000


Dive into the research topics of 'Bounding worst case garbage collection time for embedded real-time systems'. Together they form a unique fingerprint.

Cite this