Chapter 10: CPU Scheduling — Who Gets the CPU First
Vol 3: Computer Core Expedition · Chapter 10
Metadata Card
| Attribute | Value |
|---|---|
| Keywords | FCFS, SJF, MLFQ, Round Robin, CFS, Real-time Scheduling |
Your Progress
"There are hundreds of processes ready to run, but only one CPU core (per core). Who gets to run, and for how long? This is the scheduler's problem."
Encounter 1: Scheduling Goals
- Fairness: Each process gets a fair share of CPU
- Efficiency: Maximize throughput
- Latency: Minimize response time
- Starvation-free: No process should wait indefinitely
Encounter 2: Classic Scheduling Algorithms
| Algorithm | Preemptive? | Pros | Cons |
|---|---|---|---|
| FCFS | No | Simple | Convoy effect |
| SJF | No | Optimal avg. wait | Starvation, needs future knowledge |
| Round Robin | Yes | Fair response time | High context switch overhead |
| MLFQ | Yes | Good for mixed workloads | Parameter tuning |
Encounter 3: Linux CFS (Completely Fair Scheduler)
CFS maintains a red-black tree of processes keyed by vruntime. It always picks the process with the smallest vruntime — the one that has received the least CPU time.
Verification Checklist
- [ ] Can explain FCFS, SJF, Round Robin scheduling
- [ ] Can explain MLFQ and its advantages
- [ ] Can describe Linux CFS's approach (vruntime, red-black tree)
→ Next Stop Preview
Chapter 11: Lock Implementation and Dynamic Memory