Mission control

The last chapter ended with a question: a hundred processes, two cores. Who’s next? Open the task manager on your computer. It lists several hundred processes and four, eight, maybe sixteen cores. Almost all the processes are asleep, waiting for an email, a keystroke, a reply from a server. But a dozen or two are ready to run at any second, and each behaves as if the processor were all its own. Somebody decides, every few milliseconds, which of them gets a core. In an operating system that somebody is called the scheduler.

For the next hour the scheduler is you, and your shift is in mission control. You inherit the console from the most famous overloaded computer in history, the guidance computer of the Apollo 11 lunar module. First we listen to its alarm. Then we learn its two skills, sharing a processor and meeting deadlines, take the alarm apart and land the module ourselves. At the end we write our own multitasking, the same kind that runs inside every Python web server.

102:38. Program alarm

Code 1202 meant that the computer had been given more work than it could get through. That sounds like a death sentence: the ship is being flown by a machine that can’t keep up. Yet the computer chose by itself which part of the work to drop, dropped it and went on flying the module to the Moon. How a program decides “this can go” becomes clear once we see how one processor is shared among many jobs at all.

The console: one core, many jobs

At any moment a processor core executes one instruction of one program. That is how Iskra-8 from Chapter 32 works, and so does every core in your laptop. But there are many programs. The operating system keeps each one in one of three states. Running: a core is executing its instructions right now. Ready: it could run, but all the cores are busy, so it waits in line. Blocked: it has no use for a processor at the moment, because it is waiting for the disk, the network, a keystroke, or for some time to pass. Of the hundreds of processes, nearly all are blocked. The ready ones usually number a handful, yet there are still more of them than cores, and every time a core comes free somebody picks the next one from the ready queue. The picking is done by a part of the operating system kernel, the scheduler.

You can feel it at work. The program below spins in an empty loop, checking the clock all the time. If more than a millisecond has passed between two looks, the program was away: the core went to someone else. First we spin alone, then we start one, two and three rivals, the same kind of empty loops in separate processes. The function os.sched_setaffinity pins the program to core number 0, and the rivals it starts inherit the pinning, so they all have to share one core.

The function cpu_seconds reads the process’s entry in /proc, which you know from the last chapter: how many ticks of processor time it has received. Comparing who got how much in the same six tenths of a second shows how the scheduler divides the core: with one rival we get about half, with two about a third, with three about a quarter. Nearly equal shares. The holes last from milliseconds to tenths of a second, depending on how busy the machine is (the sandbox on the course server also shares its processor with other readers), and the numbers change from run to run. The picture holds, though: dozens of holes in a fraction of a second, and nobody owns the core for long.

The strange part is something else. The empty loop while True: pass asks nothing of anyone: it reads no files, prints nothing, makes no system calls, and still the core is taken away from it. The hardware makes this possible. The processor has a timer, and every few milliseconds it sends an interrupt. At that signal the processor abandons the program’s current instruction, remembers where it stopped (as with a subroutine call in Chapter 32) and jumps to a handler inside the operating system kernel. The handler calls the scheduler, and the scheduler decides whether to give the core back to the same program or to hand it to another. The stretch of time a program gets without a break is called a time slice, or quantum, and taking the core from a program that had no intention of giving it up is preemption. Devices send interrupts too: the keyboard when a key is pressed, the network card when a packet arrives. That is why a sleeping program wakes up the moment something happens for it.

Cambridge, 1961. Time-sharing

That is how time-sharing came about: the processor is cut into quanta, and the quanta are handed out in turn. If there are many quanta per second and each is short, a person at a terminal can’t tell that the machine is busy with somebody else. Your laptop does the same thing, except that it has one user and hundreds of programs.

Each change of program on a core is a context switch. The program must not be able to tell: when it gets the core back, every register must be as it was at the moment of the interrupt. So the kernel saves everything the processor knows about the interrupted program into its process entry and loads the state of the next process from its own entry. On Iskra-8 the context is seven bytes: registers R0–R3, the program counter, the stack pointer and the flags. On an x86-64 processor it is sixteen general-purpose registers, the program counter, the flags and the wide registers of the vector instructions from Chapter 35, up to several kilobytes in all. What this costs in time is easiest to measure. A C program starts a second process, and the two toss a single byte back and forth through a pair of pipes, like a ball: each waits until the byte reaches it and immediately sends it back. Both processes are pinned to one core, so every serve is a switch.

