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

τ

k

τ

i

f d i

i

Figure 4.15 More accurate calculation of the interference on τ i by higher priority tasks.

Note that this test is sufficient but not necessary for guaranteeing the schedulability of
the task set. This is due to the fact that I i is calculated by assuming that each higher-

D i

priority task τ j times on τ i . However, as shown in Figure 4.15,

the actual interference can be smaller than I i , since τ i may terminate earlier.

exactly interferes

T j

To find a sufficient and necessary schedulability test for DM, the exact interleaving of
higher-priority tasks must be evaluated for each process. In general, this procedure is
quite costly since, for each task τ i , it requires the construction of the schedule until
D i . Audsley et al. [ABRW92, ABR + 93] proposed an efficient method for evalu-
ating the exact interference on periodic tasks and derived a sufficient and necessary
schedulability test for DM, called Response Time Analysis.

4.5.2 RESPONSE TIME ANALYSIS

According to the method proposed by Audsley at al., the longest response time R i of a
periodic task τ i is computed, at the critical instant, as the sum of its computation time
and the interference I i

of the higher priority tasks:

R i = C i + I i ,

where

R i
T j

C j .

i− 1

I i =

j =1

Hence,

R i
T j

C j .

i− 1

R i = C i + (4.17)

j =1

No simple solution exists for this equation since R i appears on both sides. Thus, the
worst-case response time of task τ i is given by the smallest value of R i that satisfies
Equation (4.17). Note, however, that only a subset of points in the interval [0 ,D i ] need