PERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 87

τ

n

t

(a)

τ

i

t

C + 2 C

n i

τ

n

t

(b)

τ

i

t

C + 3 C

n i

Figure 4.5 a. The response time of task τ n is delayed by the interference of τ i with higher
priority. b. The interference may increase advancing the release time of τ i .

4.3.1 OPTIMALITY

In order to prove the optimality of the RM algorithm, we first show that a critical in-
stant for any task occurs whenever the task is released simultaneously with all higher-
priority tasks. Let Γ=

be the set of periodic tasks ordered by in-
creasing periods, with τ n being the task with the longest period. According to RM, τ n
will also be the task with the lowest priority.

{ τ 1 ,τ 2 ,...,τ n }

As shown in Figure 4.5a, the response time of task τ n is delayed by the interference
of τ i with higher priority. Moreover, from Figure 4.5b, it is clear that advancing the
release time of τ i may increase the completion time of τ n . As a consequence, the
response time of τ n is largest when it is released simultaneously with τ i . Repeating
the argument for all τ i ,i =2 ,...,n 1, we prove that the worst response time of a

task occurs when it is released simultaneously with all higher-priority tasks.

−

A first consequence of this result is that task schedulability can easily be checked at
their critical instants. Specifically, if all tasks are feasible at their critical instants, then
the task set is schedulable in any other condition. Based on this result, the optimality
of RM is justified by showing that if a task set is schedulable by an arbitrary priority
assignment, then it is also schedulable by RM.

Consider a set of two periodic tasks τ 1 and τ 2 , with T 1 <T 2 . If priorities are not
assigned according to RM, then task τ 2 will receive the highest priority. This situation