Hardware Reference
In-Depth Information
?
YES
NO
Γ
1
U
U
ub
1
Γ
2
U
U
ub
2
Γ
3
U
U
ub
3
Γ
4
U
U
ub
4
Γ
m
U
U
ub
m
0
U
1
lub
Figure 4.3
Meaning of the least upper bound of the processor utilization factor.
If the utilization factor of a task set is greater than 1.0, the task set cannot be scheduled
by any algorithm. To show this result, let
H
be the hyperperiod of the task set. If
U>
1, we also have
UH > H
, which can be written as
n
H
T
i
C
i
>H.
i
=1
The factor (
H/T
i
) represents the (integer) number of times
τ
i
is executed in the hyper-
period, whereas the quantity (
H/T
i
)
C
i
is the total computation time requested by
τ
i
in the hyperperiod. Hence, the sum on the left hand side represents the total computa-
tional demand requested by the task set in [0
,H
). Clearly, if the total demand exceeds
the available processor time, there is no feasible schedule for the task set.
4.2
TIMELINE SCHEDULING
Timeline Scheduling (TS), also known as a
Cyclic Executive
, is one of the most used
approaches to handle periodic tasks in defense military systems and traffic control
systems. The method consists of dividing the temporal axis into slots of equal length,
in which one or more tasks can be allocated for execution, in such a way to respect
the frequencies derived from the application requirements. A timer synchronizes the
activation of the tasks at the beginning of each time slot. In order to illustrate this
method, consider the following example, in which three tasks, A, B and C, need to
be executed with a frequency of 40, 20 and 10 Hz, respectively.
By analyzing the
Search WWH ::
Custom Search