# 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="/files/nLndrup3aQFfuIAoPX9n" 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://davidjosearaujo.gitbook.io/notes-miect/sistemas-operativos-e-de-tempo-real/dynamic-priority-scheduling/on-line-scheduling-with-dynamic-priorities.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.