CPU scheduling

Computer Science and Engineering (B.E./B.Tech) · Operating systems · free study notes for exams, placements and interviews

In short

CPU scheduling decides which ready process or thread gets the single CPU (or core) next, and for how long, so that the processor is never idle while work is waiting. It is the part of the operating system that turns a list of runnable jobs into an execution order, and that order decides whether a system feels fast, fair or starved. The topic is examined in every university OS paper (Gantt charts, average waiting and turnaround time) and is a guaranteed GATE CS question, usually numerical. In interviews it appears in systems roles at Qualcomm, Samsung R&D, Intel, Texas Instruments, Bosch, Tata Elxsi, KPIT, Nvidia, VMware, Oracle, Amazon and Microsoft IDC, and in every embedded or RTOS job where deadlines, not averages, are the requirement.

Explained

Fundamentals: bursts, schedulers and the dispatcher

A process alternates between a CPU burst (computing) and an I/O burst (waiting for a device). Burst lengths follow a hyper-exponential-like curve: very many short bursts, a few long ones — which is why "favour the short job" works.
CPU-bound process: few, long CPU bursts. I/O-bound process: many, short bursts. A good mix keeps both the CPU and the devices busy.
Long-term scheduler (job scheduler): admits jobs into memory; controls the degree of multiprogramming. Almost absent in modern time-sharing systems like Linux and Windows.
Medium-term scheduler: swaps processes out of memory and back in, to relieve memory pressure or reduce the degree of multiprogramming.
Short-term scheduler (CPU scheduler): picks from the ready queue, runs in milliseconds, must itself be fast — this is "CPU scheduling".
Dispatcher: actually hands the CPU over — context switch, switch to user mode, jump to the right instruction. Dispatch latency is the time it takes; the scheduler chooses, the dispatcher acts.
Scheduling decisions arise when a process: (1) runs → waits (I/O, wait()); (2) runs → ready (interrupt, quantum expiry); (3) waits → ready (I/O completion); (4) terminates. Cases 1 and 4 only → non-preemptive; all four → preemptive.
Non-preemptive: once given the CPU, a process keeps it until it blocks or exits. Simple, low overhead, but one long job freezes the system.
Preemptive: the OS can take the CPU back. Needed for time sharing and real time, but costs context switches and requires shared kernel data to be protected (race conditions, and a preemptible kernel needs locking).

Scheduling criteria

CPU utilisation — percentage of time the CPU is doing useful work (maximise).
Throughput — processes completed per unit time (maximise).
Turnaround time (TAT) — submission to completion (minimise).
Waiting time (WT) — total time spent in the ready queue; the only part scheduling really changes (minimise).
Response time (RT) — arrival to the *first* time the process gets the CPU; the criterion for interactive systems (minimise).
Fairness and predictability (low variance) — a consistent 10 s is often better for users than 2 s or 20 s at random.
Criteria conflict: optimising average turnaround (SJF) starves long jobs; optimising fairness (RR) worsens turnaround. Some systems also minimise the *maximum* or the *variance* rather than the average.

The classical algorithms

FCFS (First Come First Served): non-preemptive, FIFO ready queue. Simple and fair in arrival order, but average waiting time is high and varies wildly with order. Suffers the convoy effect — one CPU-bound process holds the CPU while many short I/O-bound processes queue behind it, leaving devices idle.
SJF (Shortest Job First), non-preemptive: pick the smallest *next CPU burst*. Provably optimal for minimum average waiting time when all jobs are available together. Problem: the next burst length is not known — it is predicted by exponential averaging of past bursts. Long jobs can starve.
SRTF (Shortest Remaining Time First): preemptive SJF — on each arrival, compare the new burst with the remaining time of the running process. Optimal average waiting time overall, but more context switches and worse starvation.
Priority scheduling: each process gets a priority number (convention in most textbooks and GATE: *smaller number = higher priority*; always state your convention). Preemptive or non-preemptive. SJF is priority scheduling with priority = 1/burst. Main defect is indefinite blocking (starvation); the cure is aging — raise a waiting process's priority by one step every fixed interval.
Round Robin (RR): FCFS plus preemption after a fixed time quantum (typically 10–100 ms). Every process gets the CPU within (n−1)q. Best response time, worst turnaround time. Quantum choice is critical: too large → degenerates to FCFS; too small → context-switch overhead dominates. Rule of thumb: 80% of CPU bursts should be shorter than the quantum.
HRRN (Highest Response Ratio Next): non-preemptive, picks the largest (waiting time + service time)/service time. Favours short jobs but the ratio grows with waiting, so no starvation — an aging mechanism built into the formula.
Multilevel Queue: ready queue permanently split by process class (system, interactive, interactive editing, batch, student). Each queue has its own algorithm (RR for interactive, FCFS for batch); between queues, fixed-priority preemption or a time slice per queue (e.g. 80% to foreground RR, 20% to background FCFS). Processes do not move between queues.
Multilevel Feedback Queue (MLFQ): queues with decreasing priority and increasing quantum; a new process enters the top queue; if it uses up its quantum it is demoted; after a long wait or periodically, all processes are promoted back to the top (to prevent starvation and handle a job that changes behaviour). It approximates SJF without knowing burst lengths — the most general and most configurable scheme. Parameters: number of queues, algorithm per queue, promotion rule, demotion rule, entry queue.
Lottery / fair-share / proportional-share: tickets or shares are distributed and the winner is chosen at random or by stride; used for group fairness (per user, per container).

