Hardware Reference
In-Depth Information
SCHEDULABILITY ANALYSIS
The feasibility analysis of a set of firm tasks can be performed through the Processor
Demand Criterion [BRH90] illustrated in Chapter 4, under the deeply-red condition,
and assuming that in the worst case all blue jobs are aborted. In this worst-case sce-
nario, the processor demand of
τ
i
due to the red jobs in an interval [0
,L
] can be
obtained as the difference between the demand of all the jobs and the demand of the
blue jobs:
(0
,L
)=
L
T
i
L
T
i
S
i
C
i
.
g
skip
i
−
(9.22)
Hence, the feasibility of the task set can be verified through the following test:
Sufficient condition
A set of firm periodic tasks is schedulable by EDF if
L
T
i
L
T
i
S
i
C
i
≤
n
∀
L
≥
0
−
L
(9.23)
i
=1
A necessary condition can be easily derived by observing that a schedule is certainly
infeasible when the utilization factor due to the red jobs is greater than one. That is,
Necessary condition
Necessary condition for the schedulability of a set of firm periodic tasks is that
n
C
i
(
S
i
−
1)
≤
1
(9.24)
T
i
S
i
i
=1
EXAMPLE
To better clarify the concepts mentioned above, consider the task set shown in Fig-
ure 9.25 and the corresponding feasible schedule, obtained by EDF. Note that the
processor utilization factor is greater than 1 (
U
p
=1
.
25), but both conditions (9.23)
and (9.24) are satisfied.
Search WWH ::
Custom Search