Joint scheduling of garbage collector and hard real-time tasks for embedded applications

Programs with complex data structures often require dynamic memory manageme nt based on automatic memory reclamation (garbage collection). A major prob lem in adopting garbage collection for embedded real-time systems is that i t often causes unpredictable pauses and that, as a result of such delays, h ard real-time tasks may miss their deadlines. In this paper, we propose a n ew real-time garbage collection technique for embedded applications. In our approach, the system jointly schedules garbage collector and hard real-tim e tasks using one of the aperiodic server approaches. Our study focuses on reducing memory requirements while guaranteeing the deadlines of hard real- time tasks. To achieve this objective, we model garbage collection requests as aperiodic hard real-time tasks, and schedule them using the sporadic se rver (SS). We also present an effective live-memory analysis to bound the w orst-case garbage collection time. Performance analysis shows that the prop osed approach considerably reduces the worst-case memory reservation compar ed with a background policy. The analytic results are verified by simulatio n based on trace-driven data. (C) 2001 Elsevier Science Inc. All rights res erved.