chapter 4 Flashcards
there are 3 types of scheduling levels
1- short-term
2- medium-term
3- long-term
short-term scheduling
scheduler decides on which process should be executed next, this level is very short time wise (micro to milliseconds). This is also known as CPU scheduling, selects process from ready queue to be executed next.
It has 3 states: READY, BLOCKED and RUNNING
medium-term scheduling
this involves swapping in and out processes from mem, this level is medium time wise (milliseconds to mins). A process is swapped out if its entire @ space is moved to secondary mem to free up physical mem for other processes.
There are 2 states: READY SUSPEND (ausgelagert bereit) and BLOCKED suspend (ausgelagert blockiert)
long-term scheduling
decisions such as which process should be admitted to the system for processing, this takes from minutes up to hours. The purpose here is control the degree of multiprogramming.
There are 2 types: NEW (erzeugt) and EXIT (beendet).
NEW (erzeugt) means that the process is ready for program processing, this state is reached when a process is created via fork(2)
EXIT (beendet) is when a state is terminated, reached by wait(2) or exit(2), the system must release all resources
CPU scheduling strategy - First come first served (FCFS)
processes are executed in the order they arrive in the ready queue.
FCFS is non-preemptive!!!
Advantage: minimizes the # of context switches since it is non-preemptive, which reduces overhead.
Disadvantage: convoy effect
FCFS is typically used for batch processing systems.
The Convoy Effect
is when short running I/O heavy processes are forced to wait behind CPU-heavy processes. This could happend in FCFS which is not wanted.
CPU scheduling strategy - Round Robin (RR)
helps mitigate the convoy effect. It divides CPU time into slices (Zeitscheiben). When the time slice is used, the process is interrupted and the process is moved to the end of the ready list and the next process is selected according to FCFS.
If the time slice is too long, RR becomes like FCFS. If it is too short, high overhead due to context switches
Time slice should be slightly longer than the typical duration of a process`s interaction with the CPU.
what are I/O operations?
interaction of a computer with the systems disk or network, such as reading/writing to disk
CPU scheduling strategy - Virtual Round Robin (VRR)
since there is an uneven CPU time distribution in RR because of CPU-heavy and I/O-heavy processes, VRR uses 2 lists:
- preferred list: processes that have just completed an I/O burst are placed here
- ready list: the normal ready list
the scheduler always starts with the preferred list first!!! VRR works with variable length time slices, processes in the preferred list are not allocated a full time slice, instead they get the remaining time from their previous incomplete time slice. If it needs more time, it is preempted and moved to the ready list.
VRR has more overhead.
CPU scheduling strategy - Shortest Process Next (SPN)
prioritises shortest processes first, the scheduler must know or estimate the CPU burst time of the processes.
SPN is non-preemptive!!
The main problem is estimating the CPU burst time.
One major downside is the risk of starvation of CPU-heavy processes as shorter processes are continiously prioritised. (there is a formula, go back to it)
CPU scheduling strategy - Highest Response Ratio Next (HRRN)
aims to prevent the starvation of CPU-heavy processes by considering both waiting time and the expected service time of processes. (formula)
The process with highest response ratio is chosen next to be executed, this ensures that a process that has been waiting for too long is chosen and given priority
CPU scheduling strategy - Multilevel Feedback Queues (MLFQ)
prioritises short processes without estimating CPU burst time. Processes with long execution time are punished by being moved to lower-priority queues.
Preemption is possible!!
The system has many different priority queues. When a process first arrives, it starts at the highest-priority queue, if it doesnt finish within time slice, it is moved to a lower-priority queue. The lowest-priority queue operates using RR.
The system can implement an anti-aging mechanism where processes that have waited too long can regain higher-priority queues to prevent starvation.
Priority Inversion
occurs when a lower-priority process is running and holding a resource while a higher-priority process is blocked waiting for said resource.
Solution: non-blocking synchro
Goals of scheduling from user perspective
- processing time
- response time
- deadline adherence
- predictability: processes are all handled similarly regardless of the load
Goals of scheduling from system perspective
- throughput: process as many processes as possible
- CPU utilisation
- fairness: avoid starvation
- load balancing: I/O devices should be evenly utilised
