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

In Ghazalie and Baker ( 1994 ), the authors consider that the advantage of the
polling over background processing is that hard deadlines can be guaranteed, since
the server period is treated as a hard deadline. Also, by using multiple servers at
different priority levels, one can accommodate a set of tasks with a range of hard
and soft deadline requirements. In contrast, the main disadvantage of polling server
is that, under reasonable assumptions about the distribution of aperiodic requests,
the average response time is at least half the server period plus the average exe-
cution time. Thus, the only way to improve response time for soft-deadline tasks is
to reduce the server period before using the scheduling algorithm.
According to Layland and Liu ( 1973 ), a scheduling algorithm is a set of rules
that determine the task to be executed at a particular moment. The scheduling
algorithms to be studied in this topic chapter are preemptive and priority driven
ones. Indeed, whenever there is a request for a task that is of higher priority than the
one currently being executed, the running tasks is immediately interrupted and the
newly requested task is started. Thus, a scheduling algorithm is said to be static if
priorities are assigned to tasks once and for all. It is also called a fixed priority

scheduling algorithm. In contrast, a scheduling algorithm is said to be a dynamic if
priorities of tasks might change from request to request.
A scheduling algorithm is said to be a mixed or hybrid scheduling algorithm if
the priorities of some tasks are

fixed yet the priorities of the remaining tasks vary

from request to request.
In this topic chapter, we adapt this approach of hybrid scheduling as described in
the following Sect. 4 .
For a detailed analysis of aperiodic servers see Guillem ( 2001 ) and Burns and
Guillem ( 1999 ). The aperiodic scheduling algorithm must also accomplish these
goals without compromising the hard deadlines of the periodic tasks. For the
aperiodic scheduling, authors presented Slack stealing Thuel and Lehoczky ( 1994 )
and aperiodic servers, such as the sporadic server Sprunt et al. ( 1989 ) and the
deferrable server Strosnider et al. ( 1995 ), allow aperiodic tasks to be handled within
a periodic task framework. Lipari and Buttazzo ( 1999 ) proposed a hybrid method
that combined periodic and aperiodic tasks which shared many resources. Our
approach try by allowing periodic tasks to be handled with an aperiodic ones by an
hybrid approach in the same framework. To the author is knowledge, no result is

available in the state of the art for scheduling both periodic and aperiodic tasks,
except that we propose in our original work where an approach to deal with
complex timing constraints and with minimizing the response time is proposed.

'

3 System Model

A task model is required as the basis for discussing scheduling. A real-time task is a
basic executable entity, which can be scheduled; it can be either periodic or ape-
riodic, with soft or hard timing constraint. A task is best de

ned with its main
timing parameters. For our work, we shall assume that time parameters have the