Hardware Reference
In-Depth Information
skip
skip
τ
1
0
2
4
6
8
10
12
14
16
18
20
22
24
26
τ
2
0
2
4
6
8
10
12
14
16
18
20
22
24
26
Figure 9.24
The overload condition resolved by skipping one job every three in task τ 1
.
According to this model, each periodic task τ i
is characterized by the following pa-
rameters:
τ i ( C i ,T i ,D i ,S i )
where C i
is the worst-case computation time, T i
its period, D i
its relative deadline
(assumed to be equal to the period), and S i a skip parameter, 2
, expressing
the minimum distance between two consecutive skips. For example, if S i
S i ≤∞
=5the
task can skip one instance every five. When S i
no skips are allowed and τ i is
equivalent to a hard periodic task. The skip parameter can be viewed as a Quality of
Service (QoS) metric (the higher S , the better the quality of service).
=
Using the terminology introduced by Koren and Shasha [KS95], every job of a peri-
odic task can be red or blue : a red job must be completed within its deadline, whereas
a blue job can be aborted at any time. To meet the constraint imposed by the skip
parameter S i , each scheduling algorithm must have the following characteristics:
if a blue job is skipped, then the next S i
1 jobs must be red.
if a blue job completes successfully, the next job is also blue.
The authors showed that making optimal use of skips is NP-hard and presented two
algorithms (one working under Rate Monotonic and one under EDF) that exploit skips
to schedule slightly overloaded systems. In general, these algorithms are not optimal,
but they become optimal under a particular condition, called the deeply-red condition.
Definition 9.5 A system is deeply-red if all tasks are synchronously activated and the
first S i
1 instances of every task τ i are red.
Koren and Shasha showed that the worst case for a periodic skippable task set occurs
when tasks are deeply-red. For this reason, all the results shown in this section are
proved under this condition. This means that if a task set is schedulable under the
deeply-red condition, it is also schedulable in any other situation.
Search WWH ::




Custom Search