APERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 53

3

APERIODIC TASK SCHEDULING

3.1 INTRODUCTION

This chapter presents a variety of algorithms for scheduling real-time aperiodic tasks
on a single machine environment. Each algorithm represents a solution for a particular
scheduling problem, which is expressed through a set of assumptions on the task set
and by an optimality criterion to be used on the schedule. The restrictions made on
the task set are aimed at simplifying the algorithm in terms of time complexity. When
no restrictions are applied on the application tasks, the complexity can be reduced by
employing heuristic approaches, which do not guarantee to find the optimal solution
to a problem but can still guarantee a feasible schedule in a wide range of situations.

Although the algorithms described in this chapter are presented for scheduling aperi-
odic tasks on uniprocessor systems, many of them can be extended to work on multi-
processor or distributed architectures and deal with more complex task models.

To facilitate the description of the scheduling problems presented in this chapter we
introduce a systematic notation that could serve as a basis for a classification scheme.
Such a notation, proposed by Graham et al. [GLLK79], classifies all algorithms using
three fields α | β | γ , having the following meaning:

The first field α describes the machine environment on which the task set has to
be scheduled (uniprocessor, multiprocessor, distributed architecture, and so on).

The second field β describes task and resource characteristics (preemptive, inde-
pendent versus precedence constrained, synchronous activations, and so on).