Hardware Reference
In-Depth Information
let
J
new
be a newly arrived task. In order to accept
J
new
in the system we have to
J
=
guarantee that the new task set
J∪{
J
new
}
is also schedulable.
J
is feasibly
schedulable by EDF, we need to show that, in the worst case, all tasks in
Following the same approach used in EDD, to guarantee that the set
J
will
complete before their deadlines. This means that we have to show that, for each task,
the worst-case finishing time
f
i
is less than or equal to its deadline
d
i
.
J
(including
J
new
) are
ordered by increasing deadlines, so that
J
1
is the task with the earliest deadline. More-
over, since tasks are preemptable, when
J
new
arrives at time
t
some tasks could have
been partially executed. Thus, let
c
i
(
t
) be the remaining worst-case execution time of
task
J
i
(notice that
c
i
(
t
) has an initial value equal to
C
i
Without loss of generality, we can assume that all tasks in
and can be updated whenever
J
i
is preempted). Hence, at time
t
, the worst-case finishing time of task
J
i
can be
easily computed as
i
f
i
=
c
k
(
t
)
.
k
=1
Thus, the schedulability can be guaranteed by the following conditions:
i
∀
i
=1
,...,n
c
k
(
t
)
≤
d
i
.
(3.2)
k
=1
Noting that
f
i
=
f
i−
1
+
c
i
(
t
) (where
f
0
=0by definition), the dynamic guarantee
test can be performed in
O
(
n
) by executing the algorithm shown in Figure 3.7.
3.4
NON-PREEMPTIVE SCHEDULING
When preemption is not allowed and tasks can have arbitrary arrivals, the problem
of minimizing the maximum lateness and the problem of finding a feasible schedule
become NP-hard [GLLK79, LRKB77, KIM78]. Figure 3.8 illustrates an example
that shows that EDF is no longer optimal if tasks cannot be preempted during their
execution. In fact, although a feasible schedule exists for that task set (see Figure 3.8a),
EDF does not produce a feasible schedule (see Figure 3.8b), since
J
2
executes one
unit of time after its deadline. This happens because EDF immediately assigns the
processor to task
J
1
; thus, when
J
2
arrives at time
t
=1,
J
1
cannot be preempted.
J
2
can start only at time
t
=4, after
J
1
completion, but it is too late to meet its deadline.
Notice, however, that in the optimal schedule shown in Figure 3.8a the processor re-
mains idle in the interval [0
,
1) although
J
1
is ready to execute. If arrival times are not
Search WWH ::
Custom Search