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

A best-effort scheduling algorithm tries to “do its best” to meet deadlines, but there is
no guarantee of finding a feasible schedule. In a best-effort approach, tasks may be
enqueued according to policies that take time constraints into account; however, since
feasibility is not checked, a task may be aborted during its execution. On the other
hand, best-effort algorithms perform much better than guarantee-based schemes in
the average case. In fact, whereas the pessimistic assumptions made in the guarantee
mechanism may unnecessarily cause task rejections, in best-effort algorithms a task is
aborted only under real overload conditions.

2.3.2 METRICS FOR PERFORMANCE EVALUATION

The performance of scheduling algorithms is typically evaluated through a cost func-
tion defined over the task set. For example, classical scheduling algorithms try to
minimize the average response time, the total completion time, the weighted sum of
completion times, or the maximum lateness. When deadlines are considered, they are
usually added as constraints, imposing that all tasks must meet their deadlines. If some
deadlines cannot be met with an algorithm A , the schedule is said to be infeasible by
A . Table 2.1 shows some common cost functions used for evaluating the performance
of a scheduling algorithm.

The metrics adopted in the scheduling algorithm has strong implications on the perfor-
mance of the real-time system [SSDNB95], and it must be carefully chosen according
to the specific application to be developed. For example, the average response time is
generally not of interest for real-time applications, because there is not direct assess-
ment of individual timing properties such as periods or deadlines. The same is true
for minimizing the total completion time. The weighted sum of completion times is
relevant when tasks have different importance values that they impart to the system
on completion. Minimizing the maximum lateness can be useful at design time when
resources can be added until the maximum lateness achieved on the task set is less
than or equal to zero. In that case, no task misses its deadline. In general, however,
minimizing the maximum lateness does not minimize the number of tasks that miss
their deadlines and does not necessarily prevent one or more tasks from missing their
deadline.

Let us consider, for example, the case depicted in Figure 2.16. The schedule shown in
Figure 2.16a minimizes the maximum lateness, but all tasks miss their deadline. On
the other hand, the schedule shown in Figure 2.16b has a greater maximum lateness,
but four tasks out of five complete before their deadline.