CPU Scheduling I — The Basics

Start with the uncomfortable arithmetic. A modern machine might have 8 CPU cores and 400 runnable threads. Only 8 can physically execute at any given instant; the other 392 are ready and willing but simply have nowhere to run. The scheduler is the part of the kernel that resolves this mismatch: from the pool of threads that are ready to run, it repeatedly chooses which ones actually get a core, and for how long. Do it well and every program feels responsive and the machine stays busy; do it badly and the box feels sluggish even when the CPU is nearly idle.

The key insight that makes scheduling both possible and necessary is that programs almost never use the CPU continuously. A process runs for a little while — computing, comparing, looping — and then stops to wait for something slow: a disk read, a network reply, a key press. That pause is not wasted only if the scheduler immediately hands the freed CPU to someone else. So a program’s life is really a repeating cycle: a CPU burst (a stretch of pure computation), then an I/O burst (a stretch of waiting), then another CPU burst, and so on until it exits.

Ready queue

The set of threads that are loaded, runnable, and waiting only for a CPU — not blocked on I/O, not sleeping. The scheduler picks its next victim from here.

CPU burst

A continuous stretch during which a thread wants the CPU and does nothing but compute.

I/O burst

A stretch during which the thread is blocked waiting for a device (disk, network, terminal) and needs no CPU at all.

CPU–I/O burst cycle

The lifelong alternation between CPU bursts and I/O bursts that characterises essentially every real program.

This cycle lets us sort programs into two rough temperaments, and the distinction drives almost every scheduling decision. A CPU-bound program has long CPU bursts and rare I/O — think of video encoding, a compiler optimiser, or a number-crunching simulation; it wants the CPU for as long as it can get it. An I/O-bound program has short CPU bursts punctuated by frequent, long waits — think of a text editor, a database serving small queries, or a web server; it needs the CPU only briefly but wants it right away, the instant its data arrives.

CPU-bound

Spends most of its time computing; long CPU bursts, little I/O. Throughput matters more than snappiness.

I/O-bound

Spends most of its time waiting on devices; short, frequent CPU bursts. Fast response matters most.

The scheduler does not run constantly — it runs at specific moments, when something happens that might make the current choice of running thread wrong. There are exactly four such moments in the life of a running thread, and knowing them precisely is what lets you reason about any scheduling policy.

• ▸1. A running thread blocks — it makes an I/O request or waits on something — and goes from running to waiting. The CPU is now free and must be given to someone.
• ▸2. A running thread is interrupted — typically by the hardware timer — and is pushed from running back to ready even though it could still compute. This is the decisive one.
• ▸3. A waiting thread’s I/O completes, so it moves from waiting to ready. It may now deserve the CPU more than whoever is running.
• ▸4. A running thread terminates. The CPU is free and a new thread must be selected.

Cases 1 and 4 are unavoidable: the running thread has given up the CPU on its own, so the scheduler simply must pick a replacement — there is no choice about whether to schedule, only about whom. Cases 2 and 3 are where the real policy decision lives, because the current thread could keep running but the OS is choosing whether to take the CPU away from it. A scheduler that reschedules only at 1 and 4 is non-preemptive (or cooperative); one that also acts at 2 and 3 is preemptive.

Non-preemptive (cooperative)

Once a thread has the CPU it keeps it until it blocks or exits. The scheduler never forcibly interrupts a running thread. Simple, but one thread can hog the CPU forever.

Preemptive

The OS can forcibly take the CPU from a running thread — because its time slice expired or a higher-priority thread became ready — and give it to another. Essential for responsiveness and fairness.

Timer interrupt

A hardware timer the kernel programs to fire periodically (say every few milliseconds). Its interrupt hands control to the kernel, which is what makes preemption at decision point 2 physically possible.

Preemption is not something the software can wish into existence — it needs hardware help. Before handing the CPU to a user thread, the kernel arms a timer to fire after a set interval. When the timer’s interrupt arrives, the CPU traps into the kernel regardless of what the user thread was doing, and the scheduler gets to run. Without that timer, a buggy or greedy thread with an infinite loop would keep the core forever and nothing else would ever run. The timer interrupt is the leash that makes true multitasking possible.

To compare scheduling policies we need numbers, not opinions. There is a standard vocabulary of metrics, and the crucial thing to grasp is that no single policy can maximise all of them at once — they pull against each other. A policy that is superb for one metric is often mediocre for another, so choosing a scheduler is really choosing which metric you care about most for your workload.

