CPU Scheduling and Response-Time Goals

The CPU scheduler answers one question many times a second: of all the threads that are ready to run, which one gets this core next? There’s no single right answer, because “best” depends on what you’re measuring. A batch system wants jobs to finish as soon as possible. A laptop wants the window you’re typing in to react within a few milliseconds. A server wants both, plus fairness between tenants. In interviews, the strongest answers start by naming the goal, then pick the policy that serves it.

The metrics that pull in different directions

Two numbers carry most of the discussion:

• Turnaround time: from when a job arrives to when it finishes. Batch work cares about this.
• Response time: from when a job arrives to when it first gets the CPU. Interactive work cares about this, because the first slice is when the user sees something happen.

Throughput (jobs finished per second), fairness (does everyone get a share?) and tail latency (how bad is the 99th percentile?) round out the list. The policies below each optimise one of these at the expense of another. To make the trade-offs concrete, a short Python simulator runs each policy on one CPU and reports the averages. The scenarios follow the ones in OSTEP’s scheduling chapter.

# Jobs: (name, arrival, run time). One CPU, times in ms.
def simulate(jobs, policy, quantum=None, switch_cost=0.0):
    t, remaining = 0.0, {n: r for n, a, r in jobs}
    arrival = {n: a for n, a, r in jobs}
    first_run, finish, queue, last = {}, {}, [], None
    pending = sorted(jobs, key=lambda j: j[1])
    def admit(now):
        while pending and pending[0][1] <= now:
            queue.append(pending.pop(0)[0])
    admit(t)
    while queue or pending:
        if not queue:
            t = pending[0][1]; admit(t); continue
        if policy == "FIFO":
            job = queue[0]
        elif policy in ("SJF", "STCF"):
            job = min(queue, key=lambda n: remaining[n])
        else:  # RR
            job = queue[0]
        if last is not None and job != last:
            t += switch_cost
        last = job
        first_run.setdefault(job, t)
        if policy == "RR":
            slice_ = min(quantum, remaining[job])
        elif policy == "STCF" and pending:
            slice_ = min(remaining[job], pending[0][1] - t)   # run until the next arrival
        else:
            slice_ = remaining[job]
        t += slice_; remaining[job] -= slice_
        admit(t)
        queue.remove(job)
        if remaining[job] > 1e-9:
            queue.append(job)                                 # back of the line
        else:
            finish[job] = t
    n = len(jobs)
    turnaround = sum(finish[j] - arrival[j] for j in finish) / n
    response = sum(first_run[j] - arrival[j] for j in first_run) / n
    return turnaround, response

convoy = [("A", 0, 100), ("B", 0, 10), ("C", 0, 10)]
late = [("A", 0, 100), ("B", 10, 10), ("C", 10, 10)]

Order matters: FIFO and the convoy effect

Three jobs arrive together: A needs 100 ms of CPU, B and C need 10 ms each. First come, first served runs them in arrival order; shortest job first (SJF) runs the short ones first:

A=100ms, B=10ms, C=10ms, all arrive at t=0
  FIFO                   avg turnaround  110.0 ms   avg response  70.0 ms
  SJF                    avg turnaround   50.0 ms   avg response  10.0 ms

Under FIFO, A finishes at 100 ms, B at 110 and C at 120, an average of 110. B and C each needed a tenth of A’s CPU time and still finished last. That’s the convoy effect, the same thing that happens when you’re holding one item and end up behind a full trolley at the supermarket checkout. SJF finishes B at 10, C at 20 and A at 120, for an average of 50. For turnaround, running short jobs first is provably optimal when all jobs arrive together.

When jobs arrive over time

SJF as described is non-preemptive: once a job starts, it runs to completion. Change the scenario so B and C arrive 10 ms after A has started:

same jobs, but B and C arrive at t=10
  SJF                    avg turnaround  103.3 ms   avg response  63.3 ms
  STCF                   avg turnaround   50.0 ms   avg response   3.3 ms

Non-preemptive SJF is stuck: A already holds the CPU, so we’re back to a convoy. Shortest time-to-completion first (STCF, also called shortest remaining time first) preempts. When B arrives, A has 90 ms left and B needs 10, so the scheduler switches to B. The average turnaround is back to 50.

There’s a catch every interviewer will raise: the OS doesn’t know how long a job will run. The multi-level feedback queue (MLFQ) handles that by learning from behaviour. Jobs start at high priority; a job that uses its whole time slice drops a level; a job that gives up the CPU early (because it’s waiting for input) stays high. Interactive programs, which mostly wait, end up near the top, and long CPU-bound jobs sink. A periodic boost back to the top keeps the sunk jobs from starving. Variants of this idea ran in BSD Unix, Solaris and Windows.

Round robin and the time slice