fork and pipe come from the last chapter. It works out at about a microsecond per switch, thousands of processor cycles, and that includes writing and reading the byte. In the sandbox on the course server the number comes out larger: there an extra protective layer stands between the program and the machine’s kernel, and every entry into the kernel costs more. By itself the switch is cheap: with a quantum of a few milliseconds, switches eat a fraction of a percent. The expensive part is what the cell doesn’t show. The new program arrives at cold caches (Chapter 34): they hold the previous program’s data, and its first few thousand memory accesses go all the way to slow memory. That is why the quantum can’t be made as short as you like: switching too often, the processor would spend most of its time moving house.

Who goes next: queue policies

The central question at the console: a core has come free, so which of the ready jobs do we call? There are many policies, and to compare them we need yardsticks. Say a job arrived at time $a$, needs $b$ milliseconds of processor time, first got a core at time $s$ and finished at time $f$. Then:

• turnaround time $f - a$ is how long it took from the job’s arrival to the finished result;
• waiting time $f - a - b$ is how much of that the job spent in the queue when it could have been running;
• response time $s - a$ is how soon the job first got the processor.

Whoever starts a computation overnight cares about turnaround. A person at the keyboard feels the response: if a letter appears on the screen a tenth of a second after the keypress, that still counts as “at once,” and after a second it is “sluggish.” Take four jobs and hand out the core in two ways: in order of arrival, and round robin with quanta of 2 ms.

Served in order of arrival, the report holds the core for eight milliseconds, and the three short jobs all wait for it: the average wait is 5.75 ms, and the response is the same, since each job, once started, runs to the end. Round robin cuts the report into pieces, mail and search slip in between them, and the average response drops to 1.75 ms. The report itself, though, is now done at 15 instead of 8: the long job pays for the short ones’ comfort. A schedule is easiest to draw as bars along a time axis, the way construction foremen draw their work plans. The picture is called a Gantt chart, after the engineer Henry Gantt, who drew the workload of factory shops this way in the 1910s. The one below covers every policy in the chapter.

First come, first served

The first policy is the one every queue in the world starts with: whoever comes first runs first, and runs to the end. It is called FIFO (first in, first out) or FCFS (first come, first served). It needs to know nothing about the jobs, and it is hard to argue with. Its weakness is familiar to anyone who has stood at a supermarket checkout with one bottle of water behind a person with a full cart: one long job in front, and all the short ones behind it wait until it is over. This is called the convoy effect: the column moves at the speed of its slowest truck. Pick the “convoy” set and the FIFO policy in the chart: six short jobs of one or two milliseconds each stand behind a long one of 24, and the average wait is over twenty milliseconds, although nearly all the jobs are small.

Shortest job first

If the short jobs suffer behind the long ones, let the short ones go first. Shortest job first (SJF) calls whichever ready job has the least work left. On the “convoy” set it clears the queue at once: the six short jobs slip through, the long one waits an extra eight milliseconds, and nobody notices. And it can be proved that no order does better on average waiting time.

This is the same exchange argument that proved the greedy choice of requests correct in Chapter 23. It also shows why the order matters so much: in the sum of waits, the length of the first job counts $n - 1$ times, since everyone else waits for it, the length of the second $n - 2$ times, and so on, while nobody waits for the last one. Long jobs belong where fewer jobs wait for them.

If a job can arrive while another is running, the policy has a preemptive version: when a job arrives that is shorter than what remains of the current one, the current one is interrupted. It is called SRTF (shortest remaining time first), and it is in the chart too. But both versions run into the same question: how is the scheduler to know how much work a job has left? A program doesn’t say, and usually doesn’t know itself. The way out is the one used by the branch predictor of Chapter 35: judge the future by the past. Programs usually work in bursts: compute, go to the disk or the network, wait, compute again. The length of the next burst is predicted from the previous ones, for example with an average in which recent bursts weigh more than old ones.

