CPU Scheduling Algorithms
CPU scheduling determines which process in the ready queue gets to run next on the CPU. The scheduler's decisions directly affect system responsiveness, throughput, and fairness. Different workloads demand different strategies, and modern operating systems use sophisticated algorithms that adapt to process behavior.
Scheduling Goals
| Goal | Definition |
|---|---|
| Fairness | Every process gets a reasonable share of CPU time |
| Throughput | Maximize the number of processes completed per unit time |
| Turnaround time | Minimize total time from submission to completion |
| Response time | Minimize time from request to first response (critical for interactive apps) |
| No starvation | Every process eventually gets to run |
These goals often conflict -- optimizing for throughput may sacrifice response time, and vice versa.
Simple Algorithms
FCFS (First-Come, First-Served): Processes run in arrival order until they block or finish. Simple but suffers from the convoy effect -- a single long-running (CPU-bound) process blocks all shorter processes behind it, inflating average wait time.
Round-Robin (RR): Each process gets a fixed time quantum (e.g., 10 ms). When the quantum expires, the process is preempted and placed at the back of the ready queue. Provides good response time for interactive workloads. The quantum is a tradeoff: too small means excessive context switch overhead; too large degenerates into FCFS.
Priority Scheduling: Each process has a priority number. The scheduler always picks the highest-priority ready process. Risk: starvation -- low-priority processes may never run if high-priority processes keep arriving. Solution: priority aging -- gradually increase the priority of waiting processes.
MLFQ (Multi-Level Feedback Queue)
MLFQ uses multiple priority queues. New processes enter the highest-priority queue. The rules are:
- If a process uses its entire time quantum (CPU-bound behavior), it is demoted to a lower-priority queue with a longer quantum.
- If a process voluntarily yields before its quantum expires (I/O-bound behavior), it stays at the same level or is promoted.
- Periodically, all processes are boosted to the highest queue to prevent starvation.
This automatically separates I/O-bound (interactive) processes from CPU-bound (batch) processes without requiring manual priority assignment.
CFS (Completely Fair Scheduler) -- Linux
Linux's default scheduler since kernel 2.6.23, CFS tracks the virtual runtime (vruntime) of each process -- the amount of CPU time it has received, weighted by priority. CFS uses a red-black tree ordered by vruntime:
- The process with the smallest vruntime (leftmost node) runs next -- it has received the least CPU time.
- When a process runs, its vruntime increases proportionally to wall-clock time (adjusted by its nice value).
- Picking the next process is O(log n) (leftmost extraction from the red-black tree).
Nice values range from -20 (highest priority, vruntime increases slowly) to +19 (lowest priority, vruntime increases quickly). A nice value of 0 is the default.
Real-Time Scheduling
Linux also supports real-time scheduling policies for latency-critical tasks:
- SCHED_FIFO -- real-time FCFS. The process runs until it blocks or a higher-priority real-time process arrives. No time quantum.
- SCHED_RR -- real-time round-robin among processes of the same priority.
Real-time processes always preempt normal (SCHED_OTHER/CFS) processes.
Real-Life: Why Your Desktop Stays Responsive
When you are compiling a large project in the background while editing text, the scheduler must balance both tasks:
Without MLFQ/CFS: A naive FCFS scheduler would let the compiler monopolize the CPU. Your text editor would freeze until compilation finishes -- terrible user experience.
With CFS: The compiler is CPU-bound. Its vruntime climbs rapidly because it uses every microsecond of its time slice. The text editor is I/O-bound -- it mostly sleeps waiting for your keystrokes, so its vruntime stays low. When you press a key, the editor wakes up with a very low vruntime, and CFS immediately preempts the compiler to let the editor process your keystroke. Result: the editor feels instant, and the compiler still gets most of the CPU overall.
With MLFQ: The compiler quickly gets demoted to a low-priority queue with large time quanta (good for throughput). The text editor stays in a high-priority queue because it frequently yields (I/O-bound). Keystrokes are handled almost immediately.
Nice values in practice:
nice -n 19 make -j8 # compile at lowest priority
nice -n -5 audio_app # audio processing at higher priority (needs root)
Real-time example: An audio mixing application uses SCHED_FIFO to ensure audio buffers are filled within 5 ms deadlines. If it were scheduled with CFS, a burst of other activity could cause the audio thread to miss its deadline, producing audible glitches (buffer underruns).