11 Multitasking and interrupts — a machine taking turns

11.1 One core, several jobs — the idea of taking turns#

On a machine with one place to compute, the only way to run two programs “at once” is to alternate between them in very small pieces. Go back and forth faster than the eye can follow and, to a person, the two appear to run together.

This is multitasking. But “taking turns” hides three things that have to be decided.

Three things have to be decided. Who decides — who picks the job to run next; the answer is the scheduler inside the operating system. When to cut off — what occasion stops the running job; the answer is two occasions, “when it stops by itself” and “when the time runs out”. And how to announce it — how that occasion reaches the core; the answer is an interrupt from the timer device.

The third row is where multitasking and interrupts meet in this chapter. The first two are policy; the last one is a device.

11.2 When to cut off — three candidates#

“When do we cut off?” could be answered in several ways. Listing the candidates and crossing them out shows why today’s answer looks as it does.

★ Why the first row is crossed out matters. It is often said that hardware does not count instructions for you — it does. Modern cores carry a performance monitoring unit that counts retired instructions and can raise an interrupt when the counter overflows.

The reasons lie elsewhere. First, instruction count is not proportional to elapsed time (one that waits for memory takes tens of times longer — chapter 12), so “a thousand instructions” means a different amount of time each occasion. Second, those counters are a scarce resource, not a general clock to reach for at will. Third, what the operating system is protecting is fairness and response, and those are measured in time, not in instructions. So we cut by time.

11.2.1 Why giving way is not enough by itself#

There were systems that used only the second row: control passes only when the running program says “I step back for a moment”. This is called cooperative, or non-preemptive.

The trouble is right there in the word “cooperative”. If one program does not cooperate, nothing else runs. A long calculation, an endless loop, or a forgotten yield, and the whole machine stops. The mouse stops moving.

Which is why the third row is needed — a device that takes the machine back from outside, regardless of a program’s good will. That way of doing it is called preemptive.

11.3 The kinds of multitasking#

Now the kinds can be laid out. History ran roughly in this order.

★ The first row, the task switcher, is not multitasking at all. Several programs may be loaded, but only one ever runs. On a switch the outgoing program is put to sleep whole (sometimes written out to disk) and the incoming one wakes. It was the compromise of an age when memory was precious. Meet a device today where “switching works but nothing progresses in the background” and this is what you are looking at.

11.4 What is carried across a switch — the context#

Changing jobs means replacing the core’s present state wholesale. That state is called the context, and replacing it is a context switch.

One cost does not appear in that table. After a switch the caches and the translation tables still hold what the previous job was using, so the newcomer starts out slow for a while. That “cold cache” is often more expensive than saving and restoring the registers (chapter 12).

★ So the interval between switches is a trade. Cut often and response improves while the share spent switching grows; cut rarely and the reverse. Operating systems choose this value differently, and the same system gives different values to different kinds of work.

11.5 Who announces the moment — the timer interrupt#

One question is left: who tells the core that the time has run out?

The core does not watch a clock by itself. A timer device stops it at fixed intervals instead, and that stopping is the other half of this chapter: the interrupt.

★ Rows 3~5 are policy; rows 1~2 are the device. The same timer interrupt can carry either a cooperative or a preemptive policy on top of it — and in the DOS years an application program could hijack that interrupt and lay its own policy on it, as we see later in this chapter.

That is the story of taking turns. From here we look at the last link itself, the interrupt — for not only the timer but the keyboard, the disk and the communication line all speak to the core the same way.

11.6 The wires to a device — one after another, or all at once#

The card reader, the line printer and the teletype of chapter 9 were all attached to the computer by wires. How those wires are run decides much of a device’s character.

The teletype was the first kind. Bits went down a single wire in a row, and the receiver saw the “start” mark, set its clock by it, and sampled the value at fixed intervals. The thick cable to a printer was the second kind — eight wires carrying one byte at once, with a separate signal saying “valid now”.

Against intuition, the faster things get, the more serial wins. With eight wires each arrives at a slightly different moment, and as the speed rises that spread grows larger than the time of a single bit. So today’s fast links mostly took the other road: make one serial wire very fast, then bundle several of them.

One more thing. On a small machine a single wire to the outside may serve as input or as output, and which one it is the program announces by writing a value into a fixed place. This — “write into a fixed place and the device acts” — is the basic way of driving the outside, and that place is named by an address but is not memory: reading it gives the state right now, writing it makes something happen. That distinction is what later gives the language the word volatile (chapter 14).

However the wires are run, two problems remain. One is that the two sides work at different speeds — hence the tub of chapter 9. The other is the subject of this chapter: who decides when the outside speaks.

11.7 When the outside speaks#

chapter 9 said there is a tub on the incoming side. Then who puts characters into it? How does a program learn that a key was pressed?

There are two ways.

Polling is the program asking “yet? yet?” over and over. It is simple, but anything that happens between two questions waits for the next one, and the asking goes on even when there is nothing to find.

Interruption is the reverse. The device announces that something happened and stops the CPU. The CPU halts right where it is, jumps to a piece of code registered in advance, handles the event, and returns to the place it left.

This is usually how characters come to be sitting in the input buffer. While my program is busy with something else, the keyboard interrupts, drops one character into the tub and withdraws. That is why it is already there when I go to read.

One thing becomes plain here: an interruption can happen between any two lines of my code, and my code cannot tell that it did.

11.7.1 When several things interrupt#

There is more than one device. A timer, a keyboard, a communication line each announce that something happened. So the interruptions collide with one another too.

★ The fourth row is the surprising one. Interruptions are not counted. “There was a request” is normally a single on/off flag, so if ten more arrive before it is served, the handler still runs once. That is why code dealing with the outside does not count how often it was called; it asks the device what happened.

11.7.2 What “asking the device” actually means#

We just said the code “asks the device”. But how does one ask? Send it a letter? Call some function?

Reading a fixed address is the asking. There is no new syntax and no special function.

Outside devices, we said, are driven by writing to and reading from fixed places. Think of such a place as the device’s counter — a window it keeps open. The window is named by an address but it is not memory. When the CPU puts that address on the wires, the device wired to it puts its current state back as a value. One read is the question, and the value that comes back is the answer — there is no separate exchange of messages.

The windows a device keeps open are usually these.

Take an example. An interrupt has come from the device that receives characters — the one that fills the tub of chapter 9. But what if three bytes had arrived in the meantime?

Code that counts how often it was called takes one byte, because it was called once, and loses the other two. Code that asks does this instead.

void uart_isr(void)                          /* called when the interrupt fires */
{
    while (*UART_STATUS & RX_READY)          /* "anything to take?" --- the asking */
        buffer_push(*UART_DATA);             /* "here" --- one byte per read */
}

*UART_STATUS reads the status window, and one bit of that value means “there is something to take”. If there is, the data window is read for one byte, and the question is asked again. Three bytes waiting means three turns of the loop; none waiting means no turns at all. How often the handler was called does not matter.

One property surprises people at first: reading changes the device’s state. Reading the data window removes that byte from the device’s queue, and if nothing is left the “something to take” bit in the status window goes down by itself. That is why the loop above stops on its own.

11.7.3 When another arrives mid-handler — how existing code copes#

The “nesting” row above is the one that troubles real code most. If another interrupt arrives while a handler is running, the same code may start again before it has finished.

Machine and code cope together. The machine first: most chips disable interrupts automatically the moment they jump into a handler. On a machine with priorities the rule is “block the same level and below, let more urgent ones in”, so nesting does not happen at random — it happens only for something more urgent.

On top of that sits the discipline of the code. From the oldest device drivers to today’s, five things recur.

★ The first row covers most of the rest. A short handler both reduces overlap and gets out of it quickly. That is why old device code has handlers that are startlingly short — move one byte into the tub, set one flag saying there is work to do, and that is all.

The same shape repeats on top of an operating system. While a signal handler runs, the same signal is usually blocked, and what a handler may do is defined very narrowly. Why those rules exist is taken up, with the rules themselves, in chapter 81.

11.8 How the two differ — interrupts and multitasking#

Having come this far you can see the two meeting in one place — which is exactly why they should be held apart. They look alike, and their purposes are plainly different.

★ The fourth row separates them most sharply. Returning to what was running is the default for an interrupt; switching is a choice the operating system lays on top. A timer interrupt does not necessarily mean moving to another job — if time remains, control simply returns.

Conversely multitasking can exist without interrupts. Cooperative scheduling does: switch only where a program yields and no timer is needed. What disease that suffers from we have already seen.

Splitting the same moment between the two: when the timer raises an interrupt the hardware finishes the current instruction, jumps to the handler, and holds interrupts off while it runs. Meanwhile the operating system counts the time and asks whether this job’s turn is over. And as the handler ends the hardware restores the context as it was — except that the operating system may have put a different context there.

The last cell of the third row is where a “switch” actually happens. On the way back from an interrupt the operating system swaps the place it will return to. As far as the hardware is concerned it is merely returning from a handler — but on arrival, a different program is running.

11.9 It was once almost everything a personal computer did#

Today interrupts have sunk below the kernel and are hard to see. In the first age of the personal computer they sat close to the user. This is the story of the DOS years.

Machines of that era had a table saying, for each interrupt number, “when this number arrives, jump here”, and that table lived at the very start of memory (see chapter 4 for why the neighbourhood of address 0 is special). The striking part is that an application program could write its own address into that table.

DOS also had a task switcher: several programs loaded, screens swapped between them, but whatever went to the back was put to sleep whole — the first row of the table of kinds above. On a machine with about 640 KiB of memory even that was a great convenience.

★ The fourth and fifth rows say the most about that era. DOS ran one program at a time, yet by hijacking the clock interrupt an application could slice execution into pieces and run several programs in turn. Such products existed — and it was an application, not an operating system, that did it.

11.10 Where this story survives today#

DOS is gone; the structure remains. Here is only where what you saw in this chapter leads.

Three sentences are worth taking from this chapter. Outside devices are driven by writing to and reading from fixed places. An interrupt can arrive at any time, and when several arrive they collide. And on top of that stands the appearance of several programs running at once.

You will probably never use one. But the sense of how a machine takes turns between jobs — and why some code must be written on the assumption that anything can cut in at any moment — stays with you.