Hierarchical Fixed Priority Pre-emptive Scheduling

This report focuses on the hierarchical scheduling of systems where a number of separate applications reside on a single processor. It addresses the particular case where fixed priority pre-emptive scheduling is used at both global and local levels, with periodic or deferrable servers associated with each application. Using response time analysis, an exact schedulability test is derived for application tasks. This test improves on previously published work. The analysis is extended to the specific case of harmonic tasks that can be bound to the release of their server. These tasks exhibit improved schedulability indicating that it is advantageous to choose server periods that enable some tasks to be bound to the release of their server. The use of Periodic, Sporadic and Deferrable Servers is considered with the conclusion that the simple Periodic Server dominates both Sporadic and Deferrable Servers when the metric is application task schedulability. As an adjunct some interesting results are presented on the optimal priority ordering of a set of Deferrable Servers, rate-monotonic priority ordering is not optimal in this case. The second part of the report investigates the problem of selecting the optimal set of server parameters. Analysis of this problem reveals a simple method for determining the optimal set of server capacities given fixed server periods and priorities. Despite this advance, empirical results show that server parameter selection exhibits dependencies between the set of servers and so the locally optimum selection of parameters for one server often does not result in an overall selection of parameters that is either schedulable or results in the maximum remaining system utilisation. The selection of server parameters is a holistic problem that may in practice only be soluble via search; a greedy approach to parameter selection is demonstrated to be ineffective.