CPU Scheduling
Overview
CPU scheduling determines which process in the ready queue is granted the CPU next. The scheduler's job is to balance competing performance goals — some of which conflict with each other. OS Course Notes — Weeks 3 & 5.md
See also: Processes, Threads, Exam Prep — Midterm, Key Concepts Glossary
Goals of Scheduling
⚠️ These goals can conflict with each other — for example, maximizing throughput may increase response time for individual processes. OS Course Notes — Weeks 3 & 5.md
Main Scheduling Algorithms
| Algorithm | Strategy | Key Advantage | Key Drawback |
|---|---|---|---|
| FCFS (First-Come, First-Served) | Serve in arrival order | Simple to implement | Convoy effect raises average waiting time |
| SJF (Shortest-Job-First) | Shortest CPU burst first | Optimal average waiting time | Hard to predict burst length; risk of starvation |
| Round Robin | Fixed time quantum, cycle through all | Good responsiveness for time-sharing | Small quantum → high context-switch overhead |
| Priority Scheduling | Higher priority served first | Flexible control over importance | Starvation; mitigated by aging |
OS Course Notes — Weeks 3 & 5.md
Algorithm Deep Dives
FCFS — First-Come, First-Served
Processes are served strictly in the order they arrive. The convoy effect occurs when a long-running job sits at the front of the queue, forcing all shorter jobs behind it to wait — significantly raising average waiting time. OS Course Notes — Weeks 3 & 5.md
SJF — Shortest-Job-First
Picks the process with the shortest next CPU burst. Mathematically optimal for minimizing average waiting time, but in practice the next burst length must be estimated (it cannot be known exactly). Risks starvation for long jobs if short jobs keep arriving. OS Course Notes — Weeks 3 & 5.md
Round Robin
Each process gets a time quantum; after the quantum expires the CPU moves to the next process in a circular fashion. Well-suited to time-sharing systems. The quantum size is critical: too small and context-switch overhead dominates; too large and it degenerates toward FCFS. OS Course Notes — Weeks 3 & 5.md
Priority Scheduling
Each process is assigned a priority; higher-priority processes run first. Long-waiting low-priority processes can starve indefinitely — the standard fix is aging: gradually increasing a process's priority the longer it waits. OS Course Notes — Weeks 3 & 5.md
Preemptive vs. Non-Preemptive Scheduling
- Preemptive: The OS can forcibly stop a running process and reassign the CPU (e.g., Round Robin, preemptive SJF). Offers better responsiveness.
- Non-preemptive: Once a process has the CPU, it keeps it until it voluntarily releases (e.g., finishes or requests I/O). Simpler but less responsive.
OS Course Notes — Weeks 3 & 5.md
Scheduling & Context Switching
Every time the scheduler switches the active process, a context switch occurs — the current process state is saved to its PCB and the next process's state is restored. Context switches are pure overhead (no useful work is done during them), so algorithms that switch frequently (e.g., Round Robin with a tiny quantum) pay a higher overhead cost. OS Course Notes — Weeks 3 & 5.md
Exam Tips
- Practice average waiting time calculations for each algorithm by drawing Gantt charts by hand — these appear frequently on the midterm. OS Course Notes — Weeks 3 & 5.md
- Know the trade-offs: FCFS simplicity vs. convoy effect; SJF optimality vs. starvation; RR responsiveness vs. overhead; Priority scheduling vs. aging.
- Understand when each algorithm is preemptive or non-preemptive.
See the Exam Prep — Midterm page for a full checklist and practice questions.