moyano.proGlobal Scheduling of Weakly-Hard Real-Time Tasks using Job-Level Priority Classes.
-
Authors: V. Gabriel Moyano, Zain A. H. Hammadeh, Selma Saidi, and Daniel Lüdtke
-
Published in: ACM Transactions on Embedded Computing Systems, [2026]
-
Abstract:
Real-time systems are intrinsic components of many pivotal applications, such as self-driving vehicles, aerospace and defense systems. The trend in these applications is to incorporate multiple tasks onto fewer, more powerful hardware platforms, e.g., multi-core systems, mainly for reducing cost and power consumption. Many real-time tasks, like control tasks, can tolerate occasional deadline misses due to robust algorithms. These tasks can be modeled using the weakly-hard model. Literature shows that leveraging the weakly-hard model can relax the over-provisioning associated with designed real-time systems. However, a wide-range of the research focuses on single-core platforms. Therefore, we strive to extend the state-of-the-art of scheduling weakly-hard real-time tasks to multi-core platforms. We present a global job-level fixed priority scheduling algorithm together with its schedulability analysis. The scheduling algorithm leverages the tolerable continuous deadline misses to assigning priorities to jobs. The proposed analysis extends the Response Time Analysis (RTA) for global scheduling to test the schedulability of tasks. Hence, our analysis scales with the number of tasks and number of cores because, unlike literature, it depends neither on Integer Linear Programming nor reachability trees. Schedulability analyses show that the schedulability ratio is improved by 40% comparing to the global Rate Monotonic (RM) scheduling and up to 60% more than the global EDF scheduling, which are the state-of-the-art schedulers on the RTEMS real-time operating system. Our evaluation on industrial embedded multi-core platform running RTEMS shows that the scheduling overhead of our proposal does not exceed 60 Nanosecond.
Sufficient Schedulability Condition for Scheduling Weakly-Hard Real-Time Tasks Considering Job-Kill and Skip-Next Strategies.
-
Authors: V. Gabriel Moyano, Zain A. H. Hammadeh, Daniel Lüdtke, and Michael Felderer
-
Published in: ACM SIGAPP Applied Computing Review, Volume 25, Issue 3, [2025]
-
Abstract:
Real-time tasks, especially control tasks, can often tolerate occasional missed deadlines due to robust algorithms. The weakly-hard model offers an approach for specifying the maximum number of tolerable deadline misses mi within a sequence of Ki executions. Research has shown that utilizing the weakly-hard model can significantly reduce the over-provisioning typically required in real-time system design. This led to the development of various scheduling algorithms and schedulability analyses in recent years. However, existing state-of-the-art analyses have limitations: they do not scale with larger values of Ki and focus solely on job-kill as a system-level action. We propose a new job-level fixed priority scheduling algorithm that overcomes these limitations. Our approach first considers the traditional job-kill method but then extends to a skip-next job strategy in case of deadline miss. The schedulability analysis of our algorithm scales with Ki, reducing computational time by up to 100 times compared to existing approaches.
Efficient Scheduling of Weakly-Hard Real-Time Tasks with Sufficient Schedulability Condition.
-
🏆 Best Paper: System Software & Security
-
Authors: V. Gabriel Moyano, Zain A. H. Hammadeh, Selma Saidi, and Daniel Lüdtke
-
Published in: SAC ‘25: 40th ACM/SIGAPP Symposium on Applied Computing, [2025]
-
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.