Precautious-RM: A predictable non-preemptive scheduling algorithm for harmonic tasks

A major requirement of many real-time embedded systems is to have time-predictable interaction with the environment. More specifically, they need fixed or small sampling and I/O delays, and they cannot cope with large delay jitters. Non-preemptive execution is a known method to reduce the latter delay; however, the corresponding scheduling problem is NP-Hard for periodic tasks. In this paper, we present Precautious-RM as a predictable linear-time online non-preemptive scheduling algorithm for harmonic tasks which can also deal with the former delay, namely sampling delay. We derive conditions of optimality of Precautious-RM and show that satisfying those conditions, tight bounds for best- and worst-case response times of the tasks can be calculated in polynomial-time. More importantly, response time jitter of the tasks is analyzed and it is proven that under specific conditions, each task has either one or two values for response time, which leads to improving the predictability of the system interaction with the environment. Simulation results demonstrate efficiency of Precautious-RM in increasing accuracy of control applications.