</>EmbeddedInterview

Why does an OS need a scheduler, and what criteria are used to judge scheduling algorithms?

EasyOperating System Concepts

Short answer: There are usually more runnable tasks than CPUs, and tasks often wait for I/O. The scheduler decides which ready task runs on each CPU and for how long, so that the CPU is kept busy while some tasks wait, interactive tasks respond quickly, and real-time tasks meet their deadlines. Algorithms are judged on CPU utilisation, throughput, turnaround time, waiting time, response time, fairness and, for real-time systems, deadline misses and predictability.

Criteria

Criterion Definition Goal
CPU utilisation fraction of time the CPU does useful work maximise
Throughput jobs completed per unit time maximise
Turnaround time completion time − arrival time minimise
Waiting time time spent in the ready queue (turnaround − burst, for CPU-only jobs) minimise
Response time arrival → first time it runs (or first output) minimise (interactive)
Fairness each task gets a fair share; no starvation ensure
Deadlines / jitter real-time tasks finish on time with low variation guarantee

These conflict: short time slices improve response time but add context-switch overhead and reduce throughput; favouring short jobs minimises average waiting time but can starve long ones.

How scheduling relates to the process life cycle: the scheduler only chooses among Ready tasks. It runs when the current task blocks (Running → Blocked), exits, or is pre-empted (timer tick, or a higher-priority task becomes Ready because an interrupt or another task woke it).

Pre-emptive vs non-pre-emptive: in a non-pre-emptive (cooperative) scheduler, a task keeps the CPU until it blocks or yields; in a pre-emptive one the OS can take the CPU away at any time. All general-purpose OSes and most RTOSes are pre-emptive.

System calls and scheduling: a system call is a natural scheduling point. Blocking calls (read on an empty socket, sleep, pthread_mutex_lock on a held lock) move the task to Blocked and invoke the scheduler; on return from any system call or interrupt, the kernel checks whether a reschedule is needed.