CPU Scheduling
A preemptive scheduler can take the CPU away from a running task (on a timer interrupt or when a higher-priority task becomes ready); a non-preemptive one waits until the task blocks or finishes.
Concept
Goals and Metrics CPU utilization Fraction of time the CPU is busy Jobs completed per time unit Turnaround time Completion − arrival Waiting time
Turnaround − burst (time spent in the ready queue) Response time
First run − arrival (important for interactive tasks) Fairness / deadlines
No starvation; real-time tasks meet deadlines A preemptive scheduler can take the CPU away from a running task (on a timer interrupt or when a higher-priority task becomes ready); a non-preemptive one waits until the task blocks or finishes. The dispatcher performs the context switch.
Run in arrival order Simple; convoy effect (short jobs wait behind long ones) Shortest burst first
Optimal average waiting time (non-preemptive); needs burst estimates; starvation
Preemptive SJF: shortest *remaining* time Best average waiting; many switches; starvation Highest priority first
Flexible; starvation → fix with aging Round Robin Each task gets a time quantum, then goes to the back of the queue
Good response time; too small a quantum = switching overhead, too large = FCFS Multilevel (feedback) queues
Several queues with different policies; tasks move between them based on behaviour
Favours interactive tasks; used in many OSes Burst lengths are unknown in practice; they are predicted with exponential averaging of past bursts: τₙ₊₁ = α·tₙ + (1 − α)·τₙ.
Linux normal tasks (SCHED_OTHER): CFS ("Completely Fair Scheduler") gave each task CPU time in proportion to its weight (from the nice value −20…19); since kernel 6.6 it is replaced by EEVDF (Earliest Eligible Virtual Deadline First), which also considers latency. Real-time policies SCHED_FIFO and SCHED_RR (priorities 1–99) always run before normal tasks; SCHED_DEADLINE implements EDF.
Real-time theory: Rate-Monotonic (fixed priority, shorter period = higher priority; schedulable if utilization ≤ n(2^(1/n) − 1)) and Earliest Deadline First (optimal on one core for utilization ≤ 1). Priority inversion (a high-priority task waits for a low-priority one holding a lock) is solved with priority inheritance — the famous Mars Pathfinder bug.
Multiprocessor scheduling adds per-CPU run queues, load balancing and processor affinity (keeping a task on the same core for cache warmth).
Why It Matters
Scheduling explains latency spikes, why a busy background job slows a UI, how to configure real-time threads for control loops or audio, and it's a staple of OS exams and interviews (Gantt charts and average waiting time).
Syntax
nice -n 10 cmd / renice Lower (or raise) a normal task's priority chrt -f 50 cmd
Run with SCHED_FIFO priority 50 (needs privileges) taskset -c 2 cmd
sched_setscheduler(), pthread_setschedparam() Set policy from code Voluntary/involuntary context switches
Example
14.1 A scheduling simulator: five algorithms on the same workload
14.2 Linux scheduling policies and priorities 14.3 Voluntary context switches
"""CPU scheduling simulator: FCFS, SJF, SRTF, Round Robin and Priority on the same workload."""
PROCS = [ # name, arrival, burst, priority (lower number = higher priority)
("P1", 0, 8, 2),
("P2", 1, 4, 3),
("P3", 2, 9, 1),
("P4", 3, 5, 4),
]
def simulate(pick, preemptive, quantum=None):
t, done, timeline = 0, {}, []
remaining = {p[0]: p[2] for p in PROCS}
ready_order, queue = [], []
current, slice_used = None, 0
while len(done) < len(PROCS):
for p in PROCS: # arrivals join the ready queue
if p[1] == t:
queue.append(p)
if current and quantum and slice_used == quantum: # RR: quantum expired -> back of the queue
queue.append(current); current = None
if current is None or preemptive:
candidates = queue + ([current] if current else [])
if candidates:
nxt = pick(candidates, remaining)
if current and nxt is not current:
queue.append(current)
if nxt in queue:
queue.remove(nxt)
if nxt is not current:
slice_use
…$ chrt -p $$
pid 183's current scheduling policy: SCHED_OTHER
pid 183's current scheduling priority: 0
$ nice -n 10 sh -c 'ps -o pid,ni,pri,cls,comm -p $$'
PID NI PRI CLS COMMAND
187 10 9 TS sh
$ chrt -m | head -3
SCHED_OTHER min/max priority : 0/0
SCHED_FIFO min/max priority : 1/99
SCHED_RR min/max priority : 1/99#include <stdio.h>
#include <unistd.h>
#include <sys/resource.h>
int main(void)
{
struct rusage r;
for (int i = 0; i < 50; i++) usleep(1000); /* blocking: gives up the CPU voluntarily */
getrusage(RUSAGE_SELF, &r);
printf("after 50 sleeps : voluntary %ld, involuntary %ld context switches\n", r.ru_nvcsw, r.ru_nivcsw);
return 0;
}Expected Result
FCFS suffers from the convoy effect: P4 waits 18 units behind P1 and P3.
SRTF gives the best average waiting time (6.50) — it always runs the job closest to finishing; P3, the longest, waits 15.
Priority lets P3 (priority 1) preempt P1 at time 2; low-priority P4 waits 18 — without aging it could starve.
Round Robin has the worst averages here but the best response time: every process starts within 9 time units.
The shell runs under SCHED_OTHER; nice -n 10 gave the child nice value 10 (TS = time-sharing class). Real-time policies use priorities 1–99.
Each usleep blocked the process, a voluntary context switch; involuntary switches happen when the scheduler preempts a task whose time slice ran out.
process arrival burst priority
P1 0 8 2
P2 1 4 3
P3 2 9 1
P4 3 5 4
FCFS P1[0-8] P2[8-12] P3[12-21] P4[21-26]
waiting [0, 7, 10, 18] avg 8.75 | turnaround avg 15.25
SJF (non-preemptive) P1[0-8] P2[8-12] P4[12-17] P3[17-26]
waiting [0, 7, 15, 9] avg 7.75 | turnaround avg 14.25
SRTF (preemptive SJF) P1[0-1] P2[1-5] P4[5-10] P1[10-17] P3[17-26]
waiting [9, 0, 15, 2] avg 6.50 | turnaround avg 13.00
Priority (preemptive) P1[0-2] P3[2-11] P1[11-17] P2[17-21] P4[21-26]
waiting [9, 16, 0, 18] avg 10.75 | turnaround avg 17.25
Round Robin q=3 P1[0-3] P2[3-6] P3[6-9] P4[9-12] P1[12-15] P2[15-16] P3[16-19] P4[19-21] P1[21-23] P3[23-26]
waiting [15, 11, 15, 13] avg 13.50 | turnaround avg 20.00$ chrt -p $$
pid 183's current scheduling policy: SCHED_OTHER
pid 183's current scheduling priority: 0
$ nice -n 10 sh -c 'ps -o pid,ni,pri,cls,comm -p $$'
PID NI PRI CLS COMMAND
187 10 9 TS sh
$ chrt -m | head -3
SCHED_OTHER min/max priority : 0/0
SCHED_FIFO min/max priority : 1/99
SCHED_RR min/max priority : 1/99after 50 sleeps : voluntary 50, involuntary 0 context switchesCommon Mistakes
Computing waiting time as start time − arrival for preemptive algorithms (it must include every period spent waiting).
Choosing a Round Robin quantum smaller than the context-switch cost.
Running CPU-bound code at real-time priority without a sleep — it can lock up the machine.
Ignoring priority inversion when real-time threads share locks with normal ones.
Best Practices
Use real-time policies only for tasks with genuine deadlines, and use priority-inheritance mutexes (PTHREAD_PRIO_INHERIT).
Pin latency-critical threads to dedicated cores (isolcpus, taskset) on test benches.
Lower the priority of batch jobs with nice instead of hoping the scheduler guesses.
Interview Relevance
Very high: "compare FCFS, SJF, RR, priority", "compute average waiting time (Gantt chart)", "what is starvation and aging?", "preemptive vs non-preemptive?", "what is priority inversion?", "how does the Linux scheduler work?".
Practice Questions
Run the simulator with quantum 1 and 10 and explain the change.
Add aging to the priority scheduler (priority improves by 1 every 5 units of waiting).
Compute by hand the waiting times for SJF with bursts 6, 8, 7, 3 all arriving at 0.
Check whether tasks with (C=1, T=4), (C=2, T=6), (C=3, T=12) are schedulable under Rate-Monotonic.
Quick Quiz
Q1. (Multiple choice) Which algorithm minimizes average waiting time when all jobs are available at once? A) FCFS B) SJF C) Round Robin D) Priority Answer: B.
Q2. (Predict the output) Average waiting time of SRTF in the example?
Answer: 6.50 (verified).
Q3. (True/False) Round Robin with a very large quantum behaves like FCFS.
Answer: True. Q4. (Find the bug) A low-priority logger holds a mutex needed by a high-priority control task, while a medium-priority task runs for seconds; the control task misses deadlines.
Answer: Priority inversion: use priority inheritance (or priority ceiling) mutexes.
Coding Challenge
Compute the average waiting and turnaround time for non-preemptive SJF when all jobs arrive at time 0 with bursts 6, 8, 7 and 3.
bursts = {"P1": 6, "P2": 8, "P3": 7, "P4": 3}
t, waits, tats = 0, {}, {}
for name, burst in sorted(bursts.items(), key=lambda kv: kv[1]): # shortest job first
waits[name] = t
t += burst
tats[name] = t
print("order:", " -> ".join(sorted(bursts, key=bursts.get)))
print("waiting:", waits, "average", sum(waits.values()) / len(waits))
print("turnaround average", sum(tats.values()) / len(tats))