Real-time and multiprocessor scheduling

Hard real time: missing a deadline is a system failure (airbag ECU, flight control, ISRO launch-vehicle avionics). Soft real time: a miss degrades quality (video playback, VoIP).
Latency that matters: interrupt latency + dispatch latency; the conflict phase of dispatch latency (preempting a kernel process, releasing its resources) must be bounded, which is why an RTOS needs a fully preemptible kernel.
Rate Monotonic Scheduling (RMS): static priorities, shorter period = higher priority. Optimal among *fixed-priority* algorithms. Utilisation bound U ≤ n(2^1/n − 1) is sufficient but not necessary; above it, use exact response-time analysis.
Earliest Deadline First (EDF): dynamic priority, nearest absolute deadline first. Optimal for a uniprocessor — schedulable whenever U ≤ 1 — but behaves badly (domino effect) on overload. Least Laxity First (LLF) uses slack = deadline − now − remaining computation.
Priority inversion: a high-priority task waits on a lock held by a low-priority task that is itself preempted. Fixed by priority inheritance or priority ceiling protocols — the famous Mars Pathfinder bug.
Multiprocessor: asymmetric (one master CPU schedules) vs SMP (each core schedules itself from a shared or per-core run queue). Per-core run queues avoid lock contention but need load balancing by push migration (a daemon moves tasks off a loaded core) and pull migration (an idle core steals work).
Processor affinity: keeping a task on the same core preserves its cache. Soft affinity is a preference, hard affinity is enforced (Linux sched_setaffinity, taskset). Important on NUMA machines, where memory is faster near the owning core.
SMT / hyperthreading: hardware threads share one core's pipeline, so the OS must schedule at two levels — threads to logical CPUs, and logical CPUs to physical cores. big.LITTLE / heterogeneous SoCs (every Indian-market smartphone) add Energy Aware Scheduling: place a task on the cheapest core that meets its demand.
Contention scope for threads: PCS (process-contention scope — user threads compete within a process, many-to-one and many-to-many models) vs SCS (system-contention scope — kernel threads compete system-wide; Linux and Windows use only SCS).

Schedulers in real systems

Linux, 2.6.23 to 6.5 — CFS (Completely Fair Scheduler): no fixed timeslices; each task carries a vruntime (virtual runtime) and the task with the smallest vruntime, kept in a red-black tree, runs next (the leftmost node is cached, so the pick is O(1) and insertion O(log n)). vruntime advances faster for low-priority tasks, so all tasks converge to a fair share.
nice values run from −20 (most favoured) to +19; default 0. Each nice step changes CPU share by roughly 1.25×. Only a privileged user may set a negative nice.
Scheduling classes/policies: SCHED_OTHER (normal/CFS), SCHED_BATCH, SCHED_IDLE, and the real-time SCHED_FIFO (run until blocked or preempted) and SCHED_RR (RT round robin), plus SCHED_DEADLINE (EDF with a constant-bandwidth server, specified as runtime/deadline/period). RT priorities 1–99 always beat normal tasks; by default RT tasks are throttled to 95% of CPU to keep the system usable.
Linux 6.6 onward replaced CFS with EEVDF (Earliest Eligible Virtual Deadline First), which adds a latency/deadline notion to the same fair-share idea — if quoting kernel internals in an interview, say which kernel series you mean.
cgroups give group-level fair share (cpu.shares/cpu.weight, cpu.max quota); this is how Docker and Kubernetes limit container CPU on cloud infrastructure.
Windows: 32 priority levels — variable class 1–15 and real-time class 16–31; quantum-based round robin within a level, with priority boosting on I/O completion and for the foreground window, and a lower priority on quantum expiry (never below the base).
Solaris: six classes (time sharing, interactive, system, real time, fair share, fixed priority) with a dispatch table — the classic MLFQ implementation in textbooks.