Each new forecast is half the latest observation plus half the previous forecast. An observation made $k$ bursts ago has weight $2^{-(k+1)}$: the past is forgotten exponentially, which is why such an average is called exponential. When the program changes its habits (a text editor starts checking spelling, and its bursts grow from 2 to 13 ms), the forecast catches up within two or three bursts. The parameter $\alpha$ decides whom to trust more: with $\alpha$ close to one the forecast is jumpy but quick, close to zero it is calm but slow.

Round robin

Shortest job first is good for waiting, but not for response: a long job may never get the core while short ones keep coming. Time-sharing works differently, by round robin: every ready job gets a quantum, and if it hasn’t finished, it goes to the back of the queue. Nobody waits longer than $(n - 1)$ quanta, where $n$ is the number of ready jobs. The response is excellent, while long jobs get a worse turnaround: their work is smeared across the whole schedule.

A round-robin queue has one setting, the length of the quantum. Move the quantum slider in the chart with the switch cost turned on. A quantum longer than any job turns the round into FIFO: everyone finishes in one go. With a very short quantum the core is shared perfectly evenly, but the schedule fills with gray gaps, and the processor spends more time switching than working. In practice the quantum is from a few to a few tens of milliseconds: much longer than a switch, and much shorter than the delay a person notices.

Priorities and starvation

Jobs are not all equal. Music must play without stutters and the interface must respond, while a backup can wait. So jobs may have priorities: the scheduler calls the ready job with the highest priority, and among equals goes round robin. In Unix a priority is set with the nice command: the higher the “niceness,” from −20 to 19, the more readily a program gives way to others. But you already know how that ends under load: in the emergency room of Chapter 18, under the “by severity” rule, a non-urgent patient wasn’t called while urgent ones kept coming, and waited hours for a doctor. That is the same starvation. Operating systems textbooks pass on a story: rumor has it that when the IBM 7094 at MIT was shut down in 1973, a low-priority job turned up that had been submitted in 1967 and had never been run. It may be made up, but the mechanism is right.

The cure is familiar from Chapter 18 too. There the “by deadline” rule put a non-urgent patient ahead of a more urgent newcomer once the first had waited too long. In schedulers this is called aging: while a job waits, its priority creeps up, and sooner or later it overtakes everyone. In the chart the priorities policy has an “aging” checkbox. Turn it on for the “starvation” set, and the lowest-priority job gets the core without waiting for the urgent ones to run out.

A queue that learns

Corbató wanted two things from CTSS at once: instant response for the person at the terminal, and steady progress for long computations. The scheduler can’t know in advance which job is interactive and which one crunches numbers, but it can watch. That is how the multilevel feedback queue (MLFQ) came about, the chief invention of CTSS. Corbató described it in the 1962 paper; modern textbooks state it as five rules. Some details were different in CTSS, but the idea is the same.

1. There are several queues, each with its own priority. A job from the highest non-empty queue runs; within a queue, it is round robin.
2. A new job starts in the top queue: until it has shown what it is, we assume it is interactive.
3. If a job uses up the whole quantum of its level, it moves down a level. Further down the quanta are longer: if the job likes to compute, let it compute longer and less often.
4. If a job gives up the core by itself before its quantum is over (it went off to wait for a keystroke or the disk), it stays on its level.
5. Every so often all jobs are moved back to the top. Otherwise the long jobs at the bottom would starve, and a program that changed character, computed for a while and then became interactive, would stay at the bottom forever.

The queue sorts out by itself who is who. A text editor that wakes on a keystroke, works for microseconds and goes back to sleep never reaches the end of its quantum and lives at the top: it is called at once. A computation sinks to the bottom within a couple of quanta and gets the core whenever the interactive jobs need nothing. CTSS worked this way too: the lower the level, the longer the quantum. In the chart the MLFQ policy has three levels with quanta of 1, 2 and 4 ms; the color of a bar shows the level at which the job ran.

