Hardware Reference
In-Depth Information
Some methods for estimating the number of preemptions have been proposed [ERC95,
YS07], but they are restricted to the fully preemptive case and do not consider such a
circular dependency.
Often, preemption is considered a prerequisite to meet timing requirement in real-time
system design; however, in most cases, a fully preemptive scheduler produces many
unnecessary preemptions. Figure 8.2(a) illustrates an example in which, under fully
preemptive scheduling, task
τ
5
is preempted four times. As a consequence, the WCET
of
τ
5
is substantially inflated by the architecture related cost (represented by dark gray
areas), causing a response time equal to
R
5
=18. However, as shown in Figure 8.2(b),
only one preemption is really necessary to guarantee the schedulability of the task set,
reducing the WCET of
τ
5
from 14 to 11 units of time, and its response time from 18
to 13 units.
To reduce the runtime overhead due to preemptions and still preserve the schedulabil-
ity of the task set, the following approaches have been proposed in the literature.
Preemption Thresholds
. According to this approach, proposed by Wang and Sak-
sena [WS99], a task is allowed to disable preemption up to a specified priority
level, which is called preemption threshold. Thus, each task is assigned a reg-
ular priority and a preemption threshold, and the preemption is allowed to take
place only when the priority of the arriving task is higher than the threshold of
the running task.
Deferred Preemptions
. According to this method, each task
τ
i
specifies the
longest interval
q
i
that can be executed non-preemptively. Depending on how
non-preemptive regions are implemented, this model can come in two slightly
different flavors:
1.
Floating model
. In this model, non-preemptive regions are defined by the
programmer by inserting specific primitives in the task code that disable
and enable preemption. Since the start time of each region is not specified
in the model, non-preemptive regions cannot be identified off-line and, for
the sake of the analysis, are considered to be “floating” in the code, with a
duration
δ
i,k
≤
q
i
.
2.
Activation-triggered model
. In this model, non-preemptive regions are trig-
gered by the arrival of a higher priority task and enforced by a timer to last
for
q
i
units of time (unless the task finishes earlier), after which preemption
is enabled. Once a timer is set at time
t
, additional activations arriving be-
fore the timeout (
t
+
q
i
) do not postpone the preemption any further. After
the timeout, a new high-priority arrival can trigger another non-preemptive
region.
Search WWH ::
Custom Search