Scheduling Algorithms

A scheduling algorithm is a method for solving the scheduling problem.

• Note: don’t confuse scheduling algorithm (the process/method) with schedule (the result).

Classification of scheduling algorithms:

• Preemptive vs non-preemptive.

• Static vs dynamic (priorities).

• Off-line vs on-line.

• Optimal vs sub-optimal.

• With strict guarantees vs best effort.

A short note on temporal complexity

Measurement of the growth of the execution time of an algorithm as a function of the problem size ( e.g. the number of elements of a vector, the number of tasks of a real-time system).

Expressed via the O() operator (big O notation).

O() arithmetic, n=problem dimension, k=constant.

•