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

NP and, for every Q ∈

A problem Q is said to be NP- complete if Q NP ,Q'is

polynomially transformable to Q [GJ79]. A decision problem Q is said to be NP- hard
if all problems in NP are polynomially transformable to Q , but we cannot show that
Q

∈

∈ NP .

Let us consider two algorithms with complexity functions n and 5 n , respectively, and
let us assume that an elementary step for these algorithms lasts 1 μs . If the input
length of the instance is n =30, then it is easy to calculate that the polynomial algo-
rithm can solve the problem in 30 μs , whereas the other needs about 3 10 5 centuries.

This example illustrates that the difference between polynomial and exponential time
algorithms is large and, hence, it may have a strong influence on the performance of
dynamic real-time systems. As a consequence, one of the research objectives in real-
time scheduling is to identify simpler, but still practical, problems that can be solved
in polynomial time.

·

To reduce the complexity of constructing a feasible schedule, one may simplify the
computer architecture (for example, by restricting to the case of uniprocessor sys-
tems), or one may adopt a preemptive model, use fixed priorities, remove precedence
and/or resource constraints, assume simultaneous task activation, homogeneous task
sets (solely periodic or solely aperiodic activities), and so on. The assumptions made
on the system or on the tasks are typically used to classify the various scheduling
algorithms proposed in the literature.

2.3.1 CLASSIFICATION OF SCHEDULING

ALGORITHMS

Among the great variety of algorithms proposed for scheduling real-time tasks, the
following main classes can be identified:

Preemptive vs. Non-preemptive .

- In preemptive algorithms, the running task can be interrupted at any time
to assign the processor to another active task, according to a predefined
scheduling policy.
- In non-preemptive algorithms, a task, once started, is executed by the pro-
cessor until completion. In this case, all scheduling decisions are taken as
the task terminates its execution.