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

= i =1 C i =5, R (0)

4

t I (0)
4

=5and I (0)
4

+ C 4 >R (0) Step 0:

4

hence τ 4 does not finish at R (0)
4

.

R (1)
4

= I (0)
4

+ C 4 =6,but I (1)
4

=6and I (1)
4

+ C 4 >R (1)
4

Step 1:

hence τ 4 does not finish at R (1)
4

.

R (2)
4

= I (1)
4

+ C 4 =7,but I (2)
4

=8and I (2)
4

+ C 4 >R (2)
4

Step 2:

hence τ 4 does not finish at R (2)
4

.

R (3)
4

= I (2)
4

+ C 4 =9,but I (3) =9and I (3)

4

+ C 4 >R (3) Step 3:

4 4

hence τ 4 does not finish at R (3)
4

.

R (4)
4

= I (3)
4

+ C 4 =10,but I (4) =9and I (4)

4

+ C 4 = R (4) Step 4:

4 4

hence τ 4 finishes at R 4 = R (4) =10.

4

Since R 4 ≤ D i for all tasks, we

conclude that the task set is schedulable by DM. Such a schedulability test can be
performed by the algorithm illustrated in Figure 4.17.

D 4 , τ 4 is schedulable within its deadline. If R i ≤

DM guarantee (Γ) {

for (each τ i ∈ Γ) {

I i = i− 1

k =1 C k ;

do { R i = I i + C i ;

if ( R i >D i ) return(UNSCHEDULABLE);
I i = i− 1
k =1

R i
T k

C k ;

while ( I i + C i >R i );
return(SCHEDULABLE);

}

}

Figure 4.17 Algorithm for testing the schedulability of a periodic task set Γ under Dead-

line Monotonic.