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