Hardware Reference
In-Depth Information
RM
τ
1
0
5
10
15
20
25
30
35
time overflow
τ
2
0
7
14
21
28
35
(a)
EDF
τ
1
0
5
10
15
20
25
30
35
τ
2
0
7
14
21
28
35
(b)
Figure 4.13
Schedule produced by RM (a) and EDF (b) on the same set of periodic tasks.
4.4.2
AN EXAMPLE
Consider the periodic task set illustrated in Figure 4.13, for which the processor uti-
lization factor is
2
5
+
4
34
35
U
=
=
0
.
97
.
7
This means that 97 percent of the processor time is used to execute the periodic tasks,
whereas the CPU is idle in the remaining 3 percent. Being
U>
2(
√
2
0
.
83, the
schedulability of the task set cannot be guaranteed under RM, whereas it is guaranteed
under EDF. Indeed, as shown in Figure 4.13a, RM generates a deadline miss at time
t
=7, whereas EDF completes all tasks within their deadlines (see Figure 4.13b).
Another important difference between RM and EDF concerns the number of preemp-
tions occurring in the schedule. As shown in Figure 4.13, under RM every instance of
task
τ
2
is preempted, for a total number of five preemptions in the interval
T
=
T
1
T
2
.
Under EDF, the same task is preempted only once in the same interval. The smaller
number of preemptions in EDF is a direct consequence of the dynamic priority assign-
ment, which at any instant privileges the task with the earliest deadline, independently
of tasks' periods.
−
1)
Search WWH ::
Custom Search