Priorities
Last updated
Last updated
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.
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.
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.
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?
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.
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
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_N is given by:
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.
The average turnaround time is given by:
estimate e_2 is given by:
Then, priority p of a process can be given by: , where b is a coefficient that controls how much the aging weights in the priority.
