A computer usually has more runnable processes than CPU cores. The CPU scheduler decides which process runs next and for how long. Good CPU scheduling algorithms keep the system responsive, use the CPU efficiently and treat processes fairly.
This guide explains the key terms, the main algorithms with a worked example, and how modern operating systems like Linux actually schedule work.
Key terms
| Term | Meaning |
|---|---|
| Burst time | CPU time a process needs before it waits or ends |
| Arrival time | When the process becomes ready |
| Completion time | When the process finishes |
| Turnaround time | Completion time minus arrival time |
| Waiting time | Turnaround time minus burst time |
| Response time | Time from arrival until the process first runs |
| Context switch | Saving one process’s state and loading another’s |
| Dispatcher | The OS component that hands the CPU to the chosen process |
Preemptive vs non-preemptive
In non-preemptive scheduling, a process keeps the CPU until it finishes or waits for I/O. In preemptive scheduling, by contrast, the OS can interrupt a running process, for example when its time slice ends or a higher-priority process arrives. Modern desktop and server systems are preemptive, because it keeps them responsive.
Scheduling criteria
Schedulers try to balance several goals:
- High CPU utilisation: keep the CPU busy.
- High throughput: finish many processes per unit of time.
- Low turnaround and waiting time: finish each process quickly.
- Low response time: interactive users see quick reactions.
- Fairness: no process waits forever (starvation).
The main algorithms
1. First Come, First Served (FCFS)
The CPU serves processes in arrival order, like a queue at a counter. FCFS is simple, but one long process can delay many short ones. This is called the convoy effect.
2. Shortest Job First (SJF)
The scheduler picks the process with the shortest burst time. SJF gives the lowest average waiting time when all jobs arrive together. However, the OS must estimate burst times, and long jobs may starve.
3. Shortest Remaining Time First (SRTF)
This is the preemptive version of SJF. If a new process arrives with less remaining time than the running one, it takes over the CPU.
4. Priority scheduling
Each process has a priority, and the highest priority runs first. It can be preemptive or not. To avoid starvation, systems use ageing, which slowly raises the priority of waiting processes.
5. Round Robin (RR)
Each process gets a fixed time quantum, such as 10 milliseconds. When it expires, the process goes to the back of the queue. RR is fair and responsive. If the quantum is too small, though, context switches waste time; if it is too large, RR behaves like FCFS.
6. Multilevel queue and feedback queue
The OS keeps several queues, for example one for interactive processes and one for batch jobs, each with its own algorithm. In a multilevel feedback queue, processes move between queues based on behaviour. As a result, CPU-heavy processes sink to lower priority, while interactive ones stay responsive.
Worked example
Three processes arrive at time 0: P1 needs 8 ms, P2 needs 4 ms and P3 needs 2 ms.
| Algorithm | Order | Waiting times (P1, P2, P3) | Average waiting time |
|---|---|---|---|
| FCFS | P1, P2, P3 | 0, 8, 12 | 6.67 ms |
| SJF | P3, P2, P1 | 6, 2, 0 | 2.67 ms |
| Round Robin (quantum 2 ms) | P1, P2, P3, P1, P2, P1, P1 | 6, 6, 4 | 5.33 ms |
SJF wins on average waiting time. Round Robin, on the other hand, gives every process a turn early, which improves response time.
How Linux schedules today
Linux used the Completely Fair Scheduler (CFS) for many years. It tracks how much CPU time each task has received and runs the task that has had the least, weighted by its nice value. Since kernel 6.6, Linux uses the EEVDF scheduler, which keeps the fairness idea but also considers deadlines to improve latency. Real-time tasks use separate policies, such as SCHED_FIFO and SCHED_RR.
Related guides
Sources
Running Linux servers in production? Our Linux server hardening & security audit checks configuration, patching, SSH and logging. You can also use our free Linux server hardening checklist, or contact us.
