virtualirfan

History of Interrupts

This article is all about the fascinating history of computer system interrupts. See also this video which walks you through this history.

The use of interrupts goes back to the early days of computers. So, what is an interrupt? Let’s take a look at an example. WhatIsAnInterruptAn IO controller, for example, a network or storage controller is like an external embedded computer to the main processor. Here, time is on the x-axis. At some point in time, the IO controller will complete it’s pending, previously issued work. It will then send an “interrupt” to the main processor which is running a user-level process. Immediately, the main processor will vector (lookup) the interrupt to find a piece of code which will execute in interrupt context to handle the interrupt. Typically, this is a low-level driver. Further, typically some work will be queued for the kernel to perform in response to the thing that the IO controller just informed the drive and kernel about having just completed. This could be an disk IO that has just completed and needs to be sent to the user process that started it. Or an incoming network packet. Now, the process continues on.

“It was a great invention, but also a Box of Pandora”
E.W. Dijkstra EWD 1303

FWIW: the capitalization is Dijkstra’s, not mine, from his manuscript #1303. Interestingly, Dijkstra’s work on interrupts is circa 1957 and the machine that he worked on then was the Electrologica X-1. If this is not the first time you’re hearing about the Electrologica X-1, you are awesome.

ElectrologicX1Let’s see if a picture can help jog your memory. Even if you’ve heard of it, I’m guessing none of my readers has actually programmed an an X-1. If you have, please email me. I’d love to interview you or buy you coffee or whatever it is that you drink! You deserve it. Turns out that the X-1 is a very interesting machine from a historical perspective.

Anyway, let’s get back to interrupts. So, I said that Dijkstra worked on interrupts for the X-1. Here’s what he had to say about it:

“Halfway the functional design of the X1, I guess early 1957, Bram [J. Loopstra] and Carel [S. Scholten] confronted me with the idea of the interrupt, and I remember that I panicked, being used to machines with reproducible behaviour. How was I going to identify a bug if I had introduced one?”

“After I had delayed the decision to include the interrupt for 3 months, Bram and Carel flattered me out of my resistance, it was decided that an interrupt would be included and I began to study the problem.”
E.W. Dijkstra EWD 1303, Dijkstra’s PhD dissertation (on X-1)

Despite this, he went on to design the interrupt handler scheme for the X-1. According to his manuscripts, it comprised about 900 instructions. This is part of the work in his Ph.D.

Well, I guess it turns out that computers didn’t always have interrupts then … actually, Donald Knuth credits Djikstra with the independent invention of an interrupt system but historically Edsgar Dijkstra was not the first one.

So, let’s look at a timeline here.

HistoryOfInterrupts

In actual fact, in 1954, the NBS DYSEAC was the first one to have an I/O interrupt. There were machines before that had traps, for example the UNIVAC-1 had an overflow trap but not an IO interrupt.

Circa 1955 UNIVAC 1103A were wired up to wind tunnels. Really interesting use case for the early days using interrupts for real-time data collection.

To get to the time when Dijkstra was working on this problem, we have to fast forward to 1957. He published his dissertation in 1959 on the work he did on the X-1. Electrologica X-1 had the really nice vectored interrupt system same design pattern we see today. So, around the same time, computer pioneers were working on these new architectures independently in United States and Amsterdam. The IBM Stretch (which I believe there is one of at the Computer History Museum) and Lincoln Labs TX-2 are examples of work in the US. The TX-2 had nested interrupts and critical sections support built into the ISA itself. Recall that the famous SketchPad was built on the TX-2. See this amazing video about it with Ivan Sutherland.

SketchPad ran on Lincoln Labs TX-2

So, by 1960 pretty much every machine being built has interrupt support. Those that don’t are deliberate design choices, for experiments to try out alternatives to interrupts or for the simplicity of polling like a couple of the Cray machines.

In the 1960s, deferred interrupt handling starts to get used. You see this optimization in modern OS kernels including Linux kernel.  I’m not sure why this technique has been dropped and picked up again over history.

By 1966, you have the Burroughs B5500 which adds an instruction to test for additional interrupts before returning from the handler.

Burroughs5500-brochure-1

Snipped from a Burroughs 5500 product brochure (Computer History Museum)

By early 1970s, three interrupt overhead optimization design patterns have already emerged. And these will remain essentially unchanged for the next 30 years.

  • On an interrupt, try to complete more than one IO (a cousin technique of what the B5500 did with a new interrupt instruction).
  • Spin wait a little bit before dismissing the handler. Not a very common technique but definitely mentioned in literature.
  • After dismissing the interrupt, get the hardware IO controller to delay the next interrupt.

The first two are OS techniques and the third is in the IO controller with co-operation with the OS.

During the 1980s, we see high-speed devices really take off with Ethernet and SCSI. The resulting research yields very interesting designs and dozens of patents in this area. To this day, network interrupt handling techniques are obeying the same framework of the 1970s and trading off essentially the same set of parameters.

  • Maximum Interrupt Delay Latency (MIDL). Like a deadline: once the controller receives a hardware completion, how long it is allowed to wait till it will interrupt the processor. The idea being the delay is to limit the number of times a second an interrupt can occur and to get lucky with more hardware completions arriving within a specified time period.
  • Maximum Coalesce Count (MCC). The number of hardware completions before the IO controller will provide a delivery of interrupt to the processor.

Throughout the 80s, 90s and 00s, dozens of patents in networking are filed finding interesting ways to combine these two parameters and also to dynamically modify these basic parameters.

The same is also true for storage until 1998 when the earliest example of fundamentally changing the rules I could find enters the filed. This is with an LSI Logic patent filed in 1998. They changed the rules, instead of looking at MIDL and MCC, they instead looked at the commands in flight (CIF) and use that to set the delay time. This trick is possible since for a storage IO, you actually know that an IO command is outstanding.

vICDynamicFast forward to 2008, after 60 years of experiments in this area, and you find my work. I counted 4 Turing laureates who appear to have, at some point of time or another, contributed to interrupt processing including Edsger W. Dijkstra, John McCarthy, Fernando J. Corbató and Butler W. Lampson. Talk about building on the shoulders of giants and an exercise in humility. At a recent ACM event, I had the pleasure of meeting Corbató but more about that in a different post.

When I was working on this interrupt coalescing work in context of a hypervisor while at VMware, I was unaware of the LSI Logic patent mentioned above. In hindsight, we had the same intuition as them but we took it a completely different direction. We used CIF to set fine-grained delivery ratios where LSI Logic uses CIF to set fine-grained hardware timers. Our technique therefore eliminated the need for high-resolution timers needed inside the embedded systems hardware of the IO controller. By not using high-resolution timers, our system is the first sophisticated interrupt coalescing technique to not need dedicated IO controllers (with their own hi-res timers) for implementation. Note that high-resolution timing is not practical on general purpose microprocessors because a timer firing is in itself an interrupt. You can’t justify using high-resolution timers (which means more interrupts) to implement a technique which is designed to reduce interrupts. A quick overview here with more details in the paper itself.

So, you just had a whirlwind tour of the history of interrupts. My primary source for this were the excellent set of notes put together by Mark Smotherman at Clemson. Many thanks to him. I also looked up old manuscripts and manuals to learn more about some of these techniques but I don’t have all the links handy. If I ever write a more lengthy article on this topic, I’ll try to gather more interesting sources.

Since you’ve made it down this far, be sure to watch this video.

Leave a Reply

Your email address will not be published. Required fields are marked *