CPU Scheduling

CPU Scheduling Concepts

The CPU scheduler (short-term scheduler) selects which ready process/thread runs next on the CPU. It runs when:

1. A process switches from Running → Waiting (I/O request)
2. A process switches from Running → Ready (timer interrupt)
3. A process switches from Waiting → Ready (I/O complete)
4. A process terminates

Preemptive scheduling: OS can forcibly remove a process from the CPU. Non-preemptive (cooperative): process runs until it voluntarily yields or blocks.

Scheduling Criteria

Turnaround time = burst time + waiting time (when arrival = 0).

Scheduling Algorithms

First-Come, First-Served (FCFS)

Non-preemptive. Run in arrival order.

Avg wait = (0+7+10)/3 = 5.67 ms. Suffers convoy effect (short jobs stuck behind long ones).

Shortest Job First (SJF) — Non-Preemptive

Pick the job with the smallest next CPU burst. Optimal average waiting time.

(At t=8 both P2 and P3 have arrived; P3 is shorter, so it runs first.) Avg wait = (0+9+6)/3 = 5 ms.

Next burst prediction (exponential average): τₙ₊₁ = α · tₙ + (1 − α) · τₙ where tₙ = actual burst, τₙ = prediction, α ∈ [0,1] (typically 0.5).

Shortest Remaining Time First (SRTF) — Preemptive SJF

Preempt current job if a new arrival has a shorter remaining burst. Optimal mean waiting time for preemptive case. Starvation risk for long jobs.

Round Robin (RR)

Preemptive. Each process gets a time quantum q; after q expires, preempted to back of queue.

• Small q → responsive, high context-switch overhead
• Large q → degenerates to FCFS
• Rule of thumb: q should be > 80% of CPU bursts (typically 10–100 ms)

(All arrive at 0. After P3 finishes at 10 only P1 remains, so it runs 10–14, then keeps the CPU 14–16.) Avg wait: (6+4+8)/3 = 6 ms

Priority Scheduling

Each process has a priority number; highest priority (often lowest number) runs first. Can be preemptive or not.

Problem: starvation — low-priority processes may never run. Solution: aging — gradually increase priority of waiting processes over time.

Multilevel Queue (MLQ)

Separate queues for different process classes. Queues have fixed priorities.

Queue 0 (Interactive/System) — highest priority, RR q=8ms
Queue 1 (Interactive)        — medium priority,  RR q=16ms
Queue 2 (Batch)              — lowest priority,  FCFS

Multilevel Feedback Queue (MLFQ): processes can move between queues based on behavior. - New → highest-priority queue - Use full quantum → demote to lower queue - Wait too long → promote (aging) - Approximates SJF without knowing burst time in advance

Scheduling Algorithm Comparison

Real-Time Scheduling

Rate-Monotonic (RM)

Fixed-priority; shorter period → higher priority. Schedulable if: ∑(Cᵢ/Tᵢ) ≤ n(2^(1/n) − 1) → approaches ln 2 ≈ 69.3% as n → ∞

Earliest Deadline First (EDF)

Dynamic priority; closest deadline runs first. Achieves 100% utilization when feasible.

Multi-Processor Scheduling

Linux Schedulers: CFS and EEVDF

CFS (Completely Fair Scheduler) — Linux default from 2.6.23 (2007) through 6.5:

• Not time-sliced RR; uses a red-black tree keyed by vruntime
• vruntime = actual runtime × (1024 / weight); lower weight → faster vruntime growth
• Always runs the task with the smallest vruntime (leftmost node)
• nice values map to weights: nice −20 → weight 88761; nice 0 → 1024; nice +19 → 15
• Target latency: every runnable task gets one turn per period (default 6 ms for ≤8 tasks)

EEVDF (Earliest Eligible Virtual Deadline First) — replaced CFS as the default in kernel 6.6 (2023):

• Keeps CFS's weighted vruntime fairness model and nice→weight mapping
• Each task gets a virtual deadline = eligible time + slice/weight
• Runs the eligible task (one owed CPU time) with the earliest virtual deadline
• Better latency for interactive tasks, with fewer tunable heuristics than CFS