CPU Scheduling Algorithms Explained

CPU scheduling algorithms decide how a single processor core is shared among many ready programs. A modern computer keeps dozens or hundreds of processes alive at once, but each core can execute only one thread at a time. The scheduler picks the next one, and its choice shapes how fast programs finish, how responsive the desktop feels and whether any job is left waiting forever.

Why CPU scheduling is needed

Most programs alternate between CPU bursts (computing) and I/O bursts (waiting for disk, network or user input). Silberschatz describes this as the CPU and I/O burst cycle. While one process waits for I/O, the CPU would sit idle unless another ready process is given the core. Scheduling keeps the CPU busy and is the basis of multiprogramming.

Processes waiting for the CPU sit in the ready queue, which is usually a set of linked lists of process control blocks (see process vs thread for what a PCB holds). The short term scheduler picks one, and the dispatcher performs the context switch, switches to user mode and jumps to the right instruction. The time this takes is the dispatch latency, pure overhead that every switch adds.

A scheduling decision can occur when a process:

1. Switches from running to waiting (for example, an I/O request).
2. Switches from running to ready (for example, a timer interrupt).
3. Switches from waiting to ready (I/O completes).
4. Terminates.

If scheduling happens only in cases 1 and 4, the scheme is non-preemptive. If it can also happen in cases 2 and 3, it is preemptive. Nearly all modern desktop and server operating systems, including Windows, macOS and Linux, use preemptive scheduling.

Scheduling criteria

Batch systems care most about throughput and turnaround. Interactive systems care about response time. Real time systems care about meeting deadlines. No algorithm wins on all criteria.

Main CPU scheduling algorithms

First come first served (FCFS)

The process that requests the CPU first gets it first, using a simple FIFO queue like the one in stack vs queue. FCFS is non-preemptive and easy to implement, but its average waiting time is often long. A long CPU bound job at the front makes many short jobs wait behind it, which Silberschatz calls the convoy effect.

Shortest job first (SJF)

The scheduler picks the process with the shortest next CPU burst. For a given set of processes, SJF is provably optimal: it gives the minimum average waiting time, because moving a short job ahead of a long one reduces the short job’s wait by more than it increases the long one’s. The difficulty is that the next burst length is not known, so systems estimate it with an exponential average of previous bursts:

$$\tau_{n+1} = \alpha \, t_n + (1 - \alpha)\, \tau_n$$

where t_n is the length of the latest burst, τ_n is the previous prediction and α is between 0 and 1 (often 0.5).

Shortest remaining time first (SRTF)

This is the preemptive version of SJF. When a new process arrives with a burst shorter than what is left of the running process, the running one is preempted. It further reduces average waiting time but causes more context switches.

Priority scheduling

Each process has a priority number and the highest priority ready process runs. SJF is a special case where priority is the inverse of the predicted burst. Priority scheduling can be preemptive or not. Its main risk is starvation (indefinite blocking) of low priority processes, solved by aging, which slowly raises the priority of processes that have waited a long time.

Round robin (RR)

Round robin is FCFS with preemption. Each process gets a small unit of CPU time called a time quantum or time slice, typically 10 to 100 ms according to Silberschatz. When the quantum expires, a timer interrupt moves the process to the tail of the ready queue. With n ready processes and quantum q, no process waits more than (n − 1) × q before its next turn, which gives good response time.

The quantum size matters. A very large quantum makes RR behave like FCFS. A very small one wastes time on context switches. Silberschatz gives the rule of thumb that about 80% of CPU bursts should be shorter than the quantum.

Multilevel queue and multilevel feedback queue

A multilevel queue splits the ready queue into separate queues, for example real time, system, interactive and batch, each with its own algorithm and a fixed priority between queues. A multilevel feedback queue (MLFQ) lets processes move between queues: a process that uses its whole quantum drops to a lower priority queue, while one that gives up the CPU early for I/O stays high. OSTEP explains that MLFQ learns from observed behaviour, favouring short interactive jobs without knowing burst lengths in advance, and uses a periodic priority boost to prevent starvation.

Worked example with Gantt charts

Download diagram (WebP)

This matches the textbook result that SJF minimizes average waiting time, and shows why round robin is still preferred for interactive work: its strength is response time, not turnaround.

Key formulas for CPU scheduling algorithms

$$\text{TAT} = t_\text{completion} - t_\text{arrival}, \qquad \text{WT} = \text{TAT} - t_\text{burst}$$

CPU scheduling algorithms compared

Scheduling in real operating systems

Real kernels schedule threads rather than processes and must also handle multiple cores, keeping a thread on the same core where possible (processor affinity) and balancing load between cores. Tanenbaum describes Windows as using 32 priority levels with round robin inside each level and temporary priority boosts for threads that finish I/O.

Linux used the Completely Fair Scheduler (CFS) from kernel 2.6.23. CFS tracks each task’s virtual runtime and runs the task that has received the least, keeping tasks in a red black tree, so selection cost grows with the logarithm of the number of tasks (see Big O notation). Since kernel 6.6 the default fair class uses EEVDF (Earliest Eligible Virtual Deadline First), which keeps the fairness goal but chooses among eligible tasks by virtual deadline to improve latency. Embedded and real time systems, often running on the chips described in microcontroller vs microprocessor, use fixed priority preemptive scheduling so that deadlines can be analysed.

CPU scheduling algorithms interview and viva questions

1. Why is SJF called optimal? For a given set of processes it gives the minimum average waiting time, because running shorter jobs first reduces their wait by more than it delays longer jobs.
2. What is the convoy effect? In FCFS, a long CPU bound process at the front of the queue makes many short processes wait behind it, lowering CPU and device utilization.
3. How does the time quantum affect round robin? A very large quantum turns RR into FCFS, while a very small one spends too much time on context switches; a common guideline is that about 80% of CPU bursts should be shorter than the quantum.
4. What is the difference between turnaround time and response time? Turnaround runs from arrival to completion, while response time runs from arrival to the first time the process gets the CPU.
5. How does aging prevent starvation? It gradually raises the priority of processes that have waited a long time, so even low priority processes eventually run.

Related reading

• Process vs thread
• Stack vs queue
• Big O notation
• Von Neumann vs Harvard architecture