On Fixed Priority Preemptive Scheduling for Imprecise Computation

We present new results in hard real-time fixed priority scheduling for real-time AI systems. Anytime algorithms have issues rooted from the task model and lack of related system level supports while contract anytime algorithms require strict resource reservations a priori but no hard system timing guarantees are provided in previous works in terms of real-time systems scheduling. Audsley et al. devised schedulability tests for guaranteeing mandatory computation while incorporating unbounded optional components. In particular, the task model is defined to be of the form `Prologue-Optional-Epilogue', which is a generalisation of the traditional `Mandatory-Optional' task model of Liu el al. The model is shown to be useful in constructing hybrid anytime algorithms of a more general `Contract-Anytime-Contract' structure. However, problems are discovered which can make calculation of task's worst-case response time inaccurate. Besides presenting the problem and proposing the required fixes, we proved the tests can be simplified under deadline monotonic priority ordering. We also propose a novel scheduling scheme, based on Dual Priority Scheduling, to maximize the scheduling of unbounded optional components, along with the required schedulability tests. The application of the new scheme shows substantial improvement. With its basis on fixed priority scheduling, it is expected the scheme can be easily incorporated into existing real-time operating systems and provokes wider use of anytime algorithms and imprecise computing.