Key points

Short-term scheduler - picks a ready process for the CPU, runs very frequently, must be cheap.
Dispatcher - performs the context switch; its cost is pure overhead and is measured as dispatch latency.
Preemptive vs non-preemptive - whether the OS can take the CPU back before the process yields it.
Waiting time - turnaround minus service time; the only metric scheduling can directly reduce.
Response time - time to *first* execution; the criterion for interactive and mobile systems.
FCFS - simple, non-preemptive, suffers the convoy effect and high average waiting time.
SJF - minimum average waiting time when all jobs arrive together; needs burst prediction, starves long jobs.
SRTF - preemptive SJF, the true optimum for average waiting time, at the cost of context switches.
Exponential averaging - predicts the next burst from history, τ(n+1) = αt(n) + (1−α)τ(n).
Priority scheduling - starvation is the defect, aging is the standard cure.
Round Robin - fair and responsive; performance depends entirely on the quantum relative to burst length.
MLFQ - demote CPU hogs, promote waiters; approximates SJF without knowing burst lengths.
HRRN - (W+S)/S; short jobs first but waiting raises the ratio, so no starvation.
Convoy effect - short I/O-bound jobs stuck behind one long CPU-bound job, idling the devices.
RMS - static, shorter period = higher priority, bound n(2^1/n−1), sufficient not necessary.
EDF - dynamic, nearest deadline first, uniprocessor-optimal up to U = 1.
Processor affinity - keep a task on one core to retain its cache; soft (preferred) or hard (enforced).
Linux CFS/EEVDF - fair share by vruntime in a red-black tree; nice −20…+19, each step ≈ 1.25× CPU.

Formulas and examples

Turnaround time, TAT = Completion time (CT) − Arrival time (AT) — units: ms or s
Waiting time, WT = TAT − Burst time (BT) = TAT − CPU service time
Response time, RT = time of first dispatch − AT
Averages: Avg X = (ΣXi)/n for n processes
Throughput = number of processes completed / total time; CPU utilisation = busy time / total time × 100%
Degree of multiprogramming: CPU utilisation = 1 − pⁿ, where p = fraction of time a process waits on I/O, n = processes in memory
Burst prediction: τ(n+1) = α·t(n) + (1−α)·τ(n); 0 ≤ α ≤ 1, t = actual last burst, τ = predicted burst
HRRN response ratio = (W + S)/S, W = waiting time so far, S = estimated service time
Round robin with context-switch cost s: useful CPU fraction = q/(q + s); worst wait for next turn = (n−1)(q + s)
RMS schedulability (sufficient): U = Σ(Ci/Ti) ≤ n(2^1/n − 1); EDF (necessary and sufficient, uniprocessor): U ≤ 1
CFS: vruntime += Δt × (1024 / weight_of_task); timeslice_i = sched_period × w_i / Σw

Example 1 — four algorithms on one workload. P1(AT 0, BT 7), P2(AT 2, BT 4), P3(AT 4, BT 1), P4(AT 5, BT 4).

FCFS Gantt chart:

| P1   0-7 | P2  7-11 | P3 11-12 | P4 12-16 |

CT = 7, 11, 12, 16 → TAT = 7, 9, 8, 11 (avg 35/4 = 8.75); WT = 0, 5, 7, 7 (avg 19/4 = 4.75).

SJF (non-preemptive): at t = 7 the ready set is P2(4), P3(1), P4(4) → P3 first, P2 before P4 on tie-break by arrival.

| P1 0-7 | P3 7-8 | P2 8-12 | P4 12-16 |

TAT = 7, 10, 4, 11 (avg 32/4 = 8.00); WT = 0, 6, 3, 7 (avg 16/4 = 4.00).

SRTF (preemptive): P2 preempts P1 at t = 2, P3 preempts P2 at t = 4.

| P1 0-2 | P2 2-4 | P3 4-5 | P2 5-7 | P4 7-11 | P1 11-16 |

CT: P1 16, P2 7, P3 5, P4 11 → TAT = 16, 5, 1, 6 (avg 28/4 = 7.00); WT = 9, 1, 0, 2 (avg 12/4 = 3.00) — the minimum possible.

Round Robin, q = 2 (new arrival enters the queue before the preempted process):

|P1 0-2|P2 2-4|P1 4-6|P3 6-7|P2 7-9|P4 9-11|P1 11-13|P4 13-15|P1 15-16|

