Online scheduling with fixed priorities

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)

Pros

(with respect to Static Cyclic Scheduling)

• 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).

Cons

(with respect to Static Cyclic Scheduling)

• 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

Rules for priority assignment to tasks

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.

Schedulability tests

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.