# Priorities

## The idea is to estimate the occupancy fraction of the next execution window, based on the occupation of the past windows, and assign the processor to the process for which this estimate is the lowestWithout priorities, favouring fearness

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2F3uZoUhJql0P4khNmkLfZ%2Funknown.png?alt=media&#x26;token=5b7b7236-88f7-4686-a9ef-409c212fbb8e" alt=""><figcaption></figcaption></figure>

All processes are equal, being **served in order of arrival** to the READY queue.

* In non-preemptive scheduling, it is normally referred to as **first-come**, **first served** (**FCFS**) – the **time-out** transition does not exist.
* In preemptive scheduling, it is normally referred to as round robin – the time-out transition exist.

Easy to implement.

Favours CPU-bound processes over I/O-bound ones.

In interactive systems, the time quantum should be carefully chosen in order to get a good compromise between fairness and response time.

## Enforcing priorities

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FE7L8GrdyITCgWYqcvWDb%2Funknown.png?alt=media&#x26;token=afb84296-e100-4090-9981-30fb2a1e6789" alt=""><figcaption></figcaption></figure>

Often, being all the same is not the most appropriate.

* in interactive systems, minimizing response time requires I/O-bound processes to be privileged.
* in real-time systems, there are processes (for example, those associated with alarm events or operational actions) that have severe time constraints.

To address this, processes can be grouped in different levels of priority.

* higher-priority processes are selected first for execution.
* lower-priority processes can suffer **starvation**.

## Types of priorities

Priorities can be:

* **static** – if they do not change over time.
* **deterministic** – if they are deterministically defined.
* **dynamic** – if they depend on the past history of execution of the processes.

### Static priorities

Processes are grouped into fixed priority classes, according to their relative importance.

Clear **risk of starvation** of lower-priority processes.

The most **unfair** discipline.

Typical in real-time systems – *Why?*

### Deterministically changing priorities

When a process is created, a given priority level is assigned to it.

On **time-out** the **priority** is **decremented**.

On **event wait** the priority is **incremented**.

When a minimum value is reached, the priority is set to the initial value.

### Dynamic priorities

Priority classes are functionally defined.

In interactive systems, change of class can be based on how the last execution window was used.

*They are clearly CPU-bound processes and the ideia is given them large execution windows, less times.*

* level 1 (highest priority): **terminals** – a process enters this class on event occurs if it was waiting for data from the standard input device.
* level 2: **generic I/O** – a process enters this class on event occurs if it was waiting for data from another type of input device.
* level 3: **small time quantum** – a process enters this class on time-out.
* level 4: (lowest priority): **large time quantum** – a process enters this class after a successive number of time-outs.

In batch systems, the **turnaround time should be minimized**.

If estimates of the execution times of a set of processes are known in advance, it is possible to establish an order for the execution of the processes that minimizes the average turnaround time of the group.

Assume *N* jobs are submitted at time 0, whose estimates of the execution times are *t\_en* , with *n* = *1, 2, · · · , N*.

* The turnaround time of job i is given by: *t\_ti = t\_e1 + t\_e2 + ... + t\_ei*
* *The average turnaround time is given by:* ![](https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2F086YIoxphz2NenDkigYN%2Funknown.png?alt=media\&token=218a7aac-9272-4978-8ef6-decd4d034f54)
* *t\_m* is **minimum** if jobs are scheduled in ascending order of the estimated execution times.

An approach similar to the previous one can be used in interactive systems.

The idea is to estimate the occupancy fraction of the next execution window, based on the occupation of the past windows, and assign the processor to the process for which this estimate is the lowest.

Let *e\_1* be the estimate of the occupancy fraction of the first execution window assigned to a process and let *f\_1* be the first fraction effectively verified. Then:

* estimate *e\_2* is given by: ![](https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2FP2AkZ07LlAnYiCIiaQxM%2Funknown.png?alt=media\&token=a1ac0035-ddaf-47c3-9683-e4894c7ea863)
* estimate *e\_N* is given by:&#x20;

<figure><img src="https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2F1YouS5dJei4HTv3aNJd8%2Funknown.png?alt=media&#x26;token=86cfc365-6166-4022-baf2-2fa0685c0e75" alt=""><figcaption></figcaption></figure>

* coefficient *a* is used to control how much the past history of execution influences the present estimate.

In the previous approach, CPU-bound processes can suffer **starvation**.

To overcome that problem, the **aging** of a process in the READY queue can be part of the equation.

Let *R* be such time, typically normalized in terms of the duration of the execution interval.

* Then, priority *p* of a process can be given by: ![](https://933056030-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FmDWmJ4LyRblScRPGY3di%2Fuploads%2Fs579r9mntvCYXZiRizty%2Funknown.png?alt=media\&token=d1db3926-95dd-469c-bc4d-6424b8c2dd43), where *b* is a coefficient that controls how much the aging weights in the priority.
