Hardware Reference
In-Depth Information
τ
1
τ
2
0
2
4
6
8
10
12
14
16
18
20
earliest
slack
A(6, t)
7
+2
5
3
1
+2
+2
0
2
4
6
8
10
12
14
16
18
20
Figure 5.22
Slack function at time
s
=6
for the periodic task set considered in the
previous example.
According to the original algorithm proposed by Lehoczky and Ramos-Thuel [LRT92],
the slack function at time s =0is precomputed and stored in a table. During runtime,
the actual function A ( s, t ) is then computed by updating A (0 ,t ) based on the peri-
odic execution time, the aperiodic service time, and the idle time. The complexity for
computing the current slack from the table is O ( n ), where n is the number of periodic
tasks; however, depending on the periods of the tasks, the size of the table can be too
large for practical implementations.
A dynamic method for computing slack has been proposed by Davis, Tindell, and
Burns [DTB93]. According to this algorithm, the available slack is computed when-
ever an aperiodic requests enters the system. This method is more complex than the
previous static approach, but it requires much less memory and allows handling of
periodic tasks with release jitter or synchronization requirements. Finally, a more ef-
ficient algorithm for computing the slack function has been proposed by Tia, Liu, and
Shankar [TLS95].
The Slack Stealing algorithm has also been extended by Ramos-Thuel and Lehoczky
[RTL93] to guarantee firm aperiodic tasks.
 
Search WWH ::




Custom Search