HANDLING OVERLOAD CONDITIONS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 294

v(f )
i

v(f )
i

soft

Non real−time

f i f i

d

i

v(f ) i v(f ) i

hard

firm

f i f i

d

d i

i

−∞

Figure 9.6 Utility functions that can be associated to a task to describe its importance.

in many situations. A soft task can still give a value to the system if competed af-
ter its deadline, although this value may decrease with time. There are also real-time
activities, so-called firm , that do not jeopardize the system, but give a negligible con-
tribution if completed after their deadline. Figure 9.6 illustrates the utility functions of
four different types of tasks.

Once the importance of each task has been defined, the performance of a scheduling
algorithm can be measured by accumulating the values of the task utility functions
computed at their completion time. Specifically, we define as cumulative value of a
scheduling algorithm A the following quantity:

n

Γ A = v ( f i ) .

i =1

Given this metric, a scheduling algorithm is optimal if it maximizes the cumulative
value achievable on a task set.

Note that if a hard task misses its deadline, the cumulative value achieved by the algo-
rithm is minus infinity, even though all other tasks completed before their deadlines.
For this reason, all activities with hard timing constraints should be guaranteed a pri-
ori by assigning them dedicated resources (including processors). If all hard tasks
are guaranteed a priori, the objective of a real-time scheduling algorithm should be to
guarantee a feasible schedule in normal load conditions and maximize the cumulative
value of soft and firm tasks during transient overloads.