Turnaround-optimal policies have terrible response time for long jobs: under SJF, A doesn’t start until everything shorter is done. Round robin (RR) takes the other side. It runs each ready job for a fixed time slice, the quantum, then moves it to the back of the queue:

round robin on the t=0 jobs
  RR quantum  1 ms          avg turnaround   59.7 ms   avg response   1.0 ms
  RR quantum  5 ms          avg turnaround   58.3 ms   avg response   5.0 ms
  RR quantum 20 ms          avg turnaround   63.3 ms   avg response  16.7 ms
  RR q=1 + 0.1 ms switches avg turnaround   62.6 ms   avg response   1.1 ms
  RR q=5 + 0.1 ms switches avg turnaround   58.8 ms   avg response   5.1 ms

A 1 ms quantum gets every job onto the CPU within a millisecond, which is what an interactive system wants. Turnaround is worse than SJF, because B and C now share the CPU with A instead of finishing first. A long quantum drifts toward FIFO: at 20 ms, response time is 16.7 ms.

The last two lines charge 0.1 ms for each switch between jobs. With a 1 ms quantum the switching adds almost 3 ms to the average turnaround; with 5 ms, only half a millisecond. Real switches cost more than the save-and-restore itself, because the incoming thread finds caches and TLB entries full of the previous thread’s data. So the quantum has to be long enough to amortise switching and short enough to feel responsive; general-purpose kernels use slices of a few milliseconds.

What real schedulers add

Production schedulers mix these ideas and add several more dimensions.

Weights instead of strict priority. Linux’s fair scheduler gives each thread CPU in proportion to a weight derived from its nice value. A nice 0 thread has weight 1024 and a nice 19 thread has weight 15, so when both want the same core the nice 19 thread gets about 1.4%.

Many cores. Each core usually has its own run queue, and the scheduler balances load between them while trying to keep a thread on the core whose caches it has warmed.

Different kinds of core. The M1 these examples ran on has four performance cores and four efficiency cores (sysctl hw.perflevel0.physicalcpu hw.perflevel1.physicalcpu reports 4 and 4). macOS uses a thread’s quality-of-service class to decide where it runs. Running the same CPU-bound Python loop normally and then under taskpolicy -b, which marks it as background work:

default QoS:    1.29s
taskpolicy -b:  5.10s
default QoS:    1.28s
taskpolicy -b:  5.24s

The background run was four times slower because it was kept on the efficiency cores, which run at lower clock speeds. That’s scheduling policy, not a lack of CPU: other cores were free. Linux on ARM big.LITTLE systems makes similar placement decisions with its energy-aware scheduling.

Limits imposed from outside. Containers with a CPU limit (cpu.max in cgroup v2) are throttled once they’ve used their quota in each period, often 100 ms. A latency-sensitive service can be paused for the rest of a period even when the host has idle cores. CPU throttling counters are among the first things to check when a containerised service has unexplained latency spikes.

One more reading aid: uptime here printed load averages: 2.16 2.75 3.51, the average number of runnable threads over 1, 5 and 15 minutes. On this 8-core machine that’s comfortable. Linux also counts threads in uninterruptible sleep, usually waiting on disk, so a high Linux load average doesn’t always mean busy CPUs.

Practice question: a batch job next to an API

An API server and a nightly batch job share an 8-core Linux host. While the batch runs, all cores sit at 100% and the API’s p99 latency doubles. You can’t move the batch job to another host this quarter. What scheduling levers would you use?

Answer

First, the goal: the API needs low response time, and the batch job needs good throughput but can wait. So the batch job should get CPU only when the API doesn’t want it.

The cheapest lever is weight. Run the batch at nice 19, or better with SCHED_IDLE, so whenever an API thread is runnable it wins nearly all the CPU (weight 15 against 1024 for nice values; SCHED_IDLE is lower still). If the services run under systemd or in containers, set CPUWeight or cgroup cpu.weight low for the batch group, which also covers any child processes it starts.

If weights aren’t enough, partition: give the API dedicated cores with cpusets and confine the batch to the rest. The API keeps warm caches and never queues behind a batch thread, at the cost of idle API cores during quiet periods. I’d avoid a hard cpu.max limit on the API itself, since throttling would create exactly the latency spikes we’re trying to remove.

Then verify. CPU scheduling only fixes CPU contention. If p99 is still high, the jobs may be fighting over memory bandwidth, the shared last-level cache or disk, which no CPU policy fixes, and that’s the evidence for moving the batch elsewhere next quarter.

Keep reading

• Operating Systems interview questions
• Operating Systems MCQs
• Starvation, Fairness and Scheduling Policy
• Priority Inversion and Lock Ownership
• OSTEP, Scheduling: Introduction, the source of the FIFO, SJF, STCF and round robin scenarios