CPU Scheduling
The scheduler picks which ready process gets the CPU. Algorithms trade off waiting time, response time, throughput and fairness.
Cheat sheet
- ▸Turnaround Time = Completion − Arrival. Waiting Time = Turnaround − Burst.
- ▸FCFS: simple, non-preemptive, suffers convoy effect.
- ▸SJF: optimal average waiting time but needs burst prediction; can starve long jobs.
- ▸SRTF: preemptive SJF.
- ▸Round Robin: time quantum q; good response time; q too large → FCFS, too small → overhead.
- ▸Priority: starvation fixed by aging (raising priority over time).
Scheduling algorithms
| Algorithm | Preemptive? | Starvation? | Best for |
|---|---|---|---|
| FCFS | No | No | Batch, simplicity |
| SJF | No | Yes | Min avg waiting time |
| SRTF | Yes | Yes | Short interactive jobs |
| Round Robin | Yes | No | Time-sharing systems |
| Priority | Either | Yes (fix: aging) | Real-time importance |
| Multilevel Queue | Yes | Possible | Mixed workloads |
Visual
Round Robin, q=2 P1(5) P2(3) P3(1) | P1 | P2 | P3 | P1 | P2 | P1 | 0 2 4 5 7 8 9
Top 10 campus interview questions
Quick quiz
1. Which algorithm gives minimum average waiting time?
2. Convoy effect occurs in:
3. Aging is used to prevent:
4. P1 burst 6, P2 burst 3, both arrive at 0, FCFS order P1,P2. Avg waiting time?
5. Round Robin with a huge quantum behaves like: