Operating Systems #4 — CPU Scheduling

CPU scheduling decides which of the running processes gets the CPU right now. It's a bit different from process scheduling (which changes processes' states) — specifically, it's about which process becomes running. The short-term scheduler.

CPU bursts

Every program alternates between working on the CPU and issuing I/O — an alternating sequence. How often it flips is program-specific.

Plot one point per program, with "how long it holds the CPU each time" on x and "how often it takes the CPU" on y, and you get a hyperexponential distribution. Two groups fall out of it.

• CPU bound job — takes the CPU rarely but holds it a long time. Computation-heavy.
• I/O bound job — takes the CPU briefly and gives it back. Editors and the like.

The distinction matters because you have to choose who gets the CPU. Programs with heavy user interaction need it quickly so the user's actions register immediately. So the principle becomes: give the CPU to I/O bound jobs first. The algorithms are built around that principle.

When scheduling happens

1. Running → waiting (issued I/O).
2. Running → ready (timer interrupt). Its time is up, so the CPU is taken away by force and the process goes on the ready queue. This only happens under multiprogramming.
3. A process that isn't currently running goes from waiting to ready. I didn't see why this had anything to do with the CPU at first. When an interrupt arrives for a process in the waiting queue, the CPU has to handle it — and once handling is done, must it return to the process that was running? No. There's no guarantee. That process goes to the ready queue, and when handling ends the scheduler picks again. Slightly unfair, admittedly.
4. The running process terminates. The CPU is free, so someone has to be picked.

Cases 1 and 4 release the CPU voluntarily, so they're non-preemptive; cases 2 and 3 take it by force, so they're preemptive.

The dispatcher

When scheduling happens, the dispatcher module runs — the part that does the context switch. It saves the running process's state and reloads the chosen process's previously saved state into the CPU registers so it can resume. The dispatcher is kernel code, so it switches back to the mode for running user code (kernel → user) and jumps to where the program left off. Most of the time in this sequence goes into the context switch.

Performance metrics

• CPU utilization — scheduling algorithms exist to keep the CPU from idling, so this should go up.
• Throughput — processes completed per unit time. Maximize.
• Turnaround time — from a process starting to it finishing. Minimize.
• Waiting time — time spent in the ready state. (Not the waiting state.)
• Response time — from starting a program to its first response. This is what makes a system feel interactive: the time from pressing a key in a messenger to the character appearing. Shorter feels more immediate.

The two that matter most are CPU utilization and waiting time — keeping the CPU busy, and keeping time spent in the ready queue short.

FCFS

First Come First Served. The first process in gets the CPU. It's the obvious first idea, and it's used widely outside CPU scheduling too (databases, for instance).

Its virtue is fairness — the reason it dominates in everyday life, and the fairest algorithm there is. Outside fairness it has plenty of drawbacks.

Take three processes with burst times 24, 3, 3 arriving at roughly the same time. In order 1, 2, 3, the average waiting time is (0 + 24 + 27) / 3 = 17. In order 2, 3, 1, it's (0 + 3 + 6) / 3 = 3. A hair's difference in arrival produces an enormous difference in outcome.

The cause is the convoy effect. Fast escorts can only move as fast as the slow king. A long-burst process arriving first makes the short ones wait a long time. Turn that around and it says: nudging the order slightly can cut waiting time dramatically. Which is where the other algorithms come from.

SJF and SRTF

Send the fast ones to the front. Predict how long each process will hold the CPU, and give it to the one with the shortest predicted burst first.

There are two variants, for when a process that looks shorter arrives mid-run:

• Non-preemptive (SJF) — wait for the running process to finish.
• Preemptive (SRTF, Shortest Remaining Time First) — hand the CPU over by force.

SJF is optimal — no better method exists. More precisely, the algorithm that minimizes waiting time is the preemptive version, SRTF.

On the same input, non-preemptive SJF gives an average waiting time of 4 and SRTF gives 3. SRTF's waiting time is computed as (arrival to completion) minus burst time.

How do you know the burst time?

You don't. You can only estimate, with exponential averaging.

tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n)

t is the actual value, tau the prediction, alpha the weight. Predicting the (n+1)th CPU burst uses the previous actual value and the previous prediction.

• alpha = 0 ignores recent history — it's saying "average everything in the past."
• alpha = 1 uses only the immediately preceding value.

Expanded, the formula contains every past actual value, but since alpha and 1-alpha are both below 1, older values count for less and less — the terms look like alpha * (1-alpha)^n * t(n). Which is why using tau(n) when computing tau(n+1) is enough.

A large alpha weights recent values heavily and past values lightly (high skewness). A small alpha spreads the weight across the past more evenly.

Does it actually match? For a program whose CPU bursts increase or decrease monotonically, larger alpha fits better. For bursts that swing back and forth, a large alpha can produce badly wrong predictions.

Priority scheduling

This isn't really an algorithm — it's a fallacy. What you set priority to determines which algorithm you end up with. Set priority to the next burst time and you've written SJF. "Priority scheduling" on its own tells you nothing about how scheduling happens.

The base idea is to give the CPU to higher-priority processes first — used, for example, to prioritize processes with real-time requirements. It's usually mixed with another method rather than used alone. Every priority-driven algorithm has both preemptive and non-preemptive forms.

The problem is starvation: low-priority processes can be pushed back forever and never run. The fix is aging — raise a process's priority the longer it stays ready. Note that this only mitigates starvation. Starvation and aging always come as a pair.

Round Robin

The underlying philosophy is FCFS, with a limit on how long a process may hold the CPU. That limit is the time quantum.

• Even if the work isn't done, the CPU must be returned and the process goes on the ready queue.
• Issuing I/O or terminating hands the CPU over early.
• The quantum is a maximum, not a guarantee.
• Every process gets the same quantum, not a per-process one.

The benefit is an upper bound on waiting. Under FCFS a process holds the CPU until I/O or termination, so those behind it have no idea how long they'll wait. Under RR each process ahead uses at most q, so the wait is at most (n-1)q. Having an upper bound raises an algorithm's value considerably, because you can plan around it.

The question is how to pick q. Large q makes it behave like FCFS and the benefit vanishes; small q makes scheduling so frequent that context switch overhead dominates.

Why come up with this at all? Multiprogramming. Under FCFS or SJF a process holds the CPU until it issues I/O or exits, so once a CPU bound job grabs it, everything behind makes no progress at all — the point of multiprogramming evaporates. RR makes each process use a little and give it back, so everyone advances a little. Most operating systems schedule with a hybrid built on RR, combining priority or adding other mechanisms.

Turnaround time is worse than SJF's: processes take turns rather than running to completion, so finishing takes a while. But response time has an upper bound, so its average is short. Under SJF, one long-burst process in front makes response time terrible.

Careful — the time quantum is a separate concept from the timer interrupt.

Prioritizing I/O bound jobs

The principle was to give I/O bound jobs the CPU quickly. Measured against that:

• FCFS — doesn't consider it at all.
• SJF — doesn't explicitly distinguish CPU bound from I/O bound, but has the effect anyway. Processes with short bursts go first, and that's the signature of an I/O bound job.
• Round Robin — doesn't reflect it. Essential for multiprogramming, but on its own it can't express a policy that prioritizes I/O bound jobs. RR has to be combined with something else.

Multilevel queue

Use several ready queues instead of one — say foreground on RR and background on FCFS. But then the background, full of CPU bound jobs, holds the CPU too long and the foreground suffers. So you also schedule between queues.

• Fixed priority scheduling — the background gets the CPU only once the foreground is empty. This certainly prioritizes I/O bound jobs, but as long as interactive jobs remain, CPU bound jobs get nothing at all. Starvation becomes severe.
• Time slice — don't dump everything on one queue; split the time by ratio. CPU bound jobs advance a little while I/O bound jobs still get priority.

Multilevel feedback queue

The trouble with a multilevel queue is that you can't tell up front whether a process is I/O bound or CPU bound. Since you can't, drop it anywhere and move it once you find out.

MLFQ is the algorithm that watches how a process uses the CPU, takes that feedback, and decides which queue to move it to. Put it in the first queue without thinking, then move it once its character is clear.

Defining an MLFQ means deciding four things:

1. The number of queues.
2. The scheduling algorithm inside each queue.
3. The conditions for moving up or down between queues.
4. Which queue a process enters initially.

The form we saw in lecture set the movement condition as "if it didn't finish within that queue's time quantum, it drops to the next queue." I/O bound jobs mostly finish in the upper queues, so the principle is honoured.

The phrase "time quantum" itself comes from Round Robin policy — meaning the upper queues are Round Robin.

Implementing this MLFQ in xv6 was Project 1, covered in #7.

Real-time systems

Real-time systems have the notion of a deadline — a guarantee that work finishes within a certain time. A missile is a hard real time system, and it needs a real-time scheduler.

Other work would merely like the deadline met — video playback, say. That's soft real time computing: give such jobs higher priority. Most operating systems we actually use have some form of it.