CPU scheduling: who runs next?

Your laptop is running hundreds of threads right now: the browser, a music player, background updates, this page. It has perhaps eight cores. Each core can run only one thread at a time, so something has to decide, many times a second, who gets it next. That something is the scheduler.

The choice matters. Make a short job wait behind a long one and it feels sluggish. Hand out turns too eagerly and the core spends its time switching instead of working. Every policy here is a different answer to one question: who should run now?

process and burst

A job that needs the CPU. Its burst is how many units of CPU time it needs before it is done (or stops to wait for something else).

ready queue

The processes that have arrived and are waiting for the CPU. The scheduler picks from here.

preemption

Taking the CPU away from a running process before it finishes, because the rule says someone else should run.

quantum

Round robin’s turn length: a process runs for at most this long, then goes to the back of the queue.

waiting, turnaround, response

Turnaround is finish − arrival. Waiting is the part of that spent in the queue: turnaround − burst. Response is how long until it first runs.

First come, first served is the obvious rule: run jobs in the order they arrive, each to the end. Watch what happens when the first job is a long one. On the Gantt chart, each row is a process: its pale bars are time spent waiting, its solid bars are time on the CPU.

Now the same four jobs under shortest remaining time first (SRTF): whenever a job arrives with less work left than the running one, it takes over the CPU.

The player stops at every decision and asks which process gets the CPU. Use the rule, SRTF: the least work left wins, and a tie never takes the CPU away from the process already running.

Shortest-first is unfair to long jobs, and it needs to know the future. Round robin needs neither: processes take turns of at most one quantum, and a process whose turn is up goes to the back of the queue. Try the same three jobs with a quantum of 1 and of 4, and compare the context switches and when each job first runs.

A quantum longer than every burst means no job is ever cut short: round robin becomes FCFS. The art is a quantum long enough that switching is a small cost, short enough that nobody waits long for a turn.

• A scheduler picks which ready process runs, whenever the CPU frees up or (if it preempts) a better candidate arrives.
• Turnaround = finish − arrival, waiting = turnaround − burst, response = first run − arrival.
• FCFS is simple but forms convoys behind long jobs. SJF/SRTF minimise average waiting but need predicted burst lengths. Round robin keeps response times short at the cost of context switches; with a huge quantum it becomes FCFS. Priority can starve low priorities unless waiting jobs age upwards.
• Heaps meet schedulers here: SRTF and priority scheduling keep the ready queue in a priority queue keyed by remaining time or priority, so picking the next process costs $O(\log n)$ instead of a scan.