# On-line scheduling with dynamic priorities

{% hint style="info" %}

### Dynamic priorities

**Ready Queue** sorted by instantaneous priorities and dynamically re-sorted (if/when necessary)
{% endhint %}

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

<figure><img src="https://3011170443-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxBNeQZTqLnbb3C3JTlRu%2Fuploads%2FzqjIMVtLLz6EhdFXeVPt%2Fa.png?alt=media&#x26;token=a21cc859-25f0-404f-987b-86853cfb48f8" alt=""><figcaption></figcaption></figure>

## 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.
