Inserting Placeholder Slack to Improve Run-Time Scheduling of Non-preemptible Real-Time Tasks in Heterogeneous Systems

This paper proposes a method to pre-schedule slack windows in a non-preemptive heterogeneous system that executes a mix of hard-periodic and soft-aperiodic tasks. The goal is to improve the acceptance rate and waiting time of aperiodic tasks without violating periodic task deadlines. The method creates an offline schedule of periodic tasks and pre-scheduled slack that models the estimated characteristics of the aperiodic tasks. At runtime, the local schedulers use this offline schedule to guide their decisions to adjust periodic task instance start times and to schedule aperiodic tasks arriving from the global scheduler. We evaluate several dynamic local schedulers. Our results show that token-based dynamic schedulers are particularly effective for reducing waiting time and increasing acceptance rate when attempting to maintain aperiodic task execution fairness.