Hardware Reference
In-Depth Information
Proof. The theorem is proved by contradiction, assuming that τ i is blocked by two
critical sections, z 1 ,a and z 2 ,b . For this to happen, both critical sections must belong
to different tasks ( τ 1 and τ 2 ) with priority lower than P i , and both must have a ceiling
higher than or equal to P i . That is, by assumption, we must have
P 1 <P i
C ( R a );
P 2 <P i
C ( R b ) .
Now, τ i can be blocked twice only if τ 1 and τ 2 are both inside the resources when τ i
arrives, and this can occur only if one of them (say τ 1 ) preempted the other inside the
critical section. But, if τ 1 preempted τ 2
inside z 2 ,b
it means that P 2 >C ( R b ), which
is a contradiction. Hence, the theorem follows.
Since a task τ i can be blocked at most once, the maximum blocking time τ i can suffer
is given by the duration of the longest critical section among those that can block τ i .
That is,
B i =max
j,k {
δ j,k
1
|
Z j,k
γ i }
.
(7.7)
Note that one unit of time is subtracted from δ j,k to allow τ j entering Z j,k before τ i .
This method, although improving NPP, still contains a source of pessimism and could
produce some unnecessary blocking. In fact, a task is blocked at the time it attempts
to preempt, before it actually requires a resource. If a critical section is contained only
in one branch of a conditional statement, then the task could be unnecessarily blocked,
since during execution it could take the branch without the resource.
Such a source of pessimism is removed in the Priority Inheritance Protocol by post-
poning the blocking condition at the entrance of a critical section rather than at the
activation time.
7.6
PRIORITY INHERITANCE PROTOCOL
The Priority Inheritance Protocol (PIP), proposed by Sha, Rajkumar and Lehoczky
[SRL90], avoids unbounded priority inversion by modifying the priority of those tasks
that cause blocking. In particular, when a task τ i blocks one or more higher-priority
tasks, it temporarily assumes ( inherits ) the highest priority of the blocked tasks. This
prevents medium-priority tasks from preempting τ i and prolonging the blocking dura-
tion experienced by the higher-priority tasks.
Search WWH ::




Custom Search