Rule 4 has a loophole, and an easy one to find. A program that wants to live at the top can work for almost the whole quantum and, a moment before it runs out, briefly go off to wait, say by reading a byte from a file. Formally the quantum isn’t used up, the level is kept, and a program that does nothing but compute gets the priority of an interactive one. The cure is to count all the time used on a level: whoever has spent their allowance, even in small pieces, moves down. Modern systems have moved away from strict levels, but the idea has stayed. Windows temporarily raises the priority of a thread that has finished waiting for the keyboard or the disk. From 2007 to 2023 Linux used the CFS scheduler: it called the job that had received the least processor time, adjusted for its weight, and kept the jobs in a balanced search tree, a relative of the AVL trees. Since version 6.6 it has been replaced by the EEVDF scheduler, which also takes into account how urgently a job needs a response.

The 1202 alarm, taken apart

We now have the words to understand what happened aboard the Eagle. The operating system of its computer was designed by Hal Laning of the MIT Instrumentation Laboratory, and the landing program was written by a large team at the same laboratory; Margaret Hamilton led the development of the onboard software. The system divided work into two kinds. Short tasks that ran by the clock, such as “read the accelerometers again in two seconds,” were kept on a list called the Waitlist, and a timer interrupt started them, preempting everything else. Long jobs (navigation, guidance, putting numbers on the display) were started by a dispatcher called the Executive, and every job had a priority: the processor went to the ready job whose priority was highest.

The main job of the descent was called SERVICER. Every two seconds a clock task read the accelerometers and queued another SERVICER: work out where the module is and where it is going, decide how to point the engine and how much thrust to give, and update the numbers on the display. It was the longest job of all, and it was given the lowest priority: short jobs broke in on it, and SERVICER got whatever time was left after them. Every job needed a little corner of memory for as long as it lived, and the computer’s memory was tiny: 2,048 words that could be rewritten. So Laning had carved it up in advance: eight core sets for jobs and five larger areas for vector arithmetic, the VAC areas. A job arrives and takes a core set; it ends and frees it. If no core set is free, the Executive raises alarm 1202; if no VAC area is free, 1201.

Normally there were core sets to spare: a job finished long before the next one arrived. The programmers had worked out how much processor time stayed free at each stage of the descent. According to Don Eyles, who wrote landing software, the margin was more than 15% before the landing radar locked onto the surface, about 13% after, and if the crew called up extra data on the display, as Aldrin did with his 16/68, it fell to 10% or less. And then somebody started stealing cycles. The rendezvous radar looked up at the command module, and the counters for its antenna angles worked like this: every change of angle sent a pulse, and the processor, without asking the program, spent a memory cycle adding or subtracting one in a memory cell. Up to 6,400 pulses a second came in for each angle, and in the worst case together they ate about 13% of the processor’s time. The margin went negative.

From there on everything follows the laws of queues. SERVICER gets the processor last and doesn’t manage to finish, and two seconds later the clock task queues the next one. The unfinished SERVICER gives up neither its core set nor its VAC area, and the new one gets its own. The new one doesn’t finish either. Unfinished jobs pile up, and the core sets and VAC areas run out. The Executive takes an emergency exit, posts code 1202 or 1201 and restarts the program. The restart was cleverly designed. Computations that had to survive marked checkpoints as they went, and after a restart each one carried on from its last mark. The ones that could be spared vanished without a trace. The newest SERVICER survived; its unfinished predecessors were gone, and so was the 16/68 monitor: after the first two alarms the display went back by itself to the ordinary descent data. The load fell, and guidance carried on. Eyles later wrote that they “had devised a real-time control system that under certain conditions was ‘fault tolerant.’”

Now you take the console. The model below is simplified: the load figures follow Eyles’s account, rounded, and the descent is squeezed into a little over a minute. Turn on the rendezvous radar and the 16/68 monitor and try to land the module under each policy. In “by hand” mode the model stops at every alarm and waits for you to decide what to drop.

