Optimal priority assignment for aperiodic tasks with firm deadlines in fixed priority pre-emptive systems

doi:10.1016/0020-0190(94)00200-I

Information Processing Letters

Volume 53, Issue 5, 10 March 1995, Pages 249-254

https://doi.org/10.1016/0020-0190(94)00200-I Get rights and content

Abstract

An optimal priority assignment policy is presented for independent aperiodic tasks with arbitrary ready times and firm deadlines, scheduled on a uniprocessor along with a set of hard periodic/sporadic tasks. The latter tasks are assumed to have been assigned unique fixed priorities according to some arbitrary policy and guaranteed, via off-line feasibility analysis, to meet their deadlines. In contrast, priority assignment and acceptance testing of aperiodic tasks must be carried out on-line.

The priority assignment policy introduced is shown to be optimal both in terms of maximising the computation time which can be made available before the aperiodic deadline and with respect to guaranteeing subsequent aperiodic arrivals.

References (11)

Y.S Kim
An optimal scheduling algorithm for pre-emptable real-time tasks
Inform. Process. Lett.
(1994)
R.I Davis et al.
Mechanisms for enhancing the flexibility and utility of hard real-time systems
R.I Davis et al.
Scheduling slack time in fixed priority pre-emptive systems
J.R Jackson
Scheduling a production line to minimise maximum tardiness
J.P Lehoczky et al.
An optimal algorithm for scheduling soft-aperiodic tasks fixed-priority preemptive systems

There are more references available in the full text version of this article.

Cited by (12)

A review of priority assignment in real-time systems
2016, Journal of Systems Architecture
It is over 40 years since the first seminal work on priority assignment for real-time systems using fixed priority scheduling. Since then, huge progress has been made in the field of real-time scheduling with more complex models and schedulability analysis techniques developed to better represent and analyse real systems. This tutorial style review provides an in-depth assessment of priority assignment techniques for hard real-time systems scheduled using fixed priorities. It examines the role and importance of priority in fixed priority scheduling in all of its guises, including: pre-emptive and non-pre-emptive scheduling; covering single- and multi-processor systems, and networks. A categorisation of optimal priority assignment techniques is given, along with the conditions on their applicability. We examine the extension of these techniques via sensitivity analysis to form robust priority assignment policies that can be used even when there is only partial information available about the system. The review covers priority assignment in a wide variety of settings including: mixed-criticality systems, systems with deferred pre-emption, and probabilistic real-time systems with worst-case execution times described by random variables. It concludes with a discussion of open problems in the area of priority assignment.
A lazy algorithm for distributed priority assignment in real-time systems
2011, Proceedings - 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops, ISORCW 2011
Energy-efficient static priority and speed assignment for real-time tasks with non-deterministic release times
2010, Proceedings - 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2010
Optimal period and priority assignment for a networked control system scheduled by a fixed priority scheduling system
2007, International Journal of Automotive Technology
Robust priority assignment for fixed priority real-time systems
2007, Proceedings - Real-Time Systems Symposium
Optimal time-variant resource allocation for internet servers with delay constraints
2005, Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS

View all citing articles on Scopus

View full text

Optimal priority assignment for aperiodic tasks with firm deadlines in fixed priority pre-emptive systems

Abstract

Inform. Process. Lett.

Mechanisms for enhancing the flexibility and utility of hard real-time systems

Scheduling slack time in fixed priority pre-emptive systems

Scheduling a production line to minimise maximum tardiness

An optimal algorithm for scheduling soft-aperiodic tasks fixed-priority preemptive systems