Hardware Reference
In-Depth Information
normal execution
critical section
τ
1
a
τ
2
a
ba
τ
3
b
b
b
p
3
P
1
P
2
P
3
t
1
t
2
t
3
t
4
t
5
t
6
Figure 7.10
Example of transitive priority inheritance.
Lemma 7.1
A semaphore
S
k
can cause push-through blocking to task
τ
i
, only if
S
k
is
accessed both by a task with priority lower than
P
i
and by a task with priority higher
than
P
i
.
Proof.
Suppose that semaphore
S
k
is accessed by a task
τ
l
with priority lower than
P
i
, but not by a task with priority higher than
P
i
. Then,
τ
l
cannot inherit a priority
higher than
P
i
. Hence,
τ
l
will be preempted by
τ
i
and the lemma follows.
Lemma 7.2
Transitive priority inheritance can occur only in the presence of nested
critical sections.
Proof.
A transitive inheritance occurs when a high-priority task
τ
H
is blocked by
a medium-priority task
τ
M
, which in turn is blocked by a low-priority task
τ
L
(see
Figure 7.10). Since
τ
H
is blocked by
τ
M
,
τ
M
must hold a semaphore, say
S
a
. But
τ
M
is also blocked by
τ
L
on a different semaphore, say
S
b
. This means that
τ
M
attempted
to lock
S
b
inside the critical section guarded by
S
a
. The lemma follows.
Search WWH ::
Custom Search