Hardware Reference
In-Depth Information
8.3
PREEMPTION THRESHOLDS
According to this model, proposed by Wang and Saksena [WS99], each task
τ
i
is
assigned a nominal priority
P
i
(used to enqueue the task into the ready queue and to
preempt) and a
preemption threshold
θ
i
≥
P
i
(used for task execution). Then,
τ
i
can
be preempted by
τ
h
only if
P
h
>θ
i
. Figure 8.7 illustrates how the threshold is used to
raise the priority of a task
τ
i
during the execution of its
k
-th job. At the activation time
r
i,k
, the priority of
τ
i
is set to its nominal value
P
i
, so it can preempt all the tasks
τ
j
with threshold
θ
j
<P
i
. The nominal priority is maintained as long as the task is kept
in the ready queue. During this interval,
τ
i
can be delayed by all tasks
τ
h
with priority
P
h
>P
i
. When all such tasks complete (at time
s
i,k
),
τ
i
is dispatched for execution
and its priority is raised at its threshold level
θ
i
until the task terminates (at time
f
i,k
).
During this interval,
τ
i
can be preempted by all tasks
τ
h
with priority
P
h
>θ
i
. Note
that when
τ
i
is preempted its priority is kept to its threshold level.
delayed by
P
h
>P
i
preempted by
P
h
>θ
i
τ
i
θ
i
P
i
r
i,k
s
i,k
f
i,k
d
i,k
r
i,k
+1
Figure 8.7
Example of task executing under preemption threshold.
Preemption threshold can be considered as a trade-off between fully preemptive and
fully non-preemptive scheduling. Indeed, if each threshold priority is set equal to
the task nominal priority, the scheduler behaves like the fully preemptive scheduler;
whereas, if all thresholds are set to the maximum priority, the scheduler runs in non-
preemptive fashion. Wang and Saksena also showed that by appropriately setting the
thresholds, the system can achieve a higher utilization efficiency compared with fully
preemptive and fully non-preemptive scheduling. For example, assigning the preemp-
tion thresholds shown in Table 8.2, the task set of Table 8.1 results to be schedulable
by Deadline Monotonic, as illustrated in Figure 8.8.
1
1
Note that the task set is not schedulable under sporadic activations; in fact,
τ
2
misses its deadline if
τ
1
and
τ
2
are activated one unit of time after
τ
3
.
Search WWH ::
Custom Search