Hardware Reference
In-Depth Information
task A
Major Cycle
task B
task C
Minor Cycle
t
0
25
50
75
100
125
150
Figure 4.4
Example of timeline scheduling.
task periods (
T
A
=25ms,
T
B
=50ms,
T
C
= 100 ms), it is easy to verify that the
optimal length for the time slot is 25 ms, which is the Greatest Common Divisor of the
periods. Hence, to meet the required frequencies, task A needs to be executed in every
time slot, task B every two slots, and task C every four slots. A possible scheduling
solution for this task set is illustrated in Figure 4.4.
The duration of the time slot is also called a Minor Cycle, whereas the minimum
interval of time after which the schedule repeats itself (the hyperperiod) is also called
a Major Cycle. In general, the major cycle is equal to the least common multiple of
all the periods (in the example, it is equal to 100 ms). In order to guarantee a priori
that a schedule is feasible on a particular processor, it is sufficient to know the task
worst-case execution times and verify that the sum of the executions within each time
slot is less than or equal to the minor cycle. In the example shown in Figure 4.4, if
C
A
,
C
B
and
C
C
denote the execution times of the tasks, it is sufficient to verify that
C
A
+
C
B
≤
25
ms
C
A
+
C
C
≤
25
ms
The main advantage of timeline scheduling is its simplicity. The method can be imple-
mented by programming a timer to interrupt with a period equal to the minor cycle and
by writing a main program that calls the tasks in the order given in the major cycle,
inserting a time synchronization point at the beginning of each minor cycle. Since the
task sequence is not decided by a scheduling algorithm in the kernel, but it is triggered
by the calls made by the main program, there are no context switches, so the runtime
overhead is very low. Moreover, the sequence of tasks in the schedule is always the
same, can be easily visualized, and it is not affected by jitter (i.e., task start times and
response times are not subject to large variations).
In spite of these advantages, timeline scheduling has some problems. For example, it
is very fragile during overload conditions. If a task does not terminate at the minor
cycle boundary, it can either be continued or aborted.
In both cases, however, the
Search WWH ::
Custom Search