Zero-jitter semi-fixed-priority scheduling with harmonic periodic task sets

Real-time systems such as humanoid robots require low jitter and high Quality of Service (QoS). An imprecise computation is one of the solutions to improve QoS but dynamic-priority imprecise real-time scheduling has high jitter. Semi-fixed-priority scheduling was presented to achieve low jitter and high QoS for imprecise computation. Unfortunately, a semi-fixed-priority scheduling algorithm, called Rate Monotonic with Wind-up Part (RMWP), has high jitter if the actual case execution time (ACET) of each task is shorter than its worst case execution time (WCET). We propose a new semi-fixed-priority scheduling algorithm, called Rate Monotonic with Wind-up Part++ (RMWP++), to achieve the zero-jitter of each task with harmonic periodic task sets. The zero-jitter technique adds the previous and post optional parts to the extended imprecise computation model that has a second mandatory (wind-up) part. We prove that the jitter of each task in RMWP++ is always zero and the least upper bound of RMWP++ is one with harmonic periodic task sets on uniprocessors. Simulation results show that RMWP++ achieves the zero-jitter and has a smaller number of context switches than RMWP, if the ACET of each task is shorter than its WCET.