Introduction
Whenever more than one process is ready to run, the operating system's short-term scheduler must decide which one gets the CPU next. This decision happens constantly — potentially thousands of times per second — so it must be fast, but it also has a huge impact on system responsiveness, throughput, and fairness. CPU scheduling only matters for the 'ready' processes competing for a single resource (the CPU core); once a process blocks on I/O, it leaves the scheduler's immediate concern until it becomes ready again.
Cricket analogy: When multiple batters are padded up and ready, the team management must decide who walks out next -- this call happens every dismissal, so it must be quick, but it shapes the whole innings's run rate; a batter already resting in the pavilion after being out isn't part of that decision until their next turn.
Algorithm
Scheduling algorithms are compared using a standard set of metrics. Getting these formulas exact is essential, because every algorithm question in interviews reduces to computing them correctly from a Gantt chart.
Cricket analogy: Just as a batting average or strike rate must be computed exactly from the scorebook to compare players fairly, scheduling metrics must be computed exactly from a Gantt chart, since any sloppy arithmetic there throws off every comparison downstream.
/*
* Standard CPU scheduling metrics (per process i):
*
* Turnaround Time (TAT) = Completion Time - Arrival Time
* Waiting Time (WT) = Turnaround Time - Burst Time
* Response Time (RT) = Time of First CPU Burst - Arrival Time
*
* System-wide goals (often in tension with each other):
* - Maximize CPU utilization and throughput (jobs completed / unit time)
* - Minimize average waiting time and average turnaround time
* - Minimize response time (important for interactive systems)
* - Ensure fairness and avoid starvation
*/
typedef struct {
int pid;
int arrival_time;
int burst_time;
int completion_time;
int waiting_time;
int turnaround_time;
} process_t;
void compute_metrics(process_t *p) {
p->turnaround_time = p->completion_time - p->arrival_time;
p->waiting_time = p->turnaround_time - p->burst_time;
}Explanation
Scheduling algorithms fall into two broad camps. Non-preemptive algorithms (FCFS, non-preemptive SJF, non-preemptive Priority) let a running process keep the CPU until it finishes or voluntarily blocks; they are simple but can leave short or urgent jobs waiting a long time behind a long one. Preemptive algorithms (SRTF, Round Robin, preemptive Priority) can interrupt a running process — on a timer tick, or when a more important process arrives — trading some overhead (context switches) for better responsiveness and fairness. The right choice depends on the workload: batch systems favor throughput-oriented non-preemptive schemes, while interactive and time-sharing systems favor preemptive, low-response-time schemes like Round Robin.
Cricket analogy: A non-preemptive declaration lets the batting side keep batting until they choose to declare or are all out (like FCFS or non-preemptive SJF), which is simple but can leave a chasing team's urgent run-chase waiting; a preemptive rain-rule or DRS review can interrupt play mid-over (like SRTF or preemptive Priority), trading some delay for fairer outcomes -- Test cricket favors the patient non-preemptive approach, while T20 favors fast, preemptive tactical shifts.
Example
/*
* Two processes, FCFS order, to illustrate the metric formulas.
*
* Process | Arrival | Burst
* P1 | 0 | 4
* P2 | 1 | 3
*
* Gantt chart:
* |----P1----|----P2----|
* 0 4 7
*/
Output
P1 runs 0-4 and P2 runs 4-7. Completion times: P1=4, P2=7. Turnaround times: P1 = 4-0 = 4, P2 = 7-1 = 6, giving an average turnaround of (4+6)/2 = 5.0. Waiting times: P1 = 4-4 = 0, P2 = 6-3 = 3, giving an average waiting time of (0+3)/2 = 1.5. Since neither algorithm here is preemptive, response time equals waiting-until-first-run, i.e. P1=0 and P2=3, average 1.5 — response time and waiting time only diverge once a process can be preempted and resumed multiple times.
Cricket analogy: P1 bats overs 0-4 and P2 bats overs 4-7 in a non-preemptive net session: P1 finishes at over 4 with zero extra wait since they went first, while P2 finishes at over 7 having waited 3 overs past their arrival, giving an average turnaround of 5.0 overs and average wait of 1.5, with response time matching wait time exactly since nobody's turn was interrupted.
Key Takeaways
- Turnaround Time = Completion - Arrival; Waiting Time = Turnaround - Burst; Response Time = First Run - Arrival.
- Non-preemptive algorithms never interrupt a running process; preemptive algorithms can, at the cost of extra context switches.
- No single algorithm optimizes every metric at once — batch throughput and interactive responsiveness pull in opposite directions.
- The scheduler only chooses among 'ready' processes; blocked (I/O-waiting) processes are outside its control until they wake up.
- Always derive a Gantt chart first, then compute completion/turnaround/waiting times column by column to avoid arithmetic mistakes.
Practice what you learned
1. What is the correct formula for Waiting Time?
2. Which pair of algorithms is inherently preemptive?
3. In the FCFS example (P1: arrival 0, burst 4; P2: arrival 1, burst 3), what is the average turnaround time?
4. Which system type most benefits from a preemptive, low-response-time scheduling policy?
5. What does the short-term scheduler operate on?
Was this page helpful?
You May Also Like
FCFS and SJF Scheduling
First-Come-First-Served and Shortest-Job-First scheduling, worked through Gantt charts with exact waiting/turnaround-time math.
Priority and Round Robin Scheduling
Priority scheduling with starvation and aging, and Round Robin with a fully worked quantum-based Gantt chart.
Introduction to Process Scheduling
Learn why the OS schedules processes, the queues involved, and the basic goals of a scheduler.