An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks
Beyazit Yalcinkaya1,2, Mitra Nasri1,3 and Björn B. Brandenburg1
1Max Planck Institute for Software Systems (MPI-SWS), Germany
2Middle East Technical University, Turkey
3Delft University of Technology, Netherlands
ABSTRACT
Exact schedulability analysis of limited-preemptive (or non-preemptive) real-time workloads with variable execution costs and release jitter is a notoriously difficult challenge due to the scheduling anomalies inherent in non-preemptive execution. Furthermore, the presence of self-suspending tasks is well-understood to add tremendous complications to an already difficult problem. By mapping the schedulability problem to the reachability problem in timed automata (TA), this paper provides the first exact schedulability test for this challenging model. Specifically, using TA extensions available in UPPAAL, this paper presents an exact schedulability test for sets of periodic and sporadic self-suspending tasks with fixed preemption points that are scheduled upon a multiprocessor under a global fixedpriority scheduling policy. To the best of our knowledge, this is the first exact schedulability test for non- and limited-preemptive self-suspending tasks (for both uniprocessor and multiprocessor systems), and thus also the first exact schedulability test for the special case of global non-preemptive fixed-priority scheduling (for either periodic or sporadic tasks). Additionally, the paper highlights some subtle pitfalls and limitations in existing TAbased schedulability tests for non-preemptive workloads.
