Efficient Scheduling of Weakly-Hard Real-Time Tasks with Sufficient Schedulability Condition

Abstract

Many real-time tasks, particularly control tasks, can accommodate occasional missed deadlines thanks to robust algorithms. These tasks can be effectively modeled using the weakly-hard model, which specifies the maximum number of tolerable deadline misses, denoted as mi, within a sequence of Ki executions. Research indicates that utilizing the weakly-hard model can significantly reduce the over-provisioning typically required in the design of real-time systems. Therefore, different scheduling algorithms and schedulability analyses have been proposed in the last few years. However, state-of-the-art scheduling analyses do not scale with larger values of Ki. We present a new job-level fixed priority scheduling algorithm whose schedulability analysis scales with Ki. Furthermore, our scheduling algorithm leverages the tolerable continuous deadline misses to assigning priorities to jobs. Schedulability analyses show that the computation time of our analysis is up to 100 times faster comparing to the approaches in literature improving also the schedulability ratio for total utilization of 0.9.