BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 41

d1 d2 d3 d4 d5

L1 = 3 L2 = 2 L3 = 1 L4 = 1 L5 = 2

J 1 J 2 J J 4 J

(a)

3 5

t

0 2 4 6 8 10 12 14 16 18 20 22 24 26

L max = L1 = 3

d1 d2 d3 d4 d5

L1 = 23 L2 = -4 L3 = -5 L4 = -5 L5 = -4

J 2 J 3 J 4 J 5 J

(b)

1

t

0 2 4 6 8 10 12 14 16 18 20 22 24 26

L = L1 = 23

max

Figure 2.16 The schedule in (a) minimizes the maximum lateness, but all tasks miss their
deadline. The schedule in (b) has a greater maximum lateness, but four tasks out of five
complete before their deadline.

When tasks have soft deadlines and the application goal is to meet as many deadlines
as possible (without a priori guarantee), then the scheduling algorithm should use a
cost function that minimizes the number of late tasks.

In other applications, the benefit of executing a task may depend not only on the task
importance but also on the time at which it is completed. This can be described by
means of specific utility functions , which describe the value associated with the task
as a function of its completion time.

Figure 2.17 illustrates some typical utility functions that can be defined on the applica-
tion tasks. For instance, non-real-time tasks (a) do not have deadlines, thus the value
achieved by the system is proportional to the task importance and does not depend
on the completion time. Soft tasks (b) have noncritical deadlines; therefore, the value
gained by the system is constant if the task finishes before its deadline but decreases
with the exceeding time. In some cases (c), it is required to execute a task on-time ;
that is, not too early and not too late with respect to a given deadline. Hence, the
value achieved by the system is high if the task is completed around the deadline, but
it rapidly decreases with the absolute value of the lateness. Such types of constraints
are typical when playing notes, since the human ear is quite sensitive to time jitter.