On-line scheduling with dynamic priorities

Dynamic priorities

Ready Queue sorted by instantaneous priorities and dynamically re-sorted (if/when necessary)

Scheduling is based in dynamic criteria, i.e. one that is known only at run-time.

The dynamic parameter used to sort the ready tasks can be understood as a dynamic priority.

The ready queue is (re)sorted according with decreasing priorities whenever there is a priority change. Executes first the task that has the greater instantaneous priority.

• Complexity O(n.log(n))

Pros

• Scales well (wrt SCS).

  • Changes made to the task set are immediately seen by the scheduler.

• Accommodates easily sporadic tasks (wrt SCS).

• Allows higher utilization levels than Fixed Priorities.

Cons

• More complex implementation (wrt SCS and FP).

• Higher overhead (wrt SCS and FP).

  • Re-sorting of the ready queue; depends on the algorithm.

• “Unpredictability” on overloads (wrt FP).

  • It is not possible to know a priori which tasks will fail deadlines.

Priority allocation approaches

Inversely proportional to the time to the deadline.

• EDF – Earliest Deadline First.

  • Optimal among all dynamic priority criteria.

• Inversely proportional to the laxity or slack.

  • LSF (LST or LLF) – Least Slack First.

    • Optimal among all dynamic priority criteria.

• Inversely proportional to the service waiting time.

  • FCFS –First Come First Served.

    • Not optimal with respect to meet deadlines; extremely poor real-time performance.