Fixed Priority Scheduling with Deadlines Prior to Completion

A. Burns

Real-Time Systems Research Group
Department of Computer Science
University of York, UK

ABSTRACT

Standard analysis for fixed priority scheduling assumes that all the computations for each task must be completed by the task's deadline. In practice this is rarely the case. The deadline is more correctly associated with the last observable event of the task, interval events and kernel overheads (such as the context switch away from the task) can occur after the deadline. New analysis is presented that caters for this situation. The result is enhanced schedulability without modification to the preemptive behaviour of the run-time system.

1. Introduction

The fundamental rate monotonic model is based upon a number of stringent assumptions. Since the initial analysis of Liu and Layland10 in 1973 many of these assumptions have been removed (or at least weakened). For example:

g tasks must be independent ? the priority inheritance protocols12 allow tasks to share data that is protected by mutual exclusion;

g deadline must equal period ? deadline monotonic theory9, 4, 1 can by applied if deadline (D ) is less than period (T ), and arbitrary deadline analysis14, 8 can by used for the case of D>T ;

g tasks are periodic ? hard sporadic tasks can by supported directly once the D =T requirement is relaxed3, and aperiodic tasks can be accommodated by various bandwidth preserving algorithms13, 6.

One further restriction is relaxed in this paper; namely that the deadline of each task occurs at the very end of its computation - i.e. a task's worst case computation time, denoted by C , must always be completed by the deadline D .

In a recent report, Gerber and Hong7 argue that it is only meaningful to attach a deadline to the last observable event of a task. Moreover this last observable event may not be at the end of the task's execution, i.e. there may be a number of internal actions after the last output event. Even if the task, as written, has the last observable event at the end of its execution sequence it may be possible to transform the code so that statements not dependent on this last event are moved beyond it.

When the model for analysis is enhanced to include kernel overheads5, it is necessary to "charge" to each task the cost of the context switch that allows it to preempt a lower priority task plus the cost of the context switch back to the preempted task once the higher priority task has completed. For realistic context switch times (i.e. not zero), it is meaningless to attach the "deadline" to the end of the context switch. Figure 1 gives a block representation of a task's execution (excluding preemptions for higher priority tasks). Phase a is the initial context switch to the task, phase b is the task's actual execution time up to the last observable event, phase c represents the internal actions of the task following the last observable event, and finally phase d is the cost of the context switch away from the task. The real deadline of the task is at the end of phase b.

In the following discussions we shall denote by CD the computation time required by the