The Core Idea
Deciding Which Ready Process Runs Next
Whenever the CPU becomes available (a running process finishes, blocks on I/O, or is preempted), the OS scheduler must choose which of the currently Ready processes gets to run next. Different scheduling algorithms make this choice using different strategies, each optimizing for a different goal — minimizing average waiting time, maximizing fairness among processes, or ensuring interactive applications feel responsive.
No single scheduling algorithm is universally 'best' — each makes an explicit trade-off between competing goals like throughput (total work completed), fairness (no process waits forever), and responsiveness (interactive tasks get attention quickly), and the right choice depends on what kind of system and workload you're actually optimizing for.
💡 Memory Trick
Picture four different strategies for a single cashier serving a line of customers. FCFS is strictly first-come-first-served, no exceptions, even if the person at the front has 50 items and everyone behind them only has 1. SJF specifically calls up whoever has the FEWEST items next, minimizing the average wait for everyone overall. ROUND ROBIN gives each customer exactly 2 minutes of service, then makes them step aside and go to the back of the line if they're not done, cycling through everyone fairly in short bursts. PRIORITY SCHEDULING lets VIP customers cut to the front of the line ahead of everyone else, regardless of how long anyone has already been waiting.
The Core Algorithms
Different Strategies, Different Trade-offs
1
First-Come, First-Served (FCFS)
Processes are executed strictly in the order they arrive, with no preemption once a process starts running. Simple and fair in the sense of 'no cutting in line,' but a single long process at the front can force many short processes behind it to wait a long time — a problem known as the 'convoy effect.'
2
Shortest Job First (SJF)
Always selects the Ready process with the shortest estimated total execution time next. Mathematically minimizes average waiting time across all processes, but requires knowing (or accurately estimating) each process's total execution time in advance — often impractical in real systems, and can cause a long process to be indefinitely delayed ('starved') if a continuous stream of shorter jobs keeps arriving.
3
Round Robin
Each process gets a small, fixed slice of CPU time (a 'time quantum'), then is preempted and moved to the back of the Ready queue if it hasn't finished, giving the next process in line its turn. Provides good fairness and responsiveness for interactive systems, since no single process can monopolize the CPU for long, but choosing too small a time quantum wastes time on excessive context switching, while too large a quantum starts behaving like FCFS.
4
Priority Scheduling
Each process is assigned a priority value, and the scheduler always selects the highest-priority Ready process next. Effective for ensuring critical processes get attention quickly, but risks 'starvation' of low-priority processes if higher-priority processes keep arriving continuously — commonly mitigated with 'aging,' where a process's priority gradually increases the longer it waits, eventually guaranteeing it gets scheduled.
Choosing an Algorithm
Matching Scheduling Strategy to System Goals
Batch-processing systems (where jobs run without needing real-time interaction, like large overnight data processing) often favor SJF or similar throughput-maximizing strategies, since minimizing total average wait time across many queued jobs is the primary goal and no human is waiting for immediate interactive feedback.
Interactive systems (like a desktop OS or a phone) heavily favor Round Robin or priority-based approaches with aging, since responsiveness — the system feeling instantly responsive to user input, rather than making users wait behind other running processes — matters more than strictly minimizing total average wait time across all processes.
🖥️ Applied Scenario
A shared computing cluster runs both quick, interactive data-query jobs from analysts and occasional massive overnight batch-processing jobs, and users complain that their interactive queries sometimes get stuck behind a huge batch job.
1
You identify the cluster is currently using FCFS scheduling, meaning if a massive multi-hour batch job starts running just before a quick interactive query arrives, that query must wait the ENTIRE remaining duration of the batch job — the classic convoy effect.
2
You switch to a priority-based scheduling scheme, giving interactive queries a higher priority than batch jobs, so a newly arriving interactive query can preempt or otherwise cut ahead of an already-running lower-priority batch job.
3
To prevent the batch jobs from being starved entirely by a continuous stream of higher-priority interactive queries, you add aging, gradually increasing a batch job's priority the longer it waits, eventually guaranteeing it does get CPU time even during busy interactive periods.
4
Conclusion: the combination of priority scheduling (for responsiveness) and aging (to prevent starvation) directly addresses both the original convoy-effect complaint and the new risk of batch jobs never getting scheduled at all.
📌 Exam Application
Exam questions frequently present a set of processes with arrival times and execution durations, and ask you to calculate the resulting waiting time or completion order under a specified scheduling algorithm (FCFS, SJF, or Round Robin with a given time quantum). You may also be asked to explain a specific weakness of an algorithm (convoy effect for FCFS, starvation for SJF or Priority Scheduling) and propose a mitigation.
⚠️ Most Common Scheduling Algorithms Mistakes
The most common mistake is assuming SJF is always achievable in real systems — it requires knowing each process's total execution time in advance, which is frequently unknown or only estimable, making pure SJF more of a theoretical benchmark than a directly implementable real-world algorithm in many contexts. Another frequent error is picking a Round Robin time quantum without considering the trade-off — too small a quantum wastes significant time on context-switching overhead relative to actual work done, while too large a quantum causes Round Robin to behave almost identically to FCFS, losing its fairness and responsiveness benefits.
✓ Quick Self-Test
Given a set of processes with arrival times and execution durations, can you calculate their waiting times under FCFS, SJF, and Round Robin (with a specified time quantum)? Can you explain what 'starvation' means in a scheduling context, and describe how aging addresses it?
→
← All Operating Systems Lessons