Online scheduling with fixed priorities
Last updated
Sistemas Operativos E De Tempo-real
Last updated
The schedule is built while the system operates normally (online) and is based on a static criterium (priority).
The ready queue is sorted by decreasing priorities. Executes first the task with the highest priority.
If the system is preemptive, whenever a task job arrives in the ready queue, if it has higher priority than the one currently executing, it starts executing while the latter one is moved to the ready queue.
Complexity: O(n)
Scales.
Changes in the task set are immediately taken into account by the scheduler.
Sporadic tasks are easily accommodated.
Deterministic behavior on overloads.
Tasks are affected by priority level (lower priority are the first ones).
More complex implementation (w.r.t. static cyclic scheduling).
Higher execution overhead (scheduler + dispatcher).
On overloads (e.g. due to SW errors or unpredicted events) higher priority tasks may block the execution of lower priority ones
Inversely proportional to the period (RM – Rate Monotonic).
Optimal among fixed priority scheduling criteria if D=T.
Inversely proportional to the deadline (DM – Deadline Monotonic).
Optimal if D ≤ T.
Proportional to the task importance.
Typically reduces the schedulability – not optimal.
But very common is industry cases – e.g. automotive CAN.
As the schedule is built online it is fundamental to know a priori if a given task set is schedulable (i.e., its temporal requirements are met).
There are two basic types of schedulability tests:
Based on CPU utilization rate.
Based on response time.
