CPU Scheduling¶
CPU scheduling decides which process runs next. Key algorithms: FCFS (first come, first served — simple, convoy effect), SJF (shortest job first — optimal average wait, starvation risk), Round Robin (time slices — fair, good for interactive), Priority (highest priority first — starvation solved with aging), Multilevel Queue. Metrics: throughput, turnaround time, waiting time, response time.
Key Concepts¶
Deep Dive: Scheduling Algorithms
| Algorithm | Preemptive? | Pros | Cons |
|---|---|---|---|
| FCFS | No | Simple | Convoy effect |
| SJF | Both | Optimal avg wait time | Starvation, need burst estimate |
| Round Robin | Yes | Fair, responsive | Higher context switching |
| Priority | Both | Important tasks first | Starvation (use aging) |
| Multilevel Queue | Yes | Different queues for different needs | Complex |
Deep Dive: Key Metrics
- Turnaround time = completion time - arrival time
- Waiting time = turnaround time - burst time
- Response time = first run time - arrival time
- Throughput = processes completed per unit time
Deep Dive: Preemptive vs Non-Preemptive
- Non-preemptive: Process runs until it finishes or blocks on I/O
- Preemptive: OS can interrupt a running process (timer interrupt)
- Modern OS uses preemptive scheduling (Linux, Windows)
Common Interview Questions
- Compare FCFS, SJF, and Round Robin.
- What is the convoy effect?
- What is starvation? How do you prevent it?
- What is preemptive vs non-preemptive scheduling?
- What scheduling algorithm does Linux use?