Appearance
2.3.2 — Scheduling Algorithms, Worked
Four jobs reach the photo-upload service's machine within three milliseconds of each other. Job A is a big batch of thumbnails that needs 8 ms of CPU. Job B needs 4 ms. Job C needs 9 ms. Job D needs 5 ms. There is one CPU core. In what order should they run?
It sounds like a small question. It is not. Run them in one order, and the average job waits 8.75 ms. Run them in another, and it waits 6.5 ms. Run them a third way, and every job starts within 2 ms on average, but they finish later. Each answer is right for some kind of machine and wrong for another. This page works through the classic answers with real numbers, so you can see exactly what each one buys and what it costs.
The part of the kernel that answers this question is the scheduler. Every time a core becomes free, or a time limit runs out, the scheduler picks which ready thread runs next (2.2.1 showed the ready state; 2.3.1 showed that the kernel schedules threads). It runs thousands of times a second, so it must decide quickly.
1. What "good" means: five measurements
Before comparing schedulers, we need to agree how to score them. Every job has an arrival time (when it became ready) and a burst time (how much CPU it needs). From the schedule, we can measure:
- Completion time: when the job finished.
- Turnaround time: how long the job spent in the system from arrival to finish. Turnaround = completion − arrival.
- Waiting time: how long the job sat ready but not running. Waiting = turnaround − burst.
- Response time: how long until the job first got the CPU at all. Response = first run − arrival.
- Throughput: how many jobs finish per second.
These pull against each other, and that is the whole difficulty.
- A batch machine, crunching overnight reports, wants high throughput and low turnaround. It does not care if one job waits, as long as the total work gets done fast.
- A laptop or a web server wants low response time. When you press a key, something must react at once, even if that makes the total work a little slower.
- A shared machine wants fairness: no job should be made to wait forever.
No single schedule wins on all three. Every algorithm below is a choice of which to favour.
2. When may the scheduler take the CPU away?
There is one decision that comes before any algorithm.
- With cooperative scheduling, a job keeps the CPU until it gives it up by itself, either by finishing, by waiting for input, or by explicitly yielding. It is simple. But one buggy job stuck in a loop never gives up the CPU, and the whole machine freezes. Windows 3.1 and the classic Mac OS worked this way, and one hung program really could lock the whole computer.
- With preemptive scheduling, the kernel can take the CPU away from a running job. It uses the timer interrupt from 2.1.1: a hardware clock that interrupts the CPU many times a second, whatever the job is doing, and hands control to the kernel. The kernel can then decide to run someone else. The longest a job may run before it can be interrupted is its time slice, also called a quantum, usually a few milliseconds.
Every general-purpose operating system today is preemptive. Note how the pieces connect: the timer interrupt is the trigger, the scheduler makes the decision, and the context switch from 2.2.1 carries it out.
One idea from the cooperative world survives everywhere, though. Inside one Node program, your JavaScript callbacks are scheduled cooperatively by the event loop. A callback that loops forever freezes every other callback, because nothing preempts it (3.8.2). The kernel still preempts Node's thread to run other programs, but inside Node, it is cooperative.
3. A simulator for our four jobs
To compare the algorithms honestly, here is a small simulator. It steps through time one millisecond at a time. At each step it lets new jobs arrive, decides whether the running job must give up the CPU, picks the next job, and runs it for 1 ms.
ts
// scheduler-sim.ts — run four jobs through four scheduling policies, one millisecond at a time
type Job = { name: string; arrival: number; burst: number };
type Policy = "fcfs" | "sjf" | "srtf" | "rr";
const jobs: Job[] = [
{ name: "A", arrival: 0, burst: 8 },
{ name: "B", arrival: 1, burst: 4 },
{ name: "C", arrival: 2, burst: 9 },
{ name: "D", arrival: 3, burst: 5 },
];
function simulate(policy: Policy, slice = 2) {
const left = new Map(jobs.map((j) => [j.name, j.burst])); // (1) work still to do
const firstRun = new Map<string, number>();
const finish = new Map<string, number>();
const ready: string[] = []; // (2) the ready queue
let running: string | null = null;
let used = 0; // ms used in this turn
let timeline = "";
for (let t = 0; finish.size < jobs.length; t++) {
for (const j of jobs) if (j.arrival === t) ready.push(j.name); // (3) arrivals join
if (running) { // (4) should it give up the CPU?
const shorter = ready.some((n) => left.get(n)! < left.get(running!)!);
if ((policy === "rr" && used === slice) || (policy === "srtf" && shorter)) {
ready.push(running);
running = null;
}
}
if (!running && ready.length) { // (5) pick the next job
let i = 0;
if (policy === "sjf" || policy === "srtf")
i = ready.reduce((best, n, k) => (left.get(n)! < left.get(ready[best])! ? k : best), 0);
running = ready.splice(i, 1)[0];
used = 0;
if (!firstRun.has(running)) firstRun.set(running, t);
}
timeline += running ?? "."; // (6) run for 1 ms
if (running) {
left.set(running, left.get(running)! - 1);
used++;
if (left.get(running) === 0) { finish.set(running, t + 1); running = null; }
}
}
let wait = 0, resp = 0;
const rows = jobs.map((j) => {
const turnaround = finish.get(j.name)! - j.arrival; // (7)
const waiting = turnaround - j.burst; // (8)
const response = firstRun.get(j.name)! - j.arrival; // (9)
wait += waiting; resp += response;
return `${j.name}: done at ${finish.get(j.name)}, waited ${waiting}, first ran after ${response}`;
});
console.log(`\n${policy.toUpperCase()} ${timeline}`);
rows.forEach((r) => console.log(" " + r));
console.log(` average waiting ${(wait / jobs.length).toFixed(2)} ms, average response ${(resp / jobs.length).toFixed(2)} ms`);
}
simulate("fcfs");
simulate("sjf");
simulate("srtf");
simulate("rr", 2);Walk through the marked lines:
(1)For each job, we track how many milliseconds of work it still needs.(2)The ready queue is the list of jobs that could run but are not running. It is an ordinary array, and its order matters.(3)At each millisecond, any job whose arrival time has come joins the back of the queue.(4)This is where preemption happens. Under round-robin, a job that has used its whole slice goes to the back of the queue. Under SRTF, a job is pushed back if a waiting job needs less remaining work. The other two policies never reach the innerif, so they never preempt.(5)If the CPU is free, the policy picks the next job. FCFS and round-robin take the front of the queue (i = 0). SJF and SRTF take the job with the least work left. We also record when each job first ran.(6)The chosen job runs for one millisecond, and its letter is added to the timeline. When its remaining work hits 0, we record its finish time.(7),(8),(9)The three measurements from section 1, computed exactly as their definitions say.
The program prints four timelines. Each letter is one millisecond of that job running.
text
FCFS AAAAAAAABBBBCCCCCCCCCDDDDD
average waiting 8.75 ms, average response 8.75 ms
SJF AAAAAAAABBBBDDDDDCCCCCCCCC
average waiting 7.75 ms, average response 7.75 ms
SRTF ABBBBDDDDDAAAAAAACCCCCCCCC
average waiting 6.50 ms, average response 4.25 ms
RR AABBCCAADDBBCCAADDCCAADCCC
average waiting 12.75 ms, average response 2.00 msHere are the same four timelines as a picture. Each coloured bar is one job running.
One thing in the picture surprises people. Every schedule finishes at exactly 26 ms, because the total work is 8 + 4 + 9 + 5 = 26 ms, and the CPU is never idle. The scheduler cannot make the work smaller. It only decides who waits. Now take the algorithms one at a time.
4. First come, first served
First come, first served, or FCFS, runs jobs in the order they arrive, each one to completion. It is the line at a shop.
Work out the waiting times by hand from the first row of the figure:
| Job | Arrival | Burst | Done at | Turnaround | Waiting |
|---|---|---|---|---|---|
| A | 0 | 8 | 8 | 8 | 0 |
| B | 1 | 4 | 12 | 11 | 7 |
| C | 2 | 9 | 21 | 19 | 10 |
| D | 3 | 5 | 26 | 23 | 18 |
Take B as an example. It finished at 12 and arrived at 1, so its turnaround is 12 − 1 = 11. It needed 4 ms of work, so it spent 11 − 4 = 7 ms waiting. The average waiting time is (0 + 7 + 10 + 18) / 4 = 8.75 ms.
FCFS is simple and perfectly fair in one sense: nobody jumps the line. Its weakness has a name, the convoy effect. If a long job arrives first, every short job behind it waits for the whole long job. It is one shopper with a full trolley at the only open till, while ten people with one item each queue behind them. Here, B needed only 4 ms but waited 7 ms behind A.
5. Shortest job first
The convoy effect suggests a fix: let the short jobs go first. Shortest job first, or SJF, always picks the ready job with the smallest burst time, and runs it to completion.
In our example, A arrives alone at time 0, so it starts. SJF does not interrupt a running job, so A runs to 8. At time 8, B (4), C (9) and D (5) are all ready. SJF takes the shortest, B. At 12, D (5) is shorter than C (9), so D goes next. C goes last. The average waiting time drops to 7.75 ms.
It can be proved that, for jobs that are all ready at the same moment, shortest-first gives the lowest possible average waiting time. The reason is simple: a job's burst is added to the waiting time of every job behind it. Put the short ones first, and you add the small numbers many times and the big numbers few times.
SJF has two serious problems.
- The scheduler cannot know the future. A real operating system does not know how long a thread will run before it next waits. Real schedulers estimate it from the thread's recent behaviour. A thread that kept using its CPU in short bursts is assumed to keep doing so.
- A long job can starve. If short jobs keep arriving, a long job may never be picked. Starvation means a job that is ready to run never gets the CPU.
6. Shortest remaining time first
SJF still let A run its full 8 ms, even when shorter jobs arrived at times 1, 2 and 3. The preemptive version fixes that. Shortest remaining time first, or SRTF, re-checks at every moment. If a newly arrived job needs less work than the remaining work of the running job, the running job is pushed back and the new one runs.
Follow the third row of the figure:
- At 0, A starts.
- At 1, B arrives needing 4. A still needs 7. 4 is less than 7, so A is preempted and B runs.
- At 2 and 3, C (9) and D (5) arrive. B's remaining work is smaller than both, so B continues until it finishes at 5.
- At 5, the ready jobs need A 7, C 9 and D 5. D is shortest and runs until 10.
- At 10, A (7) beats C (9). A runs until 17. Then C runs until 26.
The average wait falls to 6.50 ms, the best of all four, and the average response time falls to 4.25 ms. It is the best possible at minimising waiting. It shares SJF's problems, more so: it needs to know remaining work, and C, the longest job, waited 15 ms. With a steady stream of short arrivals, C could wait forever.
7. Round-robin
The algorithms so far chase low waiting. Round-robin chases low response. It gives each ready job one time slice, here 2 ms, in turn. A job that uses up its slice goes to the back of the queue. The name comes from a round-robin petition, where signatures were written in a circle so nobody's name came first.
Look at the last row of the figure. Every job gets the CPU within a few milliseconds of arriving: A at 0, B at 2, C at 4, D at 8. The average response time is just 2.00 ms, far better than any other algorithm. But the average waiting time is the worst, 12.75 ms, because every job keeps being sent to the back of the line, so all of them finish late.
That trade is exactly what an interactive machine wants. When you type in an editor while a build runs, you care that your keystroke appears now. You do not care that the build finishes a few milliseconds later.
The size of the slice is the whole game
- A slice that is too long turns round-robin back into FCFS. If the slice is longer than every job, each job simply runs to completion in arrival order.
- A slice that is too short wastes the machine on switching. Every slice ends with a context switch, which costs a few microseconds plus cold caches (2.2.1). With a 0.01 ms slice, a large fraction of the CPU would go on switching.
Real systems use slices of a few milliseconds. That is long compared with a context switch, so switching costs a small fraction of the time. And it is short compared with human reaction time, which is around 100 ms, so the machine still feels instant.
8. Priority, starvation and aging
Some work matters more than other work. A video call should beat a background backup. Priority scheduling gives each job a number, and always runs the highest-priority ready job. Within one priority level, it might use round-robin.
The danger is starvation again. If high-priority jobs keep arriving, low-priority jobs may never run. The standard fix is aging. The longer a job waits, the more its priority is raised, a little at a time. Eventually even the lowest job becomes the highest and gets to run. It is the same idea as a queue at a government office that lets someone through if they have been waiting for hours, whatever their place in line.
There is a nastier failure called priority inversion, where a high-priority thread ends up waiting behind a low-priority one. It needs locks to happen, so it lives in 2.3.3.
9. The multi-level feedback queue: learning from behaviour
Here is the real problem every desktop scheduler faces. It wants to favour interactive threads, like the editor waiting for your keystrokes. It wants to push down CPU-heavy threads, like a compiler. But it does not know which thread is which. Nobody labels them.
The multi-level feedback queue, or MLFQ, solves this by watching. Fernando Corbató described the idea for the CTSS time-sharing system in 1962, and he won the Turing Award in 1990 for his work on time-sharing. It keeps several queues, from high priority to low, and follows a few rules:
- Always run a job from the highest non-empty queue. Within a queue, use round-robin.
- A new job starts in the top queue.
- If a job uses its whole time slice, it moves down one queue. It behaved like a CPU-heavy job.
- If a job gives up the CPU before its slice ends, usually because it is waiting for input, it stays where it is. It behaved like an interactive job.
- Every so often, move every job back to the top queue. This is aging, and it stops the low queues from starving forever. It also gives a job whose behaviour changed, such as a program that finished loading and became interactive, a fresh chance.
Rules 3 and 4 do the magic. The editor waits for keystrokes almost all the time, so it never uses a full slice, so it stays near the top and responds instantly. The compiler always uses its full slice, so it sinks to the bottom, where it runs whenever nothing more urgent wants the CPU. The scheduler learned which job was which, just by watching how they used their time. Variations of this idea ran inside Windows NT, macOS and many Unix systems for decades.
There is one known weakness. A crafty program could sleep for a moment just before its slice ends, every time, so it always looks interactive and stays at the top. Real MLFQ versions close this hole by counting a job's total CPU use at a level, not just whether it gave up the last slice early.
10. What real systems use
| Algorithm | Waiting | Response | Starves? | Used in |
|---|---|---|---|---|
| FCFS | poor | poor | no | simple job queues |
| SJF / SRTF | best | good | yes | batch systems, as estimates |
| Round-robin | poor | best | no | inside other schedulers |
| Priority + aging | varies | good for high | not with aging | almost everywhere |
| MLFQ | good | good | not with resets | Windows, older macOS and Unix |
No real general-purpose kernel uses any of these pure forms. They are building blocks. Linux combines a fairness rule with priority weights, time slices and separate classes for real-time work. That is the subject of the next page, 2.3.3.
You will also see these exact algorithms outside the kernel. A web server deciding which waiting request to serve, a database deciding which query to run, a message queue deciding which consumer gets the next message, and a printer deciding which document to print, all face the same choice between waiting, response and fairness.
What the interviewer will push on
"Compare FCFS, SJF and round-robin." They are checking whether you can say what each optimises, not just how each works. FCFS is simple but suffers the convoy effect. SJF minimises average waiting but needs future knowledge and can starve long jobs. Round-robin minimises response time at the cost of average waiting. The tell is giving numbers from a small example, like this page's 8.75, 7.75 and 12.75 ms.
"Work out the average waiting time for this set of jobs." This is a common written question. Draw the timeline first, then use turnaround = completion − arrival and waiting = turnaround − burst. The common mistake is forgetting to subtract the arrival time.
"What happens if the round-robin time slice is too big or too small?" Too big becomes FCFS. Too small wastes the CPU on context switches. The strong answer gives the reason real slices are milliseconds: long compared with a switch, short compared with human reaction.
"How does a scheduler favour interactive programs without being told which they are?" They want the multi-level feedback queue: jobs that use their whole slice sink, jobs that wait early stay high, and periodic resets prevent starvation.
"What is starvation, and how is it fixed?" A ready job that never gets the CPU. The fix is aging: raise a job's priority the longer it waits.
Something to volunteer that nobody asks for: the scheduler cannot change how long the work takes. In our example every schedule ended at 26 ms. All a scheduler does is decide who waits. Saying this shows you see scheduling as a trade between people waiting, not a way to make work faster.
Recall
- The scheduler picks the next ready thread. It is scored on turnaround time (completion − arrival), waiting time (turnaround − burst), response time (first run − arrival), throughput and fairness, and these conflict.
- Preemptive scheduling uses the timer interrupt to take the CPU away after a time slice; cooperative scheduling waits for the job to give it up.
- First come, first served is simple but suffers the convoy effect. Shortest job first minimises average waiting but needs future knowledge and can cause starvation; shortest remaining time first is its preemptive version.
- Round-robin gives the best response time and poor average waiting; the slice must be long compared with a context switch and short compared with human reaction.
- Priority scheduling needs aging to stop starvation. The multi-level feedback queue learns which threads are interactive by watching whether they use their whole slice.
Self-test: Why did every schedule in Figure 1 end at 26 ms? Compute B's waiting time under SJF. Why can no real kernel run pure SJF? What goes wrong with a round-robin slice of 0.01 ms, and with one of 10 seconds? How does MLFQ tell an editor from a compiler?
Quiz Bank
FoundationalWhat is the difference between preemptive and cooperative scheduling, and what makes preemption possible?
With cooperative scheduling, a running job keeps the CPU until it gives it up by finishing, waiting or yielding. One job that never yields freezes the machine. With preemptive scheduling, the kernel can take the CPU away when the job's time slice runs out, so no job can keep the CPU forever.
Preemption is made possible by the hardware timer interrupt, a clock that interrupts the CPU many times a second whatever it is doing, handing control to the kernel so the scheduler can decide again. Every general-purpose operating system today is preemptive.
FoundationalDefine turnaround time, waiting time and response time.
For a job with an arrival time and a burst time (how much CPU it needs):
- Turnaround time = completion time − arrival time: how long the job was in the system.
- Waiting time = turnaround time − burst time: how long it sat ready but not running.
- Response time = time it first ran − arrival time: how long until it got the CPU at all.
Batch systems care most about turnaround and throughput. Interactive systems care most about response time.
AppliedJobs A, B, C and D arrive at 0, 1, 2 and 3 ms needing 8, 4, 9 and 5 ms. Compute the average waiting time under FCFS and under non-preemptive SJF.
FCFS runs them in arrival order: A 0–8, B 8–12, C 12–21, D 21–26. Waiting = completion − arrival − burst: A 8−0−8 = 0, B 12−1−4 = 7, C 21−2−9 = 10, D 26−3−5 = 18. Average = 35 / 4 = 8.75 ms.
SJF starts A at 0 because it is alone, and does not interrupt it. At 8, B, C and D are ready; the shortest is B, then D, then C: B 8–12, D 12–17, C 17–26. Waiting: A 0, B 7, D 17−3−5 = 9, C 26−2−9 = 15. Average = 31 / 4 = 7.75 ms.
AppliedHow does the round-robin time slice affect behaviour?
A slice longer than every job makes round-robin identical to FCFS, since each job finishes in its first turn. A very short slice gives excellent response time, but every slice ends in a context switch, which has a direct cost and leaves the next thread with cold caches, so a large share of the CPU goes on switching. Real systems use slices of a few milliseconds: long compared with a context switch of a few microseconds, and short compared with human reaction time of about 100 ms.
InterviewWhat is the multi-level feedback queue, and how does it favour interactive programs?
The multi-level feedback queue keeps several queues at different priorities. It always runs a job from the highest non-empty queue, using round-robin within a queue. New jobs start at the top. A job that uses its whole time slice moves down, because it behaved like a CPU-heavy job. A job that gives up the CPU early, usually to wait for input, stays where it is. Periodically every job is moved back to the top, which prevents starvation and gives jobs whose behaviour changed a new chance.
The effect is that interactive programs, which almost always wait before their slice ends, stay near the top and respond quickly, while CPU-heavy programs sink and run when nothing urgent is waiting. The scheduler learns which is which from behaviour, without being told.
StaffAn API server handles fast requests of about 2 ms and occasional report requests of about 2 seconds on the same worker pool. Users complain the fast requests sometimes take seconds. Explain using scheduling theory and propose fixes.
This is the convoy effect. The worker pool behaves like FCFS: a worker that picks up a 2-second report is busy for 2 seconds, and if several reports arrive together they can occupy every worker, so the 2 ms requests behind them wait seconds.
The theory suggests three fixes. First, separate the classes: a dedicated pool or queue for reports, so fast requests never queue behind them. That is priority scheduling with two levels. Second, if work can be split, process reports in chunks and yield between chunks, so a long job cannot hold a worker for its whole duration. That is round-robin applied to the application. Third, make the report path asynchronous: accept the request, put it on a background queue, and return at once, which removes it from the latency-sensitive path entirely. Whichever you choose, guard the low-priority path against starvation with a minimum share of capacity.
Scenario Drill
DrillThe photo-upload service runs on a small machine alongside a nightly backup job. During the backup, uploads that normally take 50 ms take two seconds. Using this page, explain what the scheduler is doing and what you would change.
The backup is a CPU-heavy job that uses its whole time slice every time. The upload service is mostly waiting for the network, then needs short bursts of CPU. On a fair scheduler, when an upload's burst arrives, it must wait for its turn behind the backup's slices, and if the backup has many threads, it waits behind many slices. Each upload needs several bursts, so the small waits add up.
The fixes follow from section 8. Give the backup a lower priority, so the scheduler prefers the upload service whenever both are ready. On Linux that means starting the backup with nice, which 2.3.3 explains. Limit the backup to fewer threads, or to fewer cores. Or move it to a time when uploads are rare. What you should not do is raise the upload service to a real-time priority: that can starve everything else on the machine, including the system services the upload service depends on.
Next: these algorithms are the textbook ideas. Linux uses none of them in pure form. It measures how much CPU each thread has received and always runs the one that has received least, weighted by priority. Page 2.3.3 shows exactly how, with numbers, along with real-time scheduling, many cores, and the priority inversion that nearly ended a Mars mission.