Hardware Reference
In-Depth Information
τ
1
τ
2
0
2
4
6
8
10
12
14
16
18
20
Figure 4.1
A task set with
U
ub
=5
/
6
.
τ
1
τ
2
0
2
4
6
8
10
12
14
16
18
20
Figure 4.2
A task set with
U
ub
=0
.
9
.
task set becomes infeasible, since the first job of
τ
2
misses its deadline. Figure 4.2
shows another example in which
U
ub
=0
.
9. Notice that setting
T
1
=4and
T
2
=8,
U
ub
becomes 1.0.
For a given algorithm
A
, the
least upper bound
U
lub
(
A
) of the processor utilization
factor is the minimum of the utilization factors over all task sets that fully utilize the
processor:
U
lub
(
A
)=min
Γ
U
ub
(Γ
,A
)
.
Figure 4.3 graphically illustrates the meaning of
U
lub
for a scheduling algorithm
A
.
The task sets Γ
i
shown in the figure differ for the number of tasks and for the con-
figuration of their periods. When scheduled by the algorithm
A
, each task set Γ
i
fully utilizes the processor when its utilization factor
U
i
(varied by changing tasks'
computation times) reaches a particular upper bound
U
ub
i
.If
U
i
≤
U
ub
i
, then Γ
i
is
schedulable, else Γ
i
is not schedulable. Notice that each task set may have a different
upper bound. Since
U
lub
(
A
) is the minimum of all upper bounds, any task set having
a processor utilization factor below
U
lub
(
A
) is certainly schedulable by A.
U
lub
defines an important characteristic of a scheduling algorithm useful for easily
verifying the schedulability of a task set. In fact, any task set whose processor utiliza-
tion factor is less than or equal to this bound is schedulable by the algorithm. On the
other hand, when
U
lub
<U
≤
1
.
0, the schedulability can be achieved only if the task
periods are suitably related.
Search WWH ::
Custom Search