Partitioned Fixed-Priority Multiprocessor Scheduling for Mixed-Criticality Real-Time Systems

Abstract

The scheduling of real-time systems has been the subject of research for many years since it has many implications for safety-critical embedded real-time systems. Within that field, there have been two recent developments which are the subject of this thesis. The first is the development of new scheduling theory for mixedcriticality systems, i.e. systems in which functions of differing importance are scheduled on the same processor. The second is the increasing production use of multiprocessor systems, even in the world of embedded real-time systems. The purpose of this work is twofold. First a new schedulability test for fixedpriority mixed-criticality uniprocessor systems will be presented and evaluated. Secondly, that schedulability test will be used in an evaluation of different heuristics for partitioned multiprocessor scheduling of mixed-criticality systems. In order to evaluate the performance of the new schedulability test and the di erent heuristics in terms of schedulability, a number of experiments were performed. For this purpose random task sets were generated, and each such task set was tested for schedulability. It was found that the new uniprocessor schedulability test outperforms the previously known approaches for fixed-priority mixed-criticality task sets on preemptively scheduled uniprocessor systems. In terms of the heuristics that were evaluated for partitioning, it was determined that the combination of a slackmonotonic initial ordering with a best-fit allocation algorithm and deadline monotonic priority ordering yields the best schedulability. It seems surprising that using a deadline monotonic priority ordering outperforms Audsley's priority ordering approach. Furthermore, it was shown that a utilisation-based worst-fit task allocation algorithm is not a good heuristic for the kind of systems under assessment. Finally, the presented uniprocessor schedulability test seems to scale well with the number of processors, if the number of tasks per taskset is sufficiently high.