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

2 Related Work

Scheduling algorithms have been classically categorized into online or of ine,

priority or non-priority, preemptive or non preemptive, and hard or soft deadline
scheduling algorithms. Two of the classical scheduling algorithms for uniprocessor
are

fl

fixed priority rate-monotonic scheduling (RMS), and dynamic priority EDF
algorithms.
A real-time system often has both periodic and aperiodic tasks. Lehoczky et al.
( 1987 ) developed the Deferrable Server algorithm which is compatible with the rate
monotonic scheduling algorithm and provides a greatly improved average response
time for soft deadline aperiodic tasks over polling or background service algorithms
while still guaranteeing the deadlines of periodic tasks.
In Marouf et al. ( 2012 ), the authors proposed scheduling algorithms in the case
of harmonic and non-harmonic strict periodic tasks. In Marouf and Sorel ( 2010 ,
2011 ), a schedulability analysis for such tasks were proposed where software fault-
tolerance has been considered through the primary/alternate task models. When a
primary task cannot meet its deadline, an alternate task is run. The alternate task can
be the same task (the task is re-executed).
The scheduling problem for aperiodic tasks is very different from the scheduling
problem for periodic tasks. Scheduling algorithms for aperiodic tasks must be able
to guarantee the deadlines for hard deadline aperiodic tasks and provide good
average response times for soft deadline aperiodic tasks even though the occur-
rences of the aperiodic requests are nondeterministic. The impact also of soft
deadline aperiodic requests on tasks with hard deadlines can be reduced by using an
aperiodic server task. Aperiodic requests are queued for the server when they arrive,
and executed as soon as the scheduling algorithm permits the server to execute
them.
According to Ghazalie and Baker ( 1994 ), a simple form of aperiodic server is a
background server where the server is scheduled at lower priority than every hard
deadline task. In this way, soft deadline requests never cause a hard deadline to be
missed. The main drawback of this model is that both average and worst case
response times for the server may be unacceptably long.
Another simple form of aperiodic server is a polling server. With polling, the
server is treated as a hard deadline periodic task with a fixed execution time budget,

whose deadline is equal to its period in which the server executes and serves all the
requests that have been enqueued up to that time. In the case when there are more
requests than can be served in the budgeted time, they are carried over to the
budgeted time, they are carried over to the next period. In one hand, the period must
be short enough in this case in order to achieve the desired average response time
and to guarantee any associated hard deadline. On the other hand, the queueing
(accumulation) of requests allows the period of the server to be longer than the
interarrival

time of the requests and as a consequence, the adverse effect on

schedulability of other tasks is reduced.