Interrupts

Polling versus interrupts, priorities, the stack and interrupt service routines in the fetch-decode-execute cycle.

A10.4Operating systems, software and translatorsA level40 min

A processor runs one instruction after another. But the world does not wait: a key is pressed, a disk finishes writing, the battery runs low, a wheel encoder ticks. The operating system needs some way to find out about these events the moment they happen. This lesson is about the two ways to do it, polling and interrupts, and exactly what the processor does when an interrupt arrives.

Polling

The simple way is to keep asking. A program that checks the distance sensor every time round its loop is polling it:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

checks = 0
while distance() > 30:          # ask the sensor, again and again
    checks = checks + 1
    forward(40, distance=2)
print("wall near after", checks, "checks")

Run this in the simulator

Polling is easy to write, but it has two costs. Most checks find nothing, which wastes processor time. And an event is only noticed at the next check, so a fast event can be noticed late or missed. With hundreds of devices, a processor that polled them all would do little else.

Interrupts

An interrupt is a signal sent to the processor to say that something needs attention now. Instead of the processor asking every device, the device tells the processor. Interrupts come from:

• hardware: a key press, a mouse movement, a disk or printer that has finished, a network packet arriving, a power failure;
• software: a program that divides by zero, tries to use memory it does not own, or makes a system call;
• the timer: a clock that interrupts at regular intervals, which is how the scheduler takes the processor back from a process whose time slice is over (lesson A10.5).

Each interrupt has a priority. A power failure matters more than a key press, so it is dealt with first.

Interrupts and the fetch-decode-execute cycle

The processor does not stop halfway through an instruction. At the end of every fetch-decode-execute cycle, it checks whether an interrupt is waiting (a flag is set in its interrupt register). Then:

1. If an interrupt is waiting and its priority is higher than the task currently running, it is serviced. Otherwise it waits, and the processor carries on with the next cycle.
2. The contents of the registers, including the program counter, are saved onto the stack. This saved state is sometimes called the volatile environment.
3. The address of the interrupt service routine (ISR) for this kind of interrupt is loaded into the program counter. The addresses of the ISRs are kept in a table, the interrupt vector table.
4. The ISR runs, fetching and executing its instructions like any other code.
5. When the ISR finishes, the saved values are popped off the stack back into the registers, and the interrupted task carries on exactly where it stopped, unaware anything happened.
6. The processor checks again for waiting interrupts.

In OCR's reference language, the check at the end of each cycle looks like this:

if interruptWaiting AND interruptPriority > currentPriority then
    push registers onto stack
    PC = addressOfISR
endif

Why a stack? Because an ISR can itself be interrupted by something more important. Each interruption pushes another set of saved registers on top, and the routines are resumed in the reverse order they were interrupted: last in, first out.

A worked trace

Here is a small model. The main program is 4 instructions long and has priority 0. Each ISR is 2 instructions long. A disk interrupt (priority 2) arrives during cycle 0, and a printer interrupt (priority 1) during cycle 1. An interrupt that arrives during a cycle is checked at the end of that cycle.

The printer waited two cycles because something more important was running. Nothing was lost: the interrupt stayed pending until it could be serviced.

Polling or interrupts?

Simple embedded programs, like yours on BugBot, often poll: they check the sensor every time round a loop that runs many times a second anyway. The firmware underneath relies on hardware interrupts for events that must not be missed, such as data arriving on a serial line.

Task: nested interrupts

Simulate the processor from the worked trace, with nesting. The inputs are:

• MAIN_LENGTH, the number of instructions in the main program (6); main has priority 0;
• ISR_LENGTH, the number of instructions in every ISR (2);
• arrivals, a dictionary from a cycle number to a list of (name, priority) interrupts that arrive during that cycle. Priorities are positive integers; higher is more important.

Keep the running routine's name, priority and next instruction number (starting at "main", 0, 0), a stack list and a pending list. Number cycles from 0. Each cycle:

1. print cycle <c>: <routine> <instruction> and move on to the next instruction;
2. if the routine has now run all its instructions: if it is main, stop the program; otherwise pop the routine it interrupted off the stack and print return to <routine> at <instruction>;
3. add this cycle's arrivals to pending; if the highest-priority pending interrupt has a priority greater than the running routine's, remove it from pending, push the running routine onto the stack, print interrupt <name>: saved <routine> at <instruction>, and start that ISR at instruction 0.

Build every line from your variables. The robot stays still.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

MAIN_LENGTH = 6
ISR_LENGTH = 2
arrivals = {1: [("printer", 1)], 2: [("power", 3)], 3: [("keyboard", 1)], 4: [("timer", 2)]}

stack = []
pending = []

Challenges

1. Trace the task's data by hand before running it. At which cycle does the keyboard interrupt finally start, and why so late?
2. Change the rule to "greater than or equal to". What changes in the trace, and why is that a bad idea?
3. How deep does the stack get? Add a line that prints the largest stack size, and invent arrivals that make it deeper.