Fixed-Priority Scheduling Algorithms with Multiple Objectives in Hard Real-Time Systems

In the context ofFixed-Priority Scheduling in Real-Time Systems, we investigate scheduling
mechanisms for supporting systems where, in addition to timing constraints, their performance
with respect to additional QoS requirements must be improved. This'type of
situation may occur when the worst-case res~urce requirements of all or some running
tasks cannot be simultaneously met due to task contention.
. Solutions to these problems have been proposed in the context of both fixed-priority
and dynamic-priority scheduling. In fixed-priority scheduling, the typical approach is to
artificially modify the attributes or structure of tasks, and/or usually require non-standard
run-time support. In dynamic-priority scheduling approaches, utility functions are employed
to make scheduling decisions with the objective of maximising the utility. The
main difficulties with these approaches are the inability to formulate and model appropriately
utility functions for each task, and the inability to guarantee hard deadlines without
executing computationally costly algorithms.
In this thesis we propose a different approach. Firstly, we introduce the concept of
relative importance among tasks as a new metric for expressing QoS requirements. The
meaning of this importance relationship is to express that in a schedule it i~ desirable to
run a task in preference to other ones. This model is more intuitive and less restrictive
than traditional utility-based app~oaches. Secondly, we formulate a scheduling problem
in terms of finding a feasible assignment of fixed priorities that maximises the new QoS
metric, and propose the DI and DI+ algorithms that find optimal solutions.
By extensive simulation, we show that the new QoS metric combined with the DI algorithm
outperforms the rate monotonic priority algorithm in several practical problems such
as minimising jitter, minimising the number of preemptions or minimising the latency. In
addition, our approach outperforms EDF in several scenarios.