Hardware Reference
In-Depth Information
τ
1
τ
2
2
J
k
0
2
4
6
8
10
12
14
16
18
20
Schedule produced by EDF with
d
k
=5
Figure 6.11
.
Theorem 6.7 (Buttazzo, Sensini)
Let
σ
be a feasible schedule produced by EDF for
a task set
and let
f
k
be the finishing time of an aperiodic request
J
k
, scheduled in
σ
with deadline
d
k
.If
f
k
=
d
k
, then
f
k
=
f
k
, where
f
k
T
is the minimum finishing time
achievable by any other feasible schedule.
Proof.
Assume
f
k
=
d
k
, and let
r
0
be the earliest request such that interval [
r
0
,
d
k
]is
fully utilized by
J
k
and by tasks with deadline less than
d
k
. Hence, in
σ
,
d
k
represents
the time at which
J
k
and all instances with deadline less than
d
k
end to execute.
We show that any schedule
σ
finishes at
f
k
in which
J
k
<d
k
is not feasible.
In
fact, since [
r
0
,
d
k
] is fully utilized and
f
k
<d
k
,in
σ
d
k
must be the finishing time
with deadline less than
d
k
. As a consequence,
σ
of some periodic instance
3
is not
feasible. Thus, the theorem follows.
6.8
PERFORMANCE EVALUATION
The algorithms described in this chapter have been simulated on a synthetic workload
in order to compare the average response times achieved on soft aperiodic activities.
For completeness, a dynamic version of the Polling Server has also been compared
with the other algorithms.
The plots shown in Figure 6.12 have been obtained with a set of ten periodic tasks with
periods ranging from 100 and 1000 units of time and utilization factor
U
p
=0
.
65.
3
Time
d
k
cannot be the finishing time of an aperiodic task, since we assume that aperiodic requests are
served on a FCFS basis.
Search WWH ::
Custom Search