Scheduling: How the OS Chooses What Runs Next
The scheduler is the OS component that decides which ready process or thread gets to run next on each CPU core. Every context switch is thousands of wasted cycles, so the scheduler's goal is to pick the right one — fairness, throughput, low latency, or some mix.
The Three Classes of Scheduling
1. Long-Term Scheduler (Job Scheduler)
Decides which processes to admit from disk into memory. Rarely used in modern systems (most systems admit all processes immediately). Controls the degree of multiprogramming — how many processes are in memory at once.
2. Short-Term Scheduler (CPU Scheduler)
Decides which ready process to run next on a given core. Invoked on every timer interrupt (~100–1000 Hz) and on every syscall that might change a process's state. This is the hot path.
3. Medium-Term Scheduler
Decides which processes to swap in or out of memory. Not present in all systems.
Classic Algorithms
| Algorithm | How it works | Pros | Cons |
|---|---|---|---|
| FCFS (First-Come, First-Served) | Run in arrival order | Simple, fair | Convoy effect: short jobs behind long ones |
| SJF (Shortest Job First) | Run the job with the shortest next CPU burst | Optimal average waiting time | Requires knowing burst lengths; can starve long jobs |
| SRTF (Shortest Remaining Time First) | Preemptive SJF | Good response time | Still can starve |
| Priority | Run highest-priority job | Flexible | Can starve low-priority jobs |
| Round Robin | Each job gets a time slice (quantum) | Fair, good response time | Too-short quanta → too many context switches |
| Multilevel Queue | Separate queues per priority class | Balances interactive and batch | Complex, can starve |
| MLFQ (Multi-Level Feedback Queue) | Multiple queues with feedback (priority boosting) | Adapts to process behavior | Many tuning parameters |
Modern Linux: CFS
Linux uses the Completely Fair Scheduler (CFS), which replaced the O(1) scheduler in 2007. Instead of fixed priorities and time slices, CFS maintains a red-black tree of all runnable processes, keyed by their virtual runtime — a measure of how much CPU time they have consumed (weighted by priority).
On each scheduling decision, CFS picks the process with the smallest virtual runtime — the one that has had the least CPU time. This ensures fairness without the complexity of multiple queues. The scheduler also supports processor affinity (keeping a process on the same core for cache warmth) and load balancing across cores.
Real-Time Scheduling
For real-time systems, Linux provides:
- SCHED_FIFO — first-in, first-out; a running real-time process runs until it blocks or yields
- SCHED_RR — round-robin among real-time processes of the same priority
- SCHED_DEADLINE — each task gets a runtime budget and period; the kernel guarantees the budget is met or the task is killed
References
This article is part of the Advanced Networking and Performance learning path.