Under “priorities” the computer is the first to stall: SERVICER, with the lowest priority, can’t keep up, its unfinished copies occupy the VAC areas, and at the first alarm there is nowhere to put a new job, while the computer has no way of dropping anything. FIFO holds out longer, but guidance stands in the common queue behind the display updates, falls further and further behind, and the module goes into an abort. Only the third policy lands the module: priorities together with a restart that keeps the newest SERVICER and throws away the unfinished copies and the 16/68 monitor. That is how the Eagle’s computer was built. Switch 16/68 back on, as Aldrin did, and the alarm returns. In “by hand” mode you can see what to drop: the old copies of SERVICER have already delivered their guidance, and if you spare them, the new SERVICER finds no room and the module flies blind.

Real time: making the deadline

The Eagle’s computer had a requirement that a laptop doesn’t have: an answer that comes too late is a wrong answer. A command for the attitude thrusters computed half a second after the right moment is better not carried out at all. Such systems are called real-time systems. In hard real time, lateness is never acceptable: brakes, an airbag, a pacemaker. In soft real time it is unpleasant but bearable: a video call that drops a frame now and then.

Real-time tasks are usually periodic: adjust the engine every 4 ms, recompute navigation every 10 ms, update the display every 14 ms. Each instance must finish before the next one arrives. There are two classic ways to share the core. The first is fixed priorities by rate: whoever comes more often matters more. The second is by deadline: whoever has the earliest deadline runs. You have met the second rule before, in the emergency room of Chapter 18, where patients were chosen by the moment their waiting limit ran out. It is called EDF (earliest deadline first). We test both on three tasks: first at a load of 91%, then at an overload of 105%.

At a load of 91% the deadline rule makes every deadline, while by rate the display is late 15 times in two seconds. In 1973 C. L. Liu and James Layland proved that on a single core EDF meets the deadlines of any set of periodic tasks whose total load is at most 100%, and no policy can do better. For fixed priorities the guarantee is more modest: $n$ tasks are sure to make it if the load is at most $n(2^{1/n} - 1)$. For three tasks that is about 78%, and as $n$ grows the bound sinks toward $\ln 2 \approx 69\,\%$. Above the bound you may be lucky or you may not, and we were not.

The second row turns the conclusion around. Under overload the rate rule sacrifices the display alone: the engine and navigation were never late. EDF is late everywhere: the engine 42 times, navigation 28. Every instance whose deadline is near gets the core first, even if it won’t make it anyway, and drags the next ones down with it: the misses spread in a wave, like falling dominoes. So in systems where overload is possible, the deadline rule gets an extra safeguard, and what matters is separated in advance from what can wait: by fixed priorities or, as in the Eagle’s computer, by a list of what will survive a restart. Fixed priorities have a trap of their own: in 1997 it made the Mars Pathfinder reboot again and again, because a low-priority task held something that a high-priority one needed. That is the story of Chapter 39.

Giving the core back yourself

So far the scheduler has taken the core by force, with a timer interrupt. There is another way: programs give up the core themselves, whenever it suits them. This is cooperative multitasking. The jobs of the Eagle’s computer worked this way: the Executive never took the processor away in the middle of a computation; a job itself checked regularly whether a job with a higher priority was waiting, and gave way. Windows 3.1 and the classic Mac OS lived by the same rules: a program got control, handled the next event (a click, a keypress) and handed control back to the system. As long as everyone is polite, this works well: switching is cheap, and a program is never interrupted at an awkward moment, in the middle of updating a shared table, say. But one program that gets lost in thought and doesn’t yield freezes everything: the cursor, the windows, the music.

Cooperative multitasking is easy to write yourself with the generators of Chapter 10. A generator can stop at yield and later carry on from the same place, which makes it a ready-made job that gives up the core: yield means “that’s all for now, call the next one.” The dispatcher is a queue of generators and a loop. Press Steps and follow control as it jumps from a generator to the dispatcher and back.

Nine lines of dispatcher, and we have a round-robin queue, as in CTSS, only without a timer. A function that can stop many times and carry on from where it stopped is called a coroutine, as opposed to a subroutine, which runs from start to finish in one call. According to Donald Knuth, the word was coined by Melvin Conway in 1958. Time to test politeness. A cursor wants to blink every few milliseconds, and next to it runs an archiver that yields sometimes often, sometimes rarely, sometimes almost never.

