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