CT: P1 16, P2 9, P3 7, P4 15 → TAT = 16, 7, 3, 10 (avg 36/4 = 9.00); WT = 9, 3, 2, 6 (avg 20/4 = 5.00); 9 slices → 8 inter-process context switches. Response times: P1 0, P2 0, P3 2, P4 4 — none above (n−1)q = 6, which is RR's real strength.

Algorithm	Avg TAT (ms)	Avg WT (ms)	Preemptive	Starvation
FCFS	8.75	4.75	No	No
SJF	8.00	4.00	No	Yes
SRTF	7.00	3.00	Yes	Yes
RR (q = 2)	9.00	5.00	Yes	No

Example 2 — priority scheduling (smaller number = higher priority). P1(AT 0, BT 4, pr 3), P2(AT 1, BT 3, pr 1), P3(AT 2, BT 1, pr 4), P4(AT 3, BT 5, pr 2).

Non-preemptive: P1 0-4, P2 4-7, P4 7-12, P3 12-13. TAT = 4, 6, 11, 9 → avg 30/4 = 7.5; WT = 0, 3, 10, 4 → avg 17/4 = 4.25.
Preemptive: P2 preempts P1 at t = 1. P1 0-1, P2 1-4, P4 4-9, P1 9-12, P3 12-13. TAT = 12, 3, 11, 6 → avg 32/4 = 8.0; WT = 8, 0, 10, 1 → avg 19/4 = 4.75.
Note P3 (lowest priority) waits 10 ms in both; with a steady stream of higher-priority arrivals it would never run — this is where aging is applied.

Example 3 — burst prediction. τ1 = 10 ms, α = 0.5, actual bursts 6, 4, 6, 4. τ2 = 0.5(6) + 0.5(10) = 8; τ3 = 0.5(4) + 0.5(8) = 6; τ4 = 0.5(6) + 0.5(6) = 6; τ5 = 0.5(4) + 0.5(6) = 5 ms. With α = 0 the prediction never changes; with α = 1 only the last burst counts.

Example 4 — quantum, overhead and utilisation. Context switch s = 0.5 ms, 10 identical processes.

q = 1 ms → useful fraction 1/1.5 = 66.7%; q = 4 ms → 4/4.5 = 88.9%; q = 10 ms → 10/10.5 = 95.2%.
Worst-case wait for the next turn at q = 4: (10−1)(4 + 0.5) = 40.5 ms — acceptable for interaction; at q = 100 ms it becomes 904.5 ms, which users feel as lag.
I/O overlap: with p = 0.8, CPU utilisation = 1 − 0.8ⁿ → n = 1: 20%, n = 4: 59.0%, n = 10: 89.3%.

Example 5 — real-time schedulability. Tasks T1(C = 1, T = 4), T2(C = 2, T = 6), T3(C = 1, T = 8).

U = 1/4 + 2/6 + 1/8 = 0.250 + 0.333 + 0.125 = 0.708. RM bound for n = 3 = 3(2^1/3 − 1) = 3(0.2599) = 0.780. Since 0.708 ≤ 0.780, the set is schedulable by RMS (and by EDF, as U ≤ 1).
Counter-case: T1(C = 2, T = 5), T2(C = 2, T = 4) → U = 0.4 + 0.5 = 0.90 > 0.828 (bound for n = 2), so the RM test is inconclusive. Response-time analysis: for T2 (higher priority, shorter period) R = 2 ≤ 4; for T1, R = 2 + ⌈2/4⌉×2 = 4, then 2 + ⌈4/4⌉×2 = 4 ≤ 5 — it converges, so it *is* schedulable. The bound is sufficient, not necessary.

Example 6 — Linux nice weights. Task A at nice 0 (weight 1024) and task B at nice 5 (weight 335) on one core: A gets 1024/1359 = 75.3%, B gets 335/1359 = 24.7%, a ratio of 3.06 ≈ 1.25^5. With sched_period = 6 ms, A's slice ≈ 4.5 ms and B's ≈ 1.5 ms.

Where it is used

Mobile and consumer SoCs: Qualcomm, Samsung R&D Bengaluru/Noida and MediaTek India teams tune Linux/Android schedulers, Energy Aware Scheduling and big.LITTLE core placement for battery life and touch responsiveness.
Automotive and industrial embedded: Bosch, Continental, KPIT, Tata Elxsi and L&T Technology Services build AUTOSAR OS / FreeRTOS / QNX tasks with fixed-priority (RM-style) scheduling and WCET budgets for ECUs, BS-VI engine control and ADAS.
Aerospace and defence: ISRO and DRDO avionics and ground systems use hard real-time scheduling with provable deadlines; priority inversion and jitter are design review items.
Cloud, DevOps and SRE: Kubernetes requests/limits map onto Linux cgroup cpu.weight and CFS bandwidth quota; nice, chrt, taskset, top, pidstat and perf sched are everyday tools. Throttling caused by a tight CPU quota is a classic production incident.
HPC and research computing: C-DAC PARAM systems under the National Supercomputing Mission, and IIT/IISc clusters, run batch schedulers (SLURM, PBS) — the same FCFS/priority/backfilling ideas at job granularity.
Financial and payment systems: low-latency trading at NSE/BSE co-location sites and UPI switch backends pin threads with hard affinity, isolate cores and use SCHED_FIFO to remove scheduling jitter.
Exams and roles: GATE CS (numerical), UGC-NET, PSU interviews (BEL, BHEL, ISRO scientist/engineer), and systems/kernel/embedded engineer roles generally.

