Programmed I/O, Interrupts & DMA

The speed gap

A CPU runs billions of cycles per second. A keyboard delivers a few characters per second, and even a fast disk is much slower than the CPU. So the question is: how does the CPU get data from a slow device without wasting its time? There are three classic answers, from simplest to smartest.

In the model a device delivers one word every 6 CPU cycles. The strip at the front shows what the CPU does in each cycle.

1. Programmed I/O (polling)

The CPU does everything itself:

for each word:
    while device.status != READY:   # busy-wait
        pass
    R = device.data
    memory[buffer + i] = R

Every check that finds the device not ready is a wasted cycle (red in the model). It is simple and needs no extra hardware, but the CPU can do nothing else until the transfer is finished.

2. Interrupt-driven I/O

The CPU starts the device and goes back to its own work. When a word is ready, the device raises an interrupt request (IRQ):

1. The CPU finishes the current instruction. It never stops halfway through one.
2. It acknowledges the interrupt and saves the PC and status flags on the stack.
3. It looks up the address of the interrupt service routine (ISR). With vectored interrupts the device supplies a number that indexes a table of ISR addresses.
4. The ISR copies the word into memory.
5. RETI (return from interrupt) restores the flags and PC, and the program carries on as if nothing happened.

There is no waiting any more, but every word costs a context switch: about 4 cycles in the model, and often hundreds of cycles on a real machine. Interrupts can also have priorities, and maskable ones can be switched off for a short time. A non-maskable interrupt (NMI) is kept for emergencies such as a hardware failure.

3. Direct memory access (DMA)

A DMA controller is a small piece of hardware that copies data between a device and memory by itself. It has an address register, a count register and a control register.

1. The CPU programs the DMA: where the buffer is, how many words, and in which direction.
2. When the device has a word, the DMA asks for the bus (HOLD, or bus request BR).
3. The CPU finishes its current bus cycle and grants it (HLDA, or bus grant BG).
4. The word goes straight from the device to memory, without passing through the CPU. The address goes up by one, the count down by one.
5. When the count reaches 0, the DMA raises one interrupt for the whole block.

DMA has three modes:

Side by side

The same 4 words, one every 6 cycles, measured over 28 cycles:

Code

def timeline(method, words=4, period=6):
    """What the CPU does in each clock cycle while a device delivers `words` words,
    one every `period` cycles."""
    end = words * period + 4                  # the same time window for every method
    ready = [(k + 1) * period for k in range(words)]
    cpu, k, t = [], 0, 0
    if method == 'dma':
        cpu += ['io', 'io']                   # program the DMA controller
        t = 2
    while t < end:
        if method == 'polling' and k < words:
            if t < ready[k]:
                cpu.append('poll'); t += 1    # "ready yet?"  (wasted)
            else:
                cpu += ['io', 'io']; t += 2   # read the device, store to memory
                k += 1
        elif method == 'interrupt' and k < words and t >= ready[k]:
            cpu += ['ctx', 'io', 'io', 'ctx'] # save state, ISR copies the word, RETI
            t += 4; k += 1
        elif method == 'dma' and k < words and t == ready[k]:
            cpu.append('stolen'); t += 1      # DMA borrows the bus for one cycle
            k += 1
            if k == words:                    # block done: one interrupt
                cpu += ['ctx', 'io', 'ctx']; t += 3
        else:
            cpu.append('user'); t += 1        # the CPU's own program
    return cpu[:end]

for m in ('polling', 'interrupt', 'dma'):
    c = timeline(m)
    print(f"{m:9} user program got {c.count('user')} of {len(c)} cycles")
# polling   user program got 2 of 28 cycles
# interrupt user program got 12 of 28 cycles
# dma       user program got 19 of 28 cycles

Common mistakes

• Thinking DMA makes I/O free for the CPU. The CPU still sets up the transfer, handles the final interrupt, and loses bus cycles while the DMA uses the bus.
• Thinking an interrupt stops an instruction halfway. The CPU checks for interrupts between instructions.
• Forgetting to save the state. Without saving the PC and flags, the interrupted program could not continue correctly.
• Thinking polling is always bad. It is fine when the device is very fast or the CPU has nothing else to do. Busy network cards are sometimes polled to avoid an interrupt storm.
• Using DMA for a single byte. The setup cost is only worth it for blocks of data.