Hardware Reference
In-Depth Information
3
DPE
0
6
12
18
24
3
τ
1
0
8
16
24
3
τ
2
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Figure 6.2
DPE server schedulability.
In order to prove this result, given a schedule
σ
produced using the DPE algorithm,
consider a schedule
σ
built in the following way:
Replace the DPE server with a periodic task
τ
s
with period
T
s
and worst-case
execution time
C
s
, so that in
σ
τ
s
executes whenever the server capacity is con-
sumed in
σ
.
The execution of periodic instances during deadline exchanges is postponed until
the capacity decreases.
All other executions of periodic instances are left as in
σ
.
Note that from the definition of the DPE algorithm, at any time, at most one aperiodic
capacity decreases in
σ
,so
σ
is well defined. Also observe that, in each feasible
schedule produced by the DPE algorithm, all the aperiodic capacities are exhausted
before their respective deadlines.
Figure 6.2 shows the schedule
σ
obtained from the schedule
σ
of Figure 6.1. Note that
all the periodic executions corresponding to increasing aperiodic capacities have been
moved to the corresponding intervals in which the same capacities decrease. Also note
that the schedule
σ
does not depend on the aperiodic requests but depends only on the
characteristics of the server and on the periodic task set. Based on this observation,
the following theorem can be proved:
Theorem 6.1 (Spuri, Buttazzo)
Given a set of periodic tasks with processor utiliza-
tion
U
p
and a DPE server with processor utilization
U
s
, the whole set is schedulable
by EDF
if
and
only if
U
p
+
U
s
≤
1
.
Search WWH ::
Custom Search