The CPU scheduler selects from the ready queue which process runs next. The goal: maximize throughput and fairness, minimize waiting time and response time.
Types of Schedulers
| Scheduler | What it does | Frequency |
|---|---|---|
| Long-term (Job) | Loads processes from disk into memory | Low — controls multiprogramming degree |
| Short-term (CPU) | Picks which ready process gets CPU next | Very high — every few ms |
| Medium-term | Swaps processes in/out of memory to disk | Medium — handles thrashing |
Scheduling Criteria
| Metric | Definition | Want |
|---|---|---|
| Throughput | Processes completed per unit time | High |
| Turnaround time | Total time from submission to completion | Low |
| Waiting time | Total time spent in ready queue | Low |
| Response time | Time from submission to first response | Low (critical for interactive systems) |
Algorithms Compared
| Algorithm | Preemptive? | Starvation? | Best for |
|---|---|---|---|
| FCFS | No | No | Simple batch systems |
| SJF | No | Yes (long jobs) | When burst times are predictable |
| SRTF | Yes | Yes | When burst times are predictable |
| Round Robin | Yes | No | Time-sharing, interactive systems |
| Priority | Optional | Yes (can fix with aging) | Systems with clear priority tiers |
FCFS (First-Come, First-Served)
Non-preemptive. Processes run in arrival order.
- Convoy effect: short processes wait behind a long CPU-bound process, wasting CPU when short processes could be running while the long one does I/O.
SJF (Shortest Job First) / SRTF
SJF is non-preemptive; SRTF is preemptive (Shortest Remaining Time First).
- Optimal in terms of average waiting time (if burst times are known)
- Starvation: long processes may never get CPU if short jobs keep arriving
Round Robin
Each process gets a fixed time quantum (typically 10-100ms).
- Quantum too large → degrades to FCFS
- Quantum too small → too many context switches, high overhead
Priority Scheduling
Higher priority processes run first.
- Starvation solved by aging — gradually increase priority of waiting processes
- Priority inversion: a low-priority process holds a lock needed by a high-priority one
Q: What are the three types of schedulers?
A: Long-term (loads processes into memory), short-term (allocates CPU), medium-term (swaps processes in/out of memory). The short-term scheduler runs the most frequently — every few milliseconds.
Q: What is the Convoy Effect?
A: In FCFS, a long CPU-bound process holds the CPU while short I/O-bound processes wait. The I/O devices sit idle, then get flooded when the long process finally finishes. It causes poor resource utilization.
Q: What is Starvation and how is it solved?
A: Starvation occurs when a process never gets CPU because higher-priority or shorter processes keep arriving. Solved with aging — gradually increase the priority of waiting processes.
Q: How does time quantum affect Round Robin performance?
A: Too large → behaves like FCFS, poor response time. Too small → excessive context switching overhead, reduced throughput. Ideal quantum is just larger than most CPU bursts (~80th percentile).
Q: What is priority inversion?
A: A high-priority process is blocked because a low-priority process holds a needed lock. The low-priority process can’t run because medium-priority processes preempt it. Solved with priority inheritance (temporarily boost the low-priority process’s priority).
Premium Content
Unlock CPU Scheduling Algorithms and all premium lessons with a subscription.
From ₹199.99/year — See plans