Hardware Reference
In-Depth Information
n
B
i
=
ma
k
{
δ
j,k
−
1
|
C
(
S
k
)
≥
P
i
}
j
=
i
+1
m
B
i
=
max
j>i
{
δ
j,k
−
1
|
C
(
S
k
)
≥
P
i
}
.
k
=1
This computation is performed by the algorithm shown in Figure 7.11. The algo-
rithm assumes that the task set consists of
n
periodic tasks that use
m
distinct binary
semaphores. Tasks are ordered by decreasing priority, such that
P
i
>P
j
for all
i<j
.
Critical sections are not nested. Note that the blocking factor
B
n
is always zero, since
there are no tasks with priority lower than
P
n
that can block
τ
n
. The complexity of
the algorithm is
O
(
mn
2
).
Note that the blocking factors derived by this algorithm are not tight. In fact,
B
i
may be computed by considering two or more critical sections guarded by the same
semaphore, which for Lemma 7.4 cannot both block
τ
i
. Similarly,
B
i
may be com-
puted by considering two or more critical sections belonging to the same task, which
for Lemma 7.3 cannot both block
τ
i
. To exclude these cases, however, the complexity
grows exponentially because the maximum blocking time has to be computed among
all possible combinations of critical sections. An algorithm based on exhaustive search
is presented by Rajkumar [Raj91]. It can find better bounds than those found by the
algorithm presented in this section, but it has an exponential complexity.
EXAMPLE
To illustrate the algorithm presented above, consider the example shown in Table 7.1,
where four tasks share three semaphores. For each task
τ
i
, the duration of the longest
critical section among those that use the same semaphore
S
k
is denoted by
δ
i,k
and re-
ported in the table.
δ
i,k
=0means that task
τ
i
does not use semaphore
S
k
. Semaphore
ceilings are indicated in parentheses.
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.1
Three semaphores shared by four tasks.
Search WWH ::
Custom Search