A1.3.3 Compare different approaches to scheduling.

The big idea

CPU-scheduling algorithms decide which ready process/thread runs when and for how long.
Their goal is to optimise measurable performance criteria— low average waiting/turn-around time, high throughput, good interactive response—while remaining feasible to implement. Different algorithms make different trade-offs between fairness, overhead, starvation-risk and predictability .

 

Concise outlines of the four approaches

To pre-empt is to let the operating system forcibly take the CPU away from a currently running process or thread before it voluntarily gives it up, so that another runnable entity can run instead. Pre-empting is the act of doing this.

In an operating system scheduler, pre-emption is the mechanism by which the kernel interrupts a running task, saves its execution state (context), and switches the CPU to a different ready task according to the scheduling policy. This interruption is initiated by the system (typically via a timer interrupt or the arrival of a higher-priority task), not by the running task itself.

Term	Core idea	Pre-emptive?	Strengths	Typical pitfalls / use cases
First-Come First-Served (FCFS)	Run jobs strictly in the order they arrive (single FIFO ready queue).	No – once a job starts it runs until it blocks or finishes. (When a job blocks, it stops running because it cannot make forward progress without some external event. At that point, the operating system removes it from the ready-to-run set and gives the CPU to another job.)	Negligible context-switch overhead; easy to implement; highest raw throughput in homogeneous batch workloads.	“Convoy effect” harms short interactive jobs; long jobs can dominate turnaround time. Suitable for simple batch or embedded systems where every job is similar in length.
Round Robin (RR)	Cycle through the ready queue, giving each task a fixed time quantum before forcibly pre-empting.	Yes – timer interrupt triggers a switch at quantum expiry.	Good perceived fairness; quick interactive response if quantum ≈ 1–2 × average I/O think time.	Too small a quantum ⇒ high overhead; too large ⇒ degenerates into FCFS. Default choice for time-sharing OSs and GUIs.
Priority Scheduling	Always choose the highest-priority ready task; lower-priority tasks wait. Priorities may be static or dynamically adjusted.	Both variants exist; pre-emptive version is common.	Lets critical (real-time, kernel, latency-sensitive) work jump the queue; can deliver deterministic latencies.	Starvation of low-priority tasks unless aging or priority inheritance used; risk of priority inversion. Common in real-time kernels and QoS-aware servers.
Multilevel Queue (MLQ)	Partition ready tasks into several separate queues (e.g., system, interactive, batch). The scheduler chooses between queues by fixed rule (strict priority or time slicing); each queue runs its own algorithm (often RR or FCFS).	Usually non-pre-emptive between queues; may be pre-emptive within each queue.	Clear segregation of workload classes; simple to give system or interactive tasks guaranteed precedence.	Rigid—jobs rarely move between queues, so background work may starve; lower total utilisation if upper queues stay full. Used in OSs that must protect interactive responsiveness (desktop, mobile) or hard real-time tasks.

---

Side-by-side comparison of four classic approaches

Feature / metric	First-come first-served (FCFS)	Round Robin (RR)	Priority scheduling	Multilevel-queue (MLQ)
Pre-emptive?	No (non-pre-emptive)	Yes (time-quantum)	Either variant exists	Usually non-pre-emptive between queues; each queue may be pre-emptive
Ready-queue structure	Simple FIFO list	FIFO + periodic rotation	Priority heap/arrays	Several separate queues ordered by priority class
Typical quantum / time slice	N/A	10–100 ms (tuneable)	If pre-emptive, runs until a higher-priority task arrives or it blocks	High-priority queues often short quanta; lower queues may be FCFS
Average response time	Poor for short jobs (convoy effect)	Good for interactive jobs; depends on quantum	Excellent for high-priority jobs; poor or indefinite for low-priority	Excellent for top class; can be very poor for background class
Throughput & context-switch cost	High throughput; minimal overhead	Lower throughput as quantum ↓ (more switches)	Similar to FCFS if non-pre-emptive; overhead only on priority change	Extra bookkeeping per queue + inner scheduling
Fairness	Favourable to arrival order, but ignores job length	High perceived fairness (equal quanta)	Unfair across priority levels; mitigated by aging	Strict segregation—fair within a queue, not across
Starvation risk	None	None	High for low-priority tasks unless aging implemented	High for lowest queue(s) if upper classes remain busy
Best suited to	Simple batch systems, single-user workloads	Time-sharing, interactive shells, GUIs	Real-time or QoS-critical workloads	Mixed workloads needing hard separation (e.g. interactive, batch, system)
Weakness in practice	Long jobs block the short ones	“Quantum‐too-small” ⇒ thrashing; “quantum-too-large” ⇒ FCFS behaviour	Needs careful priority assignment & aging; can lead to priority inversion	Rigidity—tasks rarely migrate between queues, leading to utilisation loss

---

Definitions

Term	Definition	Practical notes / examples
Fairness	The extent to which each runnable entity receives a share of CPU time proportional to the share it is entitled to under the policy in force (equal shares for round-robin, weight-proportional for CFS, strict priority for real-time). Often measured as the variance between observed CPU time and the ideal allocation over an interval.	In Linux’s Completely-Fair Scheduler a task’s virtual runtime tracks the error from perfect fairness; the scheduler always chooses the task with the smallest accumulated error.
Overhead	The amount of processor time and cache/TLB bandwidth consumed by the act of scheduling itself—maintaining data structures, handling timer interrupts, performing context switches, reloading pipelines. High overhead subtracts directly from useful application work.	If a 1 ms quantum triggers a 5 µs context switch, 0.5 % of CPU capacity is lost to overhead; shrinking the quantum to 0.1 ms would waste 5 % in switches alone.
Starvation-risk	The possibility that a runnable task might wait an unbounded (or extremely long) time before receiving the CPU because higher-class or higher-priority tasks continually pre-empt it.	Classic fixed-priority schedulers can starve low-priority tasks until aging or priority inheritance mechanisms raise their effective priority.
Predictability	The scheduler’s ability to provide bounded and repeatable response times—i.e., small worst-case latency jitter—so that software can rely on timing guarantees. Also called determinism.	Hard real-time kernels use rate-monotonic or EDF algorithms for predictability; general-purpose OSs sacrifice some predictability to improve average-case throughput and fairness.

---

Similarities worth noting

• All four keep a ready list in RAM and select one runnable entity at each context switch.
• All can be implemented inside the same kernel; modern OSes often combine them (e.g. Linux’s CFS ≈ fair-share RR with dynamic priorities).