While the archiver yields every thousand steps, the cursor barely feels its neighbor: tenths of a millisecond. Every hundred thousand steps, and the freezes are around ten milliseconds, on the edge of noticeable. And if the archiver doesn’t yield until its work is done, the cursor stands still for tenths of a second, as long as the whole computation takes; with a bigger archive it would stand for minutes. That is what a “hang” looked like on a computer with cooperative multitasking: one program is to blame, and everything freezes. Compare the two worlds in the widget.

asyncio: waiting without idling

A web server, a chatbot, a program that downloads a hundred pages: they spend nearly all their time waiting for the network, the database, the disk. They need the processor for milliseconds and wait for seconds. Starting a process for every wait is wasteful. It makes more sense to have one program with hundreds of coroutines that give up the core every time they start waiting. Inside a single program cooperative multitasking works well: the program is no enemy of itself, and a switch between coroutines costs about as much as a function call and needs no trip into the OS kernel. Python has the asyncio module for this: it appeared in version 3.4 in 2014, and the keywords async and await in version 3.5. A coroutine is declared with async def, and await goes where it is ready to yield, usually where it waits for something. Instead of our run, an event loop does the work: it keeps a queue of ready coroutines and a list of waiting ones (some wait for time, some for the network), and when none is ready, it sleeps until the nearest event.

The course sandbox has no network, so asyncio.sleep stands in for a server’s reply; to the event loop it makes no difference, both are waiting. asyncio.gather starts coroutines together and waits for all of them, and asyncio.run sets up an event loop and keeps it turning until the main coroutine finishes. The three requests went out at once, the replies came after 0.5, 1 and 1.5 seconds, and the whole thing took a second and a half instead of three. A thousand one-second waits took a little over a second, on a single core, without a single thread. This is how web servers work in Python, and in JavaScript, where the event loop is built into the Node.js runtime: tens of thousands of connections, nearly all of them waiting, and the core serves the ones whose data has arrived.

This world has the same limitation as Windows 3.1: an event loop can’t take the core away. If a coroutine calls something that waits without yielding (time.sleep, an ordinary requests.get, a long computation), everything stops.

One word in one line, and the indicator freezes for half a second. This is the most common mistake in asynchronous code, and it shows up as “the server hangs sometimes”: all the clients wait while one handler sleeps or computes. Remember one rule: inside async def, everything that waits must wait through await. For the network there are asynchronous libraries; for a call that can’t help blocking there is asyncio.to_thread, which sends the call off to a separate thread so the event loop keeps running. A long computation is better moved to a separate process, where the operating system’s scheduler will preempt it.

The tasks will need one more tool. To a server, a thousand simultaneous requests look no different from an attack, so a polite client limits itself. asyncio.Semaphore(3) is a turnstile with three places: async with gate lets a coroutine in only if fewer than three are inside, and queues the rest.

Twelve pages of 0.2 seconds each, three at a time: four rounds, 0.8 seconds. Twelve coroutines change the counter stats["now"], and not a single change is lost: between awaits nobody interrupts a coroutine, and the line stats["now"] += 1 runs in one go. With threads, which the OS scheduler preempts, this no longer holds; we will come to that in the chapter after next.

Tasks

Three tasks, three shifts at the console: build a round-robin schedule, compute the waiting time under shortest job first when jobs don’t all arrive at once, and crawl a website with a hundred simultaneous requests without upsetting the server.

What next

Quantum by quantum, a hundred programs get the core, and each is sure it is running alone. But they share more than the processor. Back to the experiment with fork. A C program sets up a variable x, splits in two, and the child changes its x. Both processes print the value and the address of the variable.

The address is the same and the values differ: 99 in the child, 10 in the parent. If an address is the number of a memory cell, as we have assumed since Chapter 14, one cell can’t hold two numbers at once. So the address a program sees is not the number of a cell in a memory chip. Every program believes that all of memory belongs to it alone: it writes at any address, and nobody else sees or spoils its numbers. How this deception works is the subject of the next chapter. It resembles a hotel where the number on your key is not the number of your room.