Zero-Jitter Semi-Fixed-Priority Scheduling with Harmonic Periodic Task Sets

摘要

Real-time systems such as humanoid robots require lowrnjitter and high Quality of Service (QoS). An impreciserncomputation is one of the solutions to improve QoS butrndynamic-priority imprecise real-time scheduling has highrnjitter. Semi-fixed-priority scheduling was presented tornachieve low jitter and high QoS for imprecise computation.rnUnfortunately, a semi-fixed-priority scheduling algorithm,rncalled Rate Monotonic with Wind-up Part (RMWP), has highrnjitter if the actual case execution time (ACET) of each task isrnshorter than its worst case execution time (WCET). Wernpropose a new semi-fixed-priority scheduling algorithm,rncalled Rate Monotonic with Wind-up Part++ (RMWP++), tornachieve the zero-jitter of each task with harmonic periodicrntask sets. The zero-jitter technique adds the previous and postrnoptional parts to the extended imprecise computation modelrnthat has a second mandatory (wind-up) part. We prove thatrnthe jitter of each task in RMWP++ is always zero and the leastrnupper bound of RMWP++ is one with harmonic periodic taskrnsets on uniprocessors. Simulation results show that RMWP++rnachieves the zero-jitter and has a smaller number of contextrnswitches than RMWP, if the ACET of each task is shorter thanrnits WCET.