Hardware Reference
In-Depth Information
deadline miss
T
1
C
1
C
1
τ
1
T
2
C
2
τ
2
0
2
4
6
8
10
12
14
16
18
20
(a) Non-preemptive case.
T
1
C
1
τ
1
T
2
C
2
τ
2
0
2
4
6
8
10
12
14
16
18
20
(b) Preemptive case.
Figure 8.5
A task set with low utilization that is unfeasible under non-preemptive Rate
Monotonic scheduling, and feasible when preemption is enabled.
8.2.1 FEASIBILITY ANALYSIS
The feasibility analysis of non-preemptive task sets is more complex than under fully
preemptive scheduling. Bril et al. [BLV09] showed that in non-preemptive scheduling
the largest response time of a task does not necessarily occur in the first job, after
the critical instant. An example of such a situation is illustrated in Figure 8.6, where
the worst-case response time of
τ
3
occurs in its second instance. Such a scheduling
anomaly, identified as
self-pushing phenomenon
, occurs because the high priority jobs
activated during the non-preemptive execution of
τ
i
's first instance are pushed ahead
to successive jobs, which then may experience a higher interference.
The presence of the self-pushing phenomenon in non-preemptive scheduling implies
that the response time analysis for a task
τ
i
cannot be limited to its first job, activated
at the critical instant, as done in preemptive scheduling, but it must be performed for
multiple jobs, until the processor finishes executing tasks with priority higher than or
equal to
P
i
. Hence, the response time of a task
τ
i
needs to be computed within the
longest Level-
i
Active Period, defined as follows [BLV09]:
Search WWH ::
Custom Search