White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

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

Aguilar-Soto, Armando (2006) Fixed-Priority Scheduling Algorithms with Multiple Objectives in Hard Real-Time Systems. PhD thesis, University of York.

[img] Text (485332.pdf)
485332.pdf

Download (26Mb)

Abstract

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.

Item Type: Thesis (PhD)
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.485332
Depositing User: EThOS Import (York)
Date Deposited: 10 Dec 2015 17:18
Last Modified: 10 Dec 2015 17:18
URI: http://etheses.whiterose.ac.uk/id/eprint/11057

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)