How Does the OS Choose What Runs Next?
You've learned that processes move between ready, running, and waiting states. But who decides which process gets the CPU when multiple processes are waiting? That's the job of the process scheduler — the component of the OS that allocates CPU time to processes.
The scheduler is like an air traffic controller. With hundreds of planes (processes) in the sky, it needs to decide which one lands (gets the CPU) next, which one holds in a pattern (waits), and which one takes off (becomes ready) again. One wrong decision and you've got chaos.
Types of Schedulers
There are three levels of scheduling in an operating system:
- Long-Term Scheduler (Job Scheduler) — Decides which processes from the job pool get admitted into memory. It controls the degree of multiprogramming — how many processes are in the system at once. It runs infrequently (seconds or minutes).
- Short-Term Scheduler (CPU Scheduler) — Decides which ready process gets the CPU next. This runs very frequently (milliseconds) and is the most critical scheduler for performance.
- Medium-Term Scheduler — Removes processes from memory to reduce the load (swapping), then brings them back later. It helps manage the degree of multiprogramming dynamically.
Scheduling Goals
The scheduler tries to optimize several things simultaneously:
- CPU Utilization — Keep the CPU as busy as possible. An idle CPU is wasted potential.
- Throughput — Maximize the number of processes completed per unit time.
- Turnaround Time — Minimize the total time from process submission to completion.
- Waiting Time — Minimize the time processes spend waiting in the ready queue.
- Response Time — Minimize the time between submitting a request and getting the first response (important for interactive systems).
The catch is that these goals often conflict. Optimizing for throughput might increase waiting time. Optimizing for response time might reduce overall throughput. The scheduler must balance these trade-offs based on the system's needs.
Preemptive vs. Non-Preemptive Scheduling
An important distinction in scheduling is whether the OS can force a process off the CPU:
- Non-Preemptive — Once a process gets the CPU, it keeps it until it finishes or voluntarily yields (blocks for I/O). Simple but dangerous — a long-running process can hog the CPU and starve others.
- Preemptive — The OS can forcibly remove a process from the CPU (after its time slice expires or a higher-priority process arrives). Most modern OSes use preemptive scheduling because it ensures fairness and responsiveness.
Preemptive scheduling introduces complexity though — what happens if a process is in the middle of updating shared data when it's interrupted? This leads to race conditions and the need for synchronization mechanisms, which we'll cover later.