SOLUTIONS TO THE EXERCISES - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 459

means that the CPU is idle. A schedule is said to be preemptive if the running
task can be arbitrarily suspended at any time to assign the CPU to another task
according to a predefined scheduling policy. In a preemptive schedule, tasks
may be executed in disjointed interval of times. In a non-preemptive schedule,
a running task cannot be interrupted and therefore it proceeds until completion.

2.2 A periodic task consists of an infinite sequence of identical jobs that are regu-

larly activated at a constant rate. If φ i is the activation time of the first job of
task τ i , the activation time of the k th job is given by φ i +( k

1) T i , where T i is
the task period. Aperiodic tasks also consist of an infinite sequence of identical
jobs; however, their activations are not regular. An aperiodic task where con-
secutive jobs are separated by a minimum interarrival time is called a sporadic
task. The most important timing parameters defined for a real-time task are

−

the arrival time (or release time ); that is, the time at which a task becomes
ready for execution;
the computation time ; that is, the time needed by the processor for exe-
cuting the task without interruption;
the absolute deadline ; that is, the time before which a task should be
completed to avoid damage to the system;
the finishing time ; that is, the time at which a task finishes its execution;
the response time ; that is, the difference between the finishing time and
the release time: R i = f i − r i ;

2.3 A real-time application consisting of tasks with precedence relations is shown

in Section 2.2.2.

2.4 A static scheduler is one in which scheduling decisions are based on fixed pa-

rameters, assigned to tasks before their activation. In a dynamic scheduler,
scheduling decisions are based on dynamic parameters that may change dur-
ing system evolution. A scheduler is said to be off-line if it is pre-computed
(before task activation) and stored in a table. In an online scheduler, schedul-
ing decisions are taken at runtime when a new task enters the system or when
a running task terminates. An algorithm is said to be optimal if it minimizes
some given cost function defined over the task set. A common optimality cri-
terion for real-time system is related to feasibility. Then, a scheduler is optimal
whenever it can find a feasible schedule, if one exists. Heuristic schedulers use
a heuristic function to search for a feasible schedule; hence it is not guaranteed
that a feasible solution is found.

2.5 An example of domino effect is shown in Figure 2.15.