Interview questions

Q: What is the difference between preemptive and non-preemptive scheduling? A: Non-preemptive gives up the CPU only when the process blocks or terminates; preemptive lets the OS reclaim it on a timer or a higher-priority arrival. Preemption enables time sharing and real time but adds context-switch cost and needs protected kernel data.
Q: Which algorithm gives the minimum average waiting time, and what stops us from using it? A: SJF (SRTF if preemption is allowed), but the next CPU burst length is unknown at scheduling time, so it must be estimated by exponential averaging; it also starves long jobs.
Q: What is the convoy effect? A: Under FCFS, short I/O-bound processes pile up behind one long CPU-bound process, so the CPU and the I/O devices are both used badly.
Q: How do you choose a round-robin time quantum? A: Large enough that most CPU bursts finish within it and context-switch overhead stays small, but small enough that (n−1)q keeps response time acceptable — typically 10–100 ms on general-purpose systems.
Q: What is starvation and how is it prevented? A: A low-priority process never gets the CPU because higher-priority ones keep arriving; aging fixes it by increasing a process's priority the longer it waits (HRRN builds this into its formula).
Q: Difference between waiting time and response time? A: Waiting time is the total time in the ready queue over the whole run; response time is only the delay until the process first gets the CPU — RR optimises response time while worsening turnaround.
Q: How does a multilevel feedback queue approximate SJF without knowing burst lengths? A: A new process starts at the top queue; if it exhausts its quantum it is demoted to a lower-priority queue with a longer quantum, so short interactive bursts stay high and CPU hogs sink, with periodic promotion to avoid starvation.
Q: Explain Linux CFS in two lines. A: Each task accumulates virtual runtime scaled inversely to its weight (set by nice), and the scheduler always picks the task with the smallest vruntime from a red-black tree, so CPU time converges to each task's fair share. From kernel 6.6 this was replaced by EEVDF, which adds a virtual deadline for latency sensitivity.
Q: Why is EDF better than RMS on paper but rarer in safety-critical systems? A: EDF achieves full utilisation (U ≤ 1) while RMS is limited to about 69% in the worst case, but EDF has dynamic priorities, higher runtime cost and unpredictable cascading misses on overload, whereas fixed priorities are easier to certify.
Q: What is priority inversion and its standard fix? A: A high-priority task blocks on a lock held by a low-priority task that is itself preempted by a medium-priority one; priority inheritance temporarily raises the lock holder's priority until it releases the lock.
Q: What is processor affinity and why does it matter? A: Binding or preferring a task to a particular core preserves its cache (and local NUMA memory); migrating it costs cache misses, so the load balancer weighs affinity against imbalance.
Q: A container has a CPU limit of 0.5 and the app's latency is spiking in bursts. Why? A: CFS bandwidth control gives 50 ms of runtime per 100 ms period; once the quota is used the whole cgroup is throttled until the next period, producing periodic stalls — visible as nr_throttled in cgroup stats.

Common mistakes

Computing waiting time as CT − BT instead of TAT − BT (that is, forgetting to subtract the arrival time).
Ignoring arrival times — scheduling a process that has not arrived yet, or leaving the CPU busy when it should be idle in the gap before the next arrival.
In round robin, getting the queue order wrong at the instant a process is preempted and another arrives: the newly arrived process normally enters the ready queue *before* the preempted one (state the assumption in the answer).
Assuming "priority 1" always means highest — conventions differ (Linux nice −20 is most favoured, Windows 31 is highest); define it before solving.
Quoting the RMS utilisation bound as a pass/fail test: failing the bound does not prove the task set is unschedulable — response-time analysis may still pass it.
Claiming SJF is "always optimal" without the conditions (non-preemptive, all jobs available at the same time, known burst lengths).
Ignoring context-switch overhead when recommending a tiny quantum, and confusing *process* context switch with mode switch (a system call is only a mode switch and is far cheaper).