PERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 79

4

PERIODIC TASK SCHEDULING

4.1 INTRODUCTION

In many real-time control applications, periodic activities represent the major compu-
tational demand in the system. Periodic tasks typically arise from sensory data ac-
quisition, low-level servoing, control loops, action planning, and system monitoring.
Such activities need to be cyclically executed at specific rates, which can be derived
from the application requirements. Some specific examples of real-time applications
are illustrated in Chapter 11.

When a control application consists of several concurrent periodic tasks with indi-
vidual timing constraints, the operating system has to guarantee that each periodic
instance is regularly activated at its proper rate and is completed within its deadline
(which, in general, could be different than its period).

In this chapter, four basic algorithms for handling periodic tasks are described in detail:
Timeline Scheduling, Rate Monotonic, Earliest Deadline First, and Deadline Mono-
tonic. Schedulability analysis is performed for each algorithm in order to derive a
guarantee test for generic task sets. To facilitate the description of the scheduling
results presented in this chapter, the following notation is introduced:

Γ denotes a set of periodic tasks;

τ i denotes a generic periodic task;

τ i,j denotes the j th instance of task τ i ;

r i,j denotes the release time of the j th instance of task τ i ;