Optimal Priority Assignment for Aperiodic Tasks with Firm Deadlines in Fixed Priority Pre-emptive Systems

Robert Davis and Alan Burns

Real-Time Systems Research Group,
Department of Computer Science, University of York, Y01 5DD, England.

Email: [email protected]

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 w.r.t. guaranteeing subsequent aperiodic arrivals.

Key words: Real-Time, Scheduling, Algorithms, Priority Assignment.

1. Introduction

In this paper, we discuss the priority assignment and acceptance testing of aperiodic tasks with firm deadlines. We introduce an optimal priority assignment policy which maximises the computation time which can be made available by the aperiodic deadline, given a set of previously guaranteed hard periodic/sporadic tasks.

Research into on-line acceptance tests has been carried out by Chetto and Chetto [10] Schwan and Zhou [9] and Kim [4] with respect to earliest deadline scheduling. However, when applied to the case of mixed task sets, (aperiodic and periodic) the tests presented in [10] and [9] are pseudo-polynominal in complexity: in the worst case the time taken to perform the tests depends upon the number of task invocations within the least common multiple (LCM) of the hard task periods. Further, the model used by Schwan and Zhou requires that all task invocations, both periodic and aperiodic, undergo an on-line acceptance test, leading to unnecessarily high overheads. The test presented by Kim also requires that all task invocations undergo acceptance testing. However, of greater consequence, is the implicit assumption that tasks with an earlier ready time are of greater importance, and are therefore accepted in preference to, those with a later ready time. When mixed task sets are considered, this assumption no longer holds and it is difficult to see how the algorithm can be applied without jeopardising the hard deadlines of periodic tasks.

Within the context of fixed priority scheduling, an acceptance test has been developed by Ramos-Thuel and Lehoczky [7]. This test assumes that tasks are scheduled using the