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