Hardware Reference
In-Depth Information
PREEMPTION LEVEL
Besides a priority
p
i
, a task
τ
i
is also characterized by a
preemption level
π
i
. The
preemption level is a static parameter, assigned to a task at its creation time and as-
sociated with all instances of that task. The essential property of preemption levels is
that a task
τ
a
can preempt another task
τ
b
only if
π
a
>π
b
. This is also true for pri-
orities. Hence, the reason for distinguishing preemption levels from priorities is that
preemption levels are fixed values that can be used to predict potential blocking also in
the presence of dynamic priority schemes. The general definition of preemption level
used to prove all properties of the SRP requires that
if
τ
a
arrives after
τ
b
and
τ
a
has higher priority than
τ
b
, then
τ
a
must have a
higher preemption level than
τ
b
.
Under EDF scheduling, the previous condition is satisfied if preemption levels are
ordered inversely with respect to the order of relative deadlines; that is,
π
i
>π
j
⇐⇒
D
i
<D
j
.
To better illustrate the difference between priorities and preemption levels, consider
the example shown in Figure 7.17. Here we have two tasks
τ
1
and
τ
2
, with relative
deadlines
D
1
=10and
D
2
=5, respectively. Being
D
2
<D
1
, we define
π
1
=1
and
π
2
=2. Since
π
1
<π
2
,
τ
1
can never preempt
τ
2
; however,
τ
1
may have a priority
higher than that of
τ
2
. In fact, under EDF, the priority of a task is dynamically assigned
based on its absolute deadline. For example, in the case illustrated in Figure 7.17a,
the absolute deadlines are such that
d
2
<d
1
; hence,
τ
2
will have higher priority than
τ
1
. On the other hand, as shown in Figure 7.17b, if
τ
2
arrives a time
r
1
+6, absolute
deadlines are such that
d
2
>d
1
; hence,
τ
1
will have higher priority than
τ
2
. Note
that although
τ
1
has a priority higher than
τ
2
,
τ
2
cannot be preempted. This happens
because, when
d
1
<d
2
and
D
1
>D
2
,
τ
1
always starts before
τ
2
; thus, it does not
need to preempt
τ
2
.
In the following, it is assumed that tasks are ordered by decreasing preemption levels,
so that
i<j
⇐⇒
π
i
>π
j
. This also means that
D
1
<D
2
<...< D
n
.
RESOURCE UNITS
Each resource
R
k
is allowed to have
N
k
units that can be concurrently accessed by
multiple tasks. This notion generalizes the classical single-unit resource, which can
be accessed by one task at the time under mutual exclusion. A resource with
N
k
units
can be concurrently accessed by
N
k
different tasks, if each task requires one unit.
Search WWH ::
Custom Search