BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 36

Static vs. Dynamic .
- Static algorithms are those in which scheduling decisions are based on fixed
parameters, assigned to tasks before their activation.
- Dynamic algorithms are those in which scheduling decisions are based on
dynamic parameters that may change during system evolution.
Off-line vs. Online .
- A scheduling algorithm is used off line if it is executed on the entire task
set before tasks activation. The schedule generated in this way is stored in
a table and later executed by a dispatcher.
- A scheduling algorithm is used online if scheduling decisions are taken at
runtime every time a new task enters the system or when a running task
terminates.
Optimal vs. Heuristic .
- An algorithm is said to be optimal if it minimizes some given cost function
defined over the task set. When no cost function is defined and the only
concern is to achieve a feasible schedule, then an algorithm is said to be
optimal if it is able to find a feasible schedule, if one exists.
- An algorithm is said to be heuristic if it is guided by a heuristic function
in taking its scheduling decisions. A heuristic algorithm tends toward the
optimal schedule, but does not guarantee finding it.
Moreover, an algorithm is said to be clairvoyant if it knows the future; that is, if it
knows in advance the arrival times of all the tasks. Although such an algorithm does
not exist in reality, it can be used for comparing the performance of real algorithms
against the best possible one.
GUARANTEE-BASED ALGORITHMS
In hard real-time applications that require highly predictable behavior, the feasibility
of the schedule should be guaranteed in advance; that is, before task execution. In this
way, if a critical task cannot be scheduled within its deadline, the system is still in
time to execute an alternative action, attempting to avoid catastrophic consequences.
In order to check the feasibility of the schedule before tasks' execution, the system
has to plan its actions by looking ahead in the future and by assuming a worst-case
scenario.