Predictable Run Time Scheduling

Abstract

<p> Hybrid task-lists are sets of periodic and asynchronous processes. To verifiably schedule hybrid tasks-lists with hard and soft real-time requirements, Xu and Lam proposed Integrated Pre-Run-Time scheduling (IPRTS) [13], a two phase method that first makes use of pre-run-time scheduling techniques, converting some asynchronous tasks with hard deadlines to periodic tasks and reserving processor capacity for the remaining hard deadline asynchronous tasks. These remaining asynchronous tasks are scheduled by a novel run-time scheduler that enforces arbitrary exclusion relations between any combination of periodic and asynchronous processes. The technique has two significant drawbacks: (i) a custom run-time scheduler is required that is not available on existing Real-Time Operating Systems (RTOS) and (ii) in many circumstances the reservation of processor capacity is overly pessimistic, causing the failure of the method for many simple task lists. To overcome these drawbacks, this thesis narrows the set of task-lists considered to those where the asynchronous tasks exclude periodic tasks and periodic processes do not exclude asynchronous tasks. A high priority polling server is then used to handle all hard asynchronous tasks. In cases where the method succeeds, it is easily implementable on any RTOS that has priority based scheduling with phased release times, and inherits the error handling and soft real-time process scheduling capabilities of the RTOS. A set of software tools which partially automates the technique, including an open source implementation of the Xu-Parnas pre-run-time scheduling algorithm [14], has been developed and applied to the examples in the thesis.</p>