Handing I/O

Before There Were Interrupts

Here's a diagram of the hardware of an early computer system (modern ones are much the same, although the I/O devices would be different—your phone has a touch screen, not a tape drive).

The key aspect is that the CPU can talk to both memory (where it gets its instructions and data) and I/O devices (like disks, tape drives, and printers). All the hardware is connected together over a common communications channel known as the system bus.

In early computers (without much, if any, of an operating system), the easiest way to work with an I/O device was to ask it to do something and then wait for it to be done.

Python pseudo-code for this would look like

def read_from_disk(diskno, sectorno):
    disk_controller.send_command(cmd="read", disk=diskno, sector=sectorno)
    while not disk_controller.is_done():
        pass
    return disk_controller.get_data()

This approach is known as busy waiting, because the program is essentially repeatedly asking, “Are we there yet?” until the disk controller says, “Yes”. Below is a timing diagram of this process.

Polling Is Inefficient

The problem with busy waiting is that it's inefficient. The CPU is doing nothing while waiting for the disk controller to finish, which is a waste of CPU time that could be used to do other work.

Also, if the CPU constantly polls the I/O device, it would dominate the system bus and perhaps distract the disk controller from doing its work. So the CPU generally needs to wait a short time between polls. But now there can be a delay between when the disk controller finishes and when the CPU notices it's done. Depending on the system, it's also possible for the disk controller to be idle until the CPU notices that it's finished, thus wasting its time, too.

Interrupts

An interrupt is a signal to the CPU that an event has occurred that needs immediate attention. The CPU can then stop what it's doing, save its state, and jump to a special piece of code called an interrupt handler that deals with the event.

A Clock/Timer Interrupt

Let's set aside the disk device for a moment and imagine a different device: a clock. The clock device is going to help the computer keep track of the passage of time by sending a tick interrupt to the CPU every second.

When the CPU receives the tick, it stops what it's doing, saves its state, and jumps to the interrupt handler for the clock. The interrupt handler can then update the system time and do anything else that needs to be done every second.

A tick interrupt is one of the simplest kinds of interrupt. We didn't do anything to cause it, and there's nothing we need to ask the clock when we get it (the clock could tell us the time, but with a tick every second, we can just keep track of the time ourselves).

A Disk Interrupt

Let's go back to the disk device. With interrupts, instead of our program busy waiting for the disk controller to finish, once the request is sent, the CPU can go off and do other work (i.e., the kernel can schedule another process to run). Let's call the original program “Program A” and the second “Program B.”

When the data is ready, the disk controller sends an interrupt to the CPU. The CPU stops what it's doing, saves its state, and jumps to the interrupt handler for the disk. The interrupt handler can then read the data from the disk controller.

We now have a choice, because we have two programs that are both able to run, Program A, whose data is now ready, and Program B, which was running when the interrupt happened. Which program to run next is a scheduling decision.

Trade-offs

For I/O-related interrupts like our disk example, here are some of the trade-offs:

• We want interrupt handling to be quick, not least because while we're handling one interrupt, we won't be noticing any others. So we want to resume normal execution as soon as possible.
• When a higher-priority process becomes able to run, we want it to resume running quickly.
• We want to avoid starvation, where a process never gets to run because there's always something more important to do.

Process prioritization and the decision of what to run next is the job of the process scheduler (which we'll discuss later). In timesharing systems (including Linux, macOS, Windows, and OS/161), the scheduler is invoked regularly by a timer interrupt, so there is little advantage to specifically calling the scheduler from an I/O interrupt handler.

To make interrupt handling fast, a common approach is to have the interrupt handler be as minimal as possible, grabbing data and stashing it away. If the data needs additional processing, an internal task inside the kernel (known as a tasklet in Linux) can be scheduled to do the work.

Polling vs. Interrupts

Suppose, for example, that we're downloading an OS update that is 1 GB in size and it takes 100 seconds. If we get an interrupt for every network packet, there will be 1 million interrupts, or about 10,000 per second. That's a lot of interrupts! It might be more efficient to poll the network card every 10 ms to collect all the packets that have come in since the last poll. (We will need the network card to be able to buffer packets for us, but that's a reasonable assumption.)

Reminder: Application Code and I/O

The idealized machine that the operating system provides in the form of processes is synchronous. From a user program's perspective, a call to read just waits for the data to be ready, and then returns it. The fact that behind the scenes the program was stopped and then restarted is invisible to the program.

(When logged in, completion status appears here.)