CPU Scheduling Algorithms | FCFS, SJF, SRTF, Round Robin & Priority
🧠 CPU Scheduling Algorithms | How the OS Chooses the Next Process
CPU scheduling is the process of selecting a waiting process from the ready queue and allocating the CPU to it. It is one of the most important tasks of the operating system because it directly affects performance, responsiveness, and resource utilization.
This guide covers the most common scheduling algorithms: FCFS, SJF, SRTF, Priority, Round Robin, and Multilevel Queue. The examples below explain each technique, compare their trade-offs, and show when to use each method.
You will also find helpful links to related system topics such as Process vs Thread, Operating Systems, and other networking and OS concepts in the same series.
📋 What Makes a Good Scheduling Algorithm?
The best scheduler depends on the system's goals. Common criteria include:
- CPU utilization – Keep the CPU busy as much as possible.
- Throughput – Maximize the number of processes completed per unit time.
- Turnaround time – Minimize total time from submission to completion.
- Waiting time – Minimize the amount of time a process spends waiting in the ready queue.
- Response time – Minimize the time from submission to the first response.
These criteria often compete with one another. A scheduler that minimizes waiting time may increase context switches. A scheduler that maximizes throughput may reduce fairness. Understanding the trade-offs is the key to choosing the right algorithm.
1. FCFS (First Come, First Served)
FCFS is the simplest CPU scheduling algorithm. Processes are executed in the order they arrive, just like customers in a queue. It is non-preemptive, meaning once the CPU is assigned to a process, it runs until completion.
This method is easy to implement, but it can suffer from poor average waiting time. If a long process arrives before shorter ones, the shorter processes must wait, causing the convoy effect.
FCFS is often used in batch systems where simplicity is more important than responsiveness.
2. SJF (Shortest Job First)
SJF chooses the process with the shortest burst time next. It is also non-preemptive, so once a process starts, it finishes before the next one begins.
The advantage of SJF is that it minimizes average waiting time. However, it requires knowledge of the burst time for each process in advance, which is not always available in practice.
SJF is most suitable for batch systems or environments where process durations can be estimated reasonably well.
3. SRTF (Shortest Remaining Time First)
SRTF is the preemptive version of SJF. When a new process arrives with a shorter remaining time than the current process, the OS interrupts the running process and switches to the new one.
This improves response time for short tasks and further reduces average turnaround time. But it also increases context switches because the OS may switch processes frequently.
SRTF works well in interactive or time-sensitive systems where short tasks should finish quickly.
4. Priority Scheduling
In priority scheduling, each process receives a priority. The CPU is given to the process with the highest priority. Priorities can be assigned by the user or calculated by the operating system.
Priority scheduling can be preemptive or non-preemptive. A preemptive version can interrupt a lower-priority process if a higher-priority one arrives.
The main disadvantage is starvation, where low-priority processes may wait indefinitely. To avoid this, many systems use aging, gradually increasing the priority of waiting processes.
5. Round Robin (RR)
Round Robin scheduling assigns the CPU to each process for a fixed time slice, called the time quantum, in cyclic order. If a process does not finish during its quantum, it returns to the ready queue.
This algorithm is ideal for time-sharing systems because it provides a predictable response time. Every process gets fair access to the CPU.
The main trade-off is that a small quantum increases context switching overhead, while a large quantum can reduce the responsiveness of interactive tasks.
6. Multilevel Queue Scheduling
Multilevel Queue scheduling divides processes into multiple queues based on priority, type, or other criteria. Each queue can use its own scheduling algorithm.
For example, a system might place interactive processes in one queue using Round Robin, batch processes in another queue using FCFS, and real-time processes in a high-priority queue using Priority scheduling.
The OS can also use a multilevel feedback queue, which dynamically moves processes between queues based on their behavior.
📊 Comparison Summary
| Algorithm | Preemptive | Average Waiting Time | Complexity | Best For |
|---|---|---|---|---|
| FCFS | No | High | Very Low | Batch systems |
| SJF | No | Low | Low | Batch jobs |
| SRTF | Yes | Very Low | Medium | Interactive systems |
| Priority | Depends | Medium | Medium | Real-time systems |
| Round Robin | Yes | Medium | Low | Time-sharing systems |
| Multilevel Queue | Depends | Varies | High | Mixed environments |
🧠 Why Scheduling Metrics Matter
In the infographic, key metrics like turnaround time and average waiting time explain how different schedulers behave. A good OS balances throughput, fairness, and responsiveness.
For example, servers that process many short requests need low waiting time, while batch jobs may prioritize high throughput and low overhead.
Interactive systems such as desktops and mobile devices often prefer algorithms like Round Robin or SRTF because they make the system feel responsive.
🧪 Practical Scheduling Challenges
There is no single scheduling algorithm best for all situations. The right choice depends on system goals, workload characteristics, and hardware capabilities.
Some common challenges include:
- Estimating process burst times accurately for SJF and SRTF.
- Preventing starvation in Priority scheduling.
- Choosing an appropriate time quantum for Round Robin.
- Balancing queue priorities in Multilevel Queue systems.
Real systems often use hybrid strategies, combining several algorithms to meet multiple objectives.
🧩 Scheduling in Real Operating Systems
Modern operating systems usually implement more advanced schedulers than the basic algorithms shown here. For example, Linux uses a completely fair scheduler (CFS) for general tasks and separate real-time policies for critical processes.
Even so, the basic ideas from FCFS, SJF, Round Robin, and Priority still form the foundation of modern scheduling logic.
Understanding these classic algorithms is essential for system designers, OS students, and developers working on performance-sensitive applications.
🔗 Related System Topics
To deepen your understanding, explore these related articles in the same series:
Process vs Thread | What is an Operating System? | How the Internet Works
📝 CPU Scheduling Quiz
❓ FAQ
What is the difference between FCFS and Round Robin?
FCFS serves jobs in arrival order without time slicing, while Round Robin gives each job a fixed time quantum.
Why does SRTF improve response time?
SRTF preempts the CPU for shorter jobs, allowing quick tasks to finish sooner.
How does aging help scheduling?
Aging increases the priority of waiting processes over time to prevent starvation.
