Hardware Reference
In-Depth Information
Algorithm: Blocking Time Computation
Input:
durations
δ
i,k
for each task
τ
i
and each semaphore
S
k
Output:
B
i
for each task
τ
i
//
Assumes tasks are ordered by decreasing priorities
(1)
begin
for
i
:= 1
to
n
−
1
do
//
for each task
(2)
B
i
:= 0;
(3)
for
j
:=
i
+1
to
n
do
//
for each lower priority task
(4)
D max
:= 0;
(5)
for
k
:= 1
to
m
do
//
for each semaphore
(6)
if
(
C
(
S
k
)
≥
P
i
) and (
δ
j,k
>D max
)
do
(7)
D max
:=
δ
j,k
;
(8)
end
(9)
end
(10)
B
i
:=
B
i
+
D max
−
1;
(11)
end
(12)
B
i
:= 0;
(13)
for
k
:= 1
to
m
do
//
for each semaphore
(14)
D max
:= 0;
(15)
for
j
:=
i
+1
to
n
do
//
for each lower priority task
(16)
if
(
C
(
S
k
)
≥
P
i
) and (
δ
j,k
>D max
)
do
(17)
D max
:=
δ
j,k
;
(18)
end
(19)
end
(20)
B
i
:=
B
i
+
D max
−
1;
(21)
end
(22)
B
i
:= min(
B
i
,B
i
);
(23)
end
(24)
B
n
:= 0;
(25)
end
(26)
Figure 7.11
Algorithm for computing the blocking factors.
According to the algorithm shown in Figure 7.11, the blocking factors of the tasks are
computed as follows (note that one time unit is subtracted from each duration):
B
1
=8+7+5=20
B
1
=7+8=15
==
>B
1
=15
B
2
=7+5=12
B
2
=7+6+3=16 ==
>B
2
=12
Search WWH ::
Custom Search