![]() |
Real Time Scheduling Algorithms |
Scheduling is one of the key issues in implementing RT-systems. Scheduling algorithms
may be required
a number of times during the design of RT-systems. Very rough calculations may already be required
while fixing the specification. During hardware/software partitioning, somewhat more deteiled predicitons of execution
times may be required. After compilation, even more detailed knowledge exists about the execution
times and accordingly, more precise schedules can be made. Finally, it may be necessary to decide
at run-time which task is to be executed next.
Scheduling is closely linked to the RTOS, but the reader has to keep in mind that some of the scheduling
techniques are independent of the RTOS.
Scheduling algorithms can be classified according to various citeria. The most important criterias for the classification of scheduling algorithms are listed below.
Soft and hard deadlines:
Scheduling of soft deadlines is frequently based on extensions to standard operating systems. For
example, providing task and operating systems call priorities may be sufficient for systems with
soft deadlines. More work and a detailed analysis is required for hard deadline systems.
Scheduling for periodic and aperiodic tasks:
In the following, we will distinguish between periodic, aperiodic and sporadic tasks.
Tasks which must be executed once every p units of time are called periodic tasks, and
p is called their period. Each execution of a periodic task is called a job.
The execution time c for each job corresponding to one task is assumed to be
the same.
The deadline interval d, that is, the time between a job of a task becoming available
and the time after which the same job has to finish execution. The laxity or slack l,
defined as l = d - c.
Tasks which are not periodic are called aperiodic. Aperiodic tasks have also an execution time
c, a deadline interval d and a laxity l.
Aperiodic tasks requesting the processor at unpredictable times are called sporadic, if there is a
minimum separation between the times at which they request the processor.
Preemptive and non-preemptive scheduling:
Non-preemptive schedulers are based on the assumption that tasks are executed until they are done.
As a result the response time for external events may be quite long if some tasks have a large execution time.
Preemptive schedulers have to be used if some tasks have long execution times of if the response time
for external events is required to be short.
Static and dynamic scheduling:
Dynamic schedulers take decisions at run-time. They are quite flexible, but generate overhead
at run-time.
Static schedulers take their decisions at design time. They are based on planning the start times
of tasks and generate tables of start times forwarded to a simple dispatcher. The dispatcher
does not take any decisions, but is just in charge of starting tasks at the times indicated in the table.
Mono- and multi-processor scheduling:
Simple scheduling algorithms handle the case of single processors, whereas more complex algorithms also handle systems comprising
multiple processors. For the latter, we can distinguish between algorithms for homogeneous multi-processor
systems and algorithms for heterogeneous multi-processor systems.
In the following subsections you will find a short describtion of the scheduling algorithms which are available in this training module.
Introduction > Real Time Scheduling Algorithms
Back | Next |