CPU utilisation

The fraction of time the CPU is doing useful work rather than sitting idle. We want it high — ideally the CPU is never idle while any thread is ready to run.

Throughput

The number of processes completed per unit time. A batch system that finishes 100 jobs an hour has higher throughput than one that finishes 60.

Turnaround time

For one process, the total elapsed time from when it arrives to when it finishes — completion time minus arrival time. It counts everything: running, waiting in the ready queue, and blocked on I/O.

Waiting time

The total time a process spends sitting in the ready queue, ready to run but not running. This is the part a scheduler can actually reduce; it cannot shorten the work itself.

Response time

The time from a process’s arrival to the first moment it starts running — how long until it produces its first sign of life. This is the metric interactive users feel most directly.

Fairness

Every thread makes reasonable progress and none is starved indefinitely. Not a single number, but a property every practical scheduler must protect.

Two of these are easy to confuse, and the difference is worth burning in. Waiting time is the sum of all the time a process spends queued but not running — it can accumulate across many separate turns. Response time is only about the very first turn: how long you waited before anything happened at all. A batch scheduler might give you a fine average waiting time yet a terrible response time; an interactive scheduler does the opposite, jumping to serve you fast even if your total waiting across the whole job is larger.

Throughout the worked examples below we will report average waiting time and average turnaround time, because they are the easiest to compute by hand and expose each algorithm’s character most clearly. Keep response time and fairness in the back of your mind, though — they are exactly the metrics that eventually kill the "optimal" algorithm and force us toward Round Robin.

The simplest possible policy is the one at every supermarket till: serve threads in the order they arrive, and let each run to completion before starting the next. First-Come, First-Served is non-preemptive — once a thread has the CPU it keeps it until its CPU burst ends — and the ready queue is just a plain FIFO. It is trivial to implement and impossible to accuse of playing favourites. It is also, as we will see, quietly terrible for average performance.

Take three processes that all arrive at time 0, in the order P1, P2, P3, with the CPU-burst lengths shown. FCFS runs them back to back in arrival order.

Process   Burst
  P1        24
  P2         3
  P3         3

Gantt chart:
  | P1 (0–24) | P2 (24–27) | P3 (27–30) |

Process   Turnaround   Waiting
  P1          24           0
  P2          27          24
  P3          30          27
  ------------------------------
  Average    27.0        17.0

An average waiting time of 17 is dreadful, and it is entirely P1’s fault. P2 and P3 each need only 3 units of CPU, but because they had the bad luck to queue behind a 24-unit job, they wait 24 and 27 units respectively before they even start. The two quick jobs are held hostage by the one slow one.

Now watch what happens if the very same processes simply arrive in a different order — P2, P3, P1 — with nothing else changed.

Gantt chart:
  | P2 (0–3) | P3 (3–6) | P1 (6–30) |

Process   Turnaround   Waiting
  P2           3           0
  P3           6           3
  P1          30           6
  ------------------------------
  Average    13.0         3.0

If short jobs stuck behind long ones is the disease, the obvious cure is to run the shortest job first. Shortest Job First picks, from all the ready processes, the one with the smallest next CPU burst, and (in this non-preemptive version) runs it to completion before choosing again. Intuitively this gets the little jobs out of the way fast, and that intuition turns out to be provably correct.

Take four processes arriving together at time 0. SJF sorts them by burst length and runs them shortest first: P4, then P1, then P3, then P2.

Process   Burst
  P1         6
  P2         8
  P3         7
  P4         3

Run order (shortest burst first): P4, P1, P3, P2

Gantt chart:
  | P4 (0–3) | P1 (3–9) | P3 (9–16) | P2 (16–24) |

Process   Turnaround   Waiting
  P4           3           0
  P1           9           3
  P3          16           9
  P2          24          16
  ------------------------------
  Average    13.0         7.0

For comparison, plain FCFS on the same four processes in arrival order (P1, P2, P3, P4) yields an average waiting time of 10.25. SJF’s 7.0 is a genuine improvement, and this is no accident: SJF is provably optimal for average waiting time. Given a fixed set of jobs available at the same moment, no other scheduling order can produce a smaller average wait. The proof is a simple exchange argument — if a longer job ever runs before a shorter one, swapping them lowers the total waiting time — but the result is powerful and worth remembering.

There are two escapes, and both matter downstream. First, we can estimate the next burst by assuming it resembles recent ones — schedulers keep an exponentially weighted moving average of a thread’s past CPU bursts and treat that as the predicted length. Second, in special settings like batch systems, users can supply an estimated run time up front (and are penalised if they guess badly). Neither is perfect, which is why SJF lives on as an ideal to approximate rather than a policy to run verbatim.

SJF as described only chooses when the CPU is already free. But what if a very short job arrives while a long one is halfway through running? The preemptive version, Shortest Remaining Time First, answers boldly: at every moment — including the instant a new process arrives — pick the process whose remaining CPU time is smallest, preempting the running one if the newcomer is shorter. It is SJF with the freedom to change its mind mid-run.

This is our first example with staggered arrival times, so read the trace carefully. Each time a process arrives, we compare its burst against the remaining time of whoever is running.

Process   Arrival   Burst
  P1         0         8
  P2         1         4
  P3         2         9
  P4         3         5

Trace of decisions:
  t=0  only P1 ready            -> run P1
  t=1  P2 arrives: 4 < 7 rem    -> preempt, run P2
  t=5  P2 done; ready P1=7 P3=9 P4=5 -> run P4 (5 smallest)
  t=10 P4 done; ready P1=7 P3=9 -> run P1
  t=17 P1 done; only P3 left    -> run P3
  t=26 P3 done

Gantt chart:
  | P1 (0–1) | P2 (1–5) | P4 (5–10) | P1 (10–17) | P3 (17–26) |

Process   Completion   Turnaround   Waiting
  P1          17            17          9
  P2           5             4          0
  P3          26            24         15
  P4          10             7          2
  --------------------------------------------
  Average                  13.0        6.5

Notice how P1 is torn into two pieces: it runs for a single unit, gets preempted the moment the shorter P2 arrives, and only resumes much later once every shorter job is out of the way. That is preemption made visible on the Gantt chart. The payoff is real — SRTF drives the average waiting time down to 6.5, lower than non-preemptive SJF could manage on staggered arrivals, because a freshly arrived short job never has to wait behind the tail of a long one.

Round Robin abandons the search for the "shortest" job entirely and optimises for a different goal: fairness and responsiveness. It gives every ready thread a small fixed slice of CPU time — the time quantum (or time slice) — and cycles through them in turn. When a thread’s quantum expires, the timer interrupt preempts it, and it goes to the back of the ready queue while the next thread gets its slice. The ready queue behaves like a circle: everyone gets a turn, then everyone gets another. It is essentially preemptive FCFS with a stopwatch.

Here are the same three processes from the FCFS example, now under Round Robin with a quantum of 4. Watch how the long P1 no longer monopolises the CPU.

Process   Burst
  P1        24
  P2         3
  P3         3

Slices: P1(4) P2(3,done) P3(3,done) then P1 runs out its rest

Gantt chart:
  | P1 (0–4) | P2 (4–7) | P3 (7–10) | P1 (10–30) |

Process   Turnaround   Waiting   Response
  P1          30           6          0
  P2           7           4          4
  P3          10           7          7
  --------------------------------------------
  Average    15.7         5.7        3.7

Compare this with the FCFS run on the identical processes. There, P2 and P3 did not get the CPU until times 24 and 27; here they start at 4 and 7 and both finish by time 10. The average waiting time also drops (5.7 versus 17). Round Robin will rarely beat SJF on raw average waiting time, but it wins decisively on response time and fairness — and unlike SJF it needs no knowledge of the future and cannot starve anyone, because every thread is guaranteed the CPU within one full cycle of the queue.

Everything hinges on the size of the quantum, and it is a genuine trade-off with two failure modes at the extremes.

• ▸Quantum too large: if the slice is longer than most CPU bursts, threads finish or block before their quantum ever expires, so preemption almost never fires — and Round Robin quietly degenerates into plain FCFS, convoy effect and all.
• ▸Quantum too small: every slice is over almost as soon as it starts, so the CPU spends a large fraction of its time context-switching instead of doing useful work. The overhead of switching dominates and throughput collapses.
• ▸Just right: a common rule of thumb is to pick a quantum long enough that roughly 80% of CPU bursts finish within a single slice, while keeping context-switch overhead to a small percentage. Typical real values are in the 10–100 millisecond range.

Priority scheduling generalises the idea behind SJF: attach a priority number to every process and always run the highest-priority ready process. In fact SJF is just priority scheduling where the priority is the inverse of the predicted burst length. Priorities can come from many places — how important the user is, how much the process paid, how time-critical its work is — and the scheduler need not care where they came from, only how to compare them. (By convention we will treat a smaller number as a higher priority, as most Unix systems do.)

Priority scheduling comes in the same two flavours we have now seen twice. A non-preemptive version picks the highest-priority job whenever the CPU is free and lets it finish its burst; a preemptive version immediately snatches the CPU away whenever a higher-priority process becomes ready. Here is a non-preemptive worked example with all processes present at time 0.

Process   Burst   Priority
  P1        10        3
  P2         1        1
  P3         2        4
  P4         1        5
  P5         5        2

Run order (highest priority first): P2, P5, P1, P3, P4

Gantt chart:
  | P2 (0–1) | P5 (1–6) | P1 (6–16) | P3 (16–18) | P4 (18–19) |

Process   Turnaround   Waiting
  P1          16           6
  P2           1           0
  P3          18          16
  P4          19          18
  P5           6           1
  ------------------------------
  Average    12.0         8.2

Priority scheduling is enormously flexible — it is how a system expresses that some work matters more than other work — but it carries the same danger SJF did, and here it has a name and a famous cautionary tale. If high-priority processes keep arriving, a low-priority process may sit in the ready queue indefinitely, never quite reaching the front. This is starvation (or indefinite blocking).

The standard fix is aging: gradually raise the priority of any process that has been waiting a long time. A job that starts unimportant slowly climbs until, eventually, it becomes the highest-priority thing in the queue and is guaranteed to run. Aging costs almost nothing and dissolves starvation completely, which is why essentially every real priority-based scheduler includes some form of it. Keep this pattern in mind — "rank by something, but boost whoever has waited too long" — because it reappears constantly in production schedulers and even in application-level job queues.

Static priority

Assigned once and never changed for the life of the process (e.g. a fixed importance level).

Dynamic priority

Adjusted by the scheduler over time based on behaviour — lowered for CPU hogs, raised for waiters (aging).

Starvation

A ready process that is perpetually passed over and may never run.

Aging

Steadily increasing a waiting process’s priority so that it is eventually guaranteed to be scheduled.

Lay the five algorithms side by side and their personalities snap into focus. None is best; each trades one virtue for another, and the right choice depends entirely on what your workload values.

Algorithm  Preempt?  Fairness  Starvation   Overhead   Needs to know
---------  --------  --------  ----------   --------   -------------
FCFS         no       poor        no          low        nothing
SJF          no       poor       yes(long)    low        next burst*
SRTF        yes       poor       yes(long)    medium     remaining*
Round Robin yes       good        no          med/high   nothing
Priority    either   depends    yes->aging    low/med    priorities

* burst length cannot be known in advance — must be estimated.

Read the table as a set of engineering choices, not as trivia. If you know nothing about your jobs and just want simplicity, FCFS is honest but risks the convoy effect. If you want the mathematically lowest average wait and can estimate burst lengths, SJF/SRTF are optimal but fragile and prone to starvation. If you care about responsiveness and fairness above all — the interactive case — Round Robin is the workhorse. And if some work genuinely matters more than other work, priority scheduling expresses that directly, provided you add aging so the small jobs are not left to rot.

Batch workloads

Long, throughput-oriented jobs where no human is waiting — data pipelines, builds, scientific runs. Favour policies that maximise throughput and keep the CPU saturated (SJF-like ideas, big quanta).

Interactive workloads

Short, latency-sensitive work where a person or client is waiting on every keystroke or request — editors, shells, web servers. Favour low response time and fairness (Round Robin, priority boosts for I/O-bound threads).

This is exactly why these decades-old algorithms still matter to you as a working engineer. The moment you configure a thread pool, tune a message-queue worker, set nice values on a Linux box, choose a Kubernetes pod priority, or design a job runner that must not starve small tasks behind big ones, you are making a scheduling decision — and you are choosing, implicitly, among FCFS, SJF, Round Robin, and priority with aging. The vocabulary from this chapter turns those choices from guesswork into reasoning.