CPU Scheduling

Why scheduling is needed: Multiple processes competing for CPU cores. Without scheduling, one process would run forever. Scheduling multiplexes the CPU across processes, creating the illusion of parallelism on a single core, ensuring fairness, and minimizing response time.

FCFS (First Come First Served): Processes run in arrival order. Non-preemptive. Simple to implement. Problem: convoy effect — one long CPU-bound job blocks all short jobs behind it. Average wait time = high if there is one long job ahead of many short ones. Not used in interactive systems.

Round Robin: Each process gets a fixed time quantum (e.g., 10ms), then is preempted and moved to the back of the ready queue. Preemptive. Fair — every process gets regular CPU turns. Good average response time for interactive workloads. Problem: if quantum is too small, context switch overhead dominates (thrashing). If too large, approaches FCFS behavior. Typical quantum: 10–100ms.

Priority Scheduling: Each process has a priority. Highest-priority process runs first. Can be preemptive (a higher-priority arrival preempts the current process) or non-preemptive. Problem: starvation — low-priority processes may wait indefinitely if high-priority ones keep arriving. Solution: aging — gradually increase the priority of waiting processes so they eventually run.

Shortest Job First (SJF) / Shortest Remaining Time First (SRTF): Run the process with the shortest expected CPU burst first. Provably optimal for minimizing average wait time. Problem: requires knowing (or estimating) burst duration in advance. SRTF (preemptive SJF) preempts the current process if a new process arrives with a shorter remaining time.

graph TD q1["Queue 1 (highest priority, short quantum)"] -->|"uses full quantum, still running"| q2["Queue 2 (medium priority, longer quantum)"] q2 -->|"uses full quantum, still running"| q3["Queue 3 (lowest priority, longest quantum)"] q1 -.->|"blocks before quantum ends (I/O-bound)"| q1

Multilevel Feedback Queue: Multiple queues with different priorities. New processes start at the highest-priority queue. If a process uses its full quantum without blocking, it is demoted to the next queue (it must be CPU-bound). Processes that block before using their quantum stay at the same level (they are I/O-bound, short bursts). I/O-bound processes stay at high priority (low latency). CPU-bound processes migrate to lower-priority queues (less CPU time). This automatically adapts to process behavior.

CFS (Completely Fair Scheduler — Linux default): Tracks vruntime (virtual runtime, weighted by priority) per task in a red-black tree. The task with the smallest vruntime runs next — always catching up the most-lagging task. Timer interrupt every 4ms checks if the current task has accumulated enough vruntime to give way. Lower nice value = slower vruntime accumulation = more CPU time.

Trade-off: fairness vs performance: Pure fairness (Round Robin) gives everyone equal CPU but CPU-bound batch jobs suffer from frequent context switches. Throughput-optimal (SJF) minimizes average wait time but starves long jobs. In practice: multilevel feedback queue balances both — interactive tasks get low latency, batch tasks get eventual CPU time with less context switching overhead.

Common pitfall

Assuming SJF/SRTF could just be implemented in a real general-purpose OS because it's "provably optimal" ignores the actual blocker: it requires knowing burst duration in advance, which the scheduler fundamentally cannot know for an arbitrary process before running it. This is exactly why MLFQ exists — it approximates SJF's benefit (favor short/interactive bursts) using only information the kernel actually has (whether a process used its full quantum), without ever needing to predict the future.