Hybrid Metaheuristic Approach for Scheduling of Aperiodic OS Tasks - Complex System Modelling and Control Through Intelligent Soft Computations - page 825

R w h
i

¼ d w h
i

f w h
i

ð 3 Þ

f w h
1

c w h
1

f w h
i

f w h c w h

i

¼ t þ ; ¼

i 1 þ

8 i 1 ð 4 Þ

[

Moreover, our approach combines many nice scheduling features, further
enhancing its optimality. The main contribution of this work is the development and
the performance evaluation of an ef

cient version of the EDF algorithm.

Guarantee Algorithm

Buttazzo and Stankovic ( 1993 ) present a dynamic on-line guarantee test in terms of
residual time. Based on their proposed algorithm, we will extend this algorithm by
including tolerance indicator and task rejection policy for each recon guration

scenario w h . The basic properties stated by the following lemma and theorem are

used to derive an ef

2 algorithm for analyzing the schedulability of
the sporadic task set whenever a new task arrives in the systems after each
recon

cient O ð n þ m Þ

guration scenario w h .

n ðw h Þ ¼ fr ðw h Þ
1

; r ðw h Þ
2

; ...; r ðw h Þ Lemma Given a set of active sporadic tasks

ordered by increasing deadline in a linked list, the residual time R ðw h Þ
i

g

n

of each task

r ðw h Þ
i

at time t can be computed by the following recursive formula:

R ðw h Þ
1

d ðw h Þ
1

c ðw h Þ
1

¼ t ð 5 Þ

R ðw h Þ
i

R ðw h Þ d ðw h Þ

i

d ðw h Þ c ðw h Þ

i

¼

i 1 þð i 1 Þ

: ð 6 Þ

Now we introduce a new framework for handling real-time sporadic tasks under
overload conditions, and we propose an ef cient version of the Earliest Deadline

First algorithm (EDF).
For sporadic tasks, the utilization factor could be computed by considering the
minimum interarrival time as a sort of period. However, this would lead to an
overestimation of the workload, since it would refer to the (very pessimistic) case in
which all sporadic tasks have the maximum arrival rate.
One main purpose of our EDF-based algorithm is to operate well even in
overload conditions. However, it is dif cult to develop a good measure of load in a

real-time system because each task has a unique start time and deadline. The idea is
to iteratively identify the cpu utilization required by all the tasks up to the ith task.
In many real applications, such as robotics, the deadline timing semantics is
more

flexible than scheduling theory generally permits. Basically, our approach
minimizes the pessimism found in a basic guarantee algorithm.

fl