Hardware Reference
In-Depth Information
S
a
(
P
1
)
S
b
(
P
1
)
S
c
(
P
2
)
τ
1
1
2
0
τ
2
0
9
3
τ
3
8
7
0
τ
4
6
5
4
Table 7.2
Three semaphores shared by four tasks.
show that this assumption leads to a contradiction. In fact, if
τ
i
is blocked by
τ
j
, its
priority must be less than or equal to the maximum ceiling
C
∗
among all semaphores
locked by tasks other than
τ
i
. Thus, we have that
C
(
S
k
)
<P
i
≤
C
∗
. On the other
hand, since
C
∗
is the maximum ceiling among all semaphores currently locked by
tasks other than
τ
i
, we have that
C
∗
≥
C
(
S
k
), which leads to a contradiction and
proves the lemma.
Using the result of Lemma 7.8, we can say that a task
τ
i
can only be blocked by critical
sections belonging to lower priority tasks with a resource ceiling higher than or equal
to
P
i
. That is,
.
(7.15)
And since
τ
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,
γ
i
=
{
Z
j,k
|
(
P
j
<P
i
) and
C
(
R
k
)
≥
P
i
}
B
i
=max
j,k
{
δ
j,k
−
1
|
Z
j,k
∈
γ
i
}
.
(7.16)
Consider the same example illustrated for the Priority Inheritance Protocol, reported
in Table 7.2 for simplicity. According to Equation (7.15), we have:
γ
1
=
{
Z
2
b
,Z
3
a
,Z
3
b
,Z
4
a
,Z
4
b
}
γ
2
=
{
Z
3
a
,Z
3
b
,Z
4
a
,Z
4
b
,Z
4
c
}
γ
3
=
{
Z
4
a
,Z
4
b
,Z
4
c
}
γ
4
=
{}
Hence, based on Equation (7.16), tasks blocking factors are computed as follows:
⎧
⎨
B
1
=max(8
,
7
,
6
,
5
,
4) = 8
B
2
=max(7
,
6
,
5
,
4
,
3) = 7
B
3
=max(5
,
4
,
3) = 5
B
4
=0
.
⎩
Search WWH ::
Custom Search