PREEMPTIVE PRIORITY BASED SCHEDULING:

AN APPROPRIATE ENGINEERING APPROACH?

Alan Burns

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

ABSTRACT

Scheduling theories for fixed priority scheduling are now sufficiently mature that a genuine engineering approach to the construction of hard real-time systems is possible. In this paper we review recent advances. A flexible computational model is adopted that can accommodate periodic and sporadic activities, different levels of criticality, process interaction and blocking, cooperative scheduling (deferred preemption), release jitter, precedence constrained processes, arbitrary deadlines, deadlines associated with specific events (rather than the end of a task's execution) and offsets. Scheduling tests for these different application characteristics are described. This model can be supported by structured, object oriented or formal development methods. The paper also considers the issues involved in producing safe and predictable kernels to support this computational model.

1. INTRODUCTION

Recent developments in the analysis of fixed priority preemptive scheduling have made significant enhancements to the models introduced by Lui and Layland in their seminal 1973 paper33. These developments, taken together, now represent a body of analysis that forms the basis for an engineering approach to the design, verification and implementation of hard real-time systems. In this paper we review much of this analysis in order to support the thesis that safety critical realtime systems can, and should, be built using these techniques.

Preemptive priority based scheduling prescribes a run-time environment in which tasks, with a priority attribute, are dispatched in priority order. Priorities are, essentially, static. Processes are either runnable, in which case they are held on a notional (priority ordered) run queue; delayed, in which case they are held on a notional delay queue; or suspended, in which case they are awaiting an event which may be triggered externally (via an interrupt) or internally (from some other task).

Most existing hard real-time systems are implemented using a static table driven schedule (often called a cyclic executive). Priority based scheduling has many advantages over this static approach (see Locke35 for a detailed discussion of this issue). In essence these advantages all relate to one theme ? increased flexibility. However, in order to challenge the role of static scheduling as the premier implementation model, priority based scheduling must:

g provide the same level of predictability (of temporal behaviour)

g allow a wide range of application characteristics to be accommodated

g enable dependable (safe) implementations to be supported.

All of these issues are addressed in this review, which is organised as follows. The remainder of this introduction outlines a simple model of task attributes and shows how worst case response hhhhhhhhhhhhhhh
?A version of this paper will appear in Principles of Real-Time Systems edited by Sang H. Son; to be published by Prentice Hall.