A generalized framework for hierarchical real-time scheduling

Abstract

Most real-time systems allow concurrent execution of different applications and it is necessary to guarantee that the timing requirement of each application is met. One way to ensure this is to compose all the applications with a unique scheduling paradigm at the system level and modify the applications to suit the chosen paradigm. But most often, it is desirable to keep the implemented application and determine the feasibility of scheduling the application in conjunction with other applications. The problem gets more involved as we try to compose applications that come with their own scheduling strategy. An alternate approach to compose existing applications with different timing characteristics is to use a two-level scheduling paradigm, comprising of a global scheduler at the system level and a local scheduler for each application. The global scheduler selects the application that will be executed next and assigns to it a fraction of the total processor time according to certain criteria and the scheduler is feasible only if it preserves the temporal guarantees of the local scheduling models. Each local scheduler schedules tasks within the application. Such hierarchical composition of schedulers allows for maximum flexibility in the design of systems with a mix of tasks, each having different timing constraints. A considerable amount of work has been recently addressed to the analysis of these kind of hierarchical systems. Various resource reservation schemes have been proposed and the notion of real-time virtual resources gives a very flexible parameterization of resource partitions. We propose a generalized framework for hierarchical scheduling that permits resource partitioning to be extended to multiple levels. In constructing the hierarchical scheduling framework we intend to combine the advantages offered by the notion of virtual resources with the flexibility of real-time calculus in accommodating non-standard event models and permitting re-use of unused computation capacity. The framework handles a wider range of task models and permits data dependencies among tasks and task groups.