Mark Smotherman
Last updated: July 2008
Summary: Interrupts are a vital part of sequencing a modern computer. They were developed for exception handling and were later applied to I/O events. Today, they also also play a role in protection and memory management. However, interrupts can be disruptive to both program design and to high performance.
.. under construction ..
Machines discussed:
Univac-I (1951) - overflow trap
NBS DYSEAC (1954) - I/O interrupt
Univac 1103/1103A (1955 innovation) - wind tunnel interrupt
IBM 704 (1955) - transfer trap (for debugging)
IBM Stretch (1957 paper) - vectored interrupt system
Lincoln Labs TX-2 (1957 paper) - multiple-sequence system
Electrologica X-1 (1957-1958 innovation)
- vectored interrupt system
Manchester Atlas (1961) - page fault
Comments on interrupts
Strachey
Denning
Dijkstra
Hardy
Deferred interrupt handler structure
In my 1989 paper, "A Sequencing-Based Taxonomy of I/O Systems and Review of Historical Machines," Computer Architecture News, vol. 17, no. 5, pp. 5-15, September 1989 (and reprinted as Paper 1 of Chapter 7, in M. Hill, N. Jouppi, and G. Sohi (eds.), Readings in Computer Architecture, Morgan Kaufmann, San Francisco, 2000),
(cf. SWAC with a 4th address in the instruction used to specify a
branch address on overflow)
In the context of arithmetic overflow handling in the UNIVAC I,
Codd states,
"in the NBS DYSEAC the very significant step was made of
extending interruption to input-output operations."
[E.F. Codd, "Multiprogramming," pp. 77-153, in F.L. Alt and
M. Rubinoff (eds.), Advances in Computers, Vol. 3. New York:
Academic Press, 1962.]
... versus ...
[discussing interlocks]
Thus the assigned priority levels are not under program control and
cannot change during execution.
Memory included:
Also, the X-1 could provide:
At that point, the predefined subroutine call instruction corresponding
to the interrupt class was inserted into the instruction register.
Executing this instruction formed a link word (note the contents listed
above), which was saved into the corresponding word in low memory, and
control was transferred to the interrupt handler.
The interrupt handler began execution with interrupts disabled ("not
susceptible"). The interrupt handler had the responsibility of saving
the A, S, and B registers and then reading the class word. All bits
(i.e., interrupt request signals) in the class word would be reset upon
the read.
The enable bit and permit bits could be individually set and reset
under program control to provide for disabling all or some of the
interrupts. This allowed for a priority system among classes.
Returning from the interrupt handler was accomplished by use of a
"restoring jump" which restored the information from the saved link word.
Christopher Strachey, "Timesharing in Large Fast Computers,"
International Conference on Information Processing, June 1959, Paris,
pp. 336-341 [IFIP conference; the proceedings were published by UNESCO
in 1960].
... to be added ...
Peter J. Denning, "Principles for Reliable Operating Systems,"
January 28, 2003
Norm Hardy's history of interrupts
(adapted from Blaauw and Brooks, section 7.4, on interrupts)
on another note, Rob Warnock writing in comp.arch on 16 Jul 2001:
(E.g., see US 3,789,365 issued January 1974 and US 4,342,082
issued July 1982)
In this section I want to trace the development of the idea of
"bottom half" or "deferred" interrupt handlers
(a.k.a. fork routines, interrupt queueing, interrupt stacking, as well as
the term "Cutler kernel" structure).
The idea is that a "first half" interrupt handler dynamically creates
a new thread or "fork routine" for later scheduling and execution, as
opposed to an interrupt handler that runs to completion or a barebones
interrupt handler that merely awakens a previously-created driver process.
(For example, in RSX-11M, interrupt handlers fork a routine for later
execution by adding a four-word fork block to a FIFO fork queue. The
fork routines must be executed before any user processes are scheduled.)
Motivations:
The idea appears to date from at least the early 1960s with the
soft-real-time monitor developed for the Project Mercury space program.
[See the discussion of "Cutler kernel" in
Bruce R. Montague, "JN: An Operating System for an
Embedded Java Network Computer," UCSC-CRL-96-29, 1996.]
Fred Brooks said that having to stack interrupts influenced Seymour Cray
to design the CDC 6600 with polling rather than interrupts.
CDC 3600
two systems with deferred handling are cited by Richard Watson in
Timesharing System Design Concepts, 1970, pp. 126,144:
genealogical tree involving Dave Cutler
Linux deferred handlers
See Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman,
Linux Device Drivers,
Third Edition
...
Hardware support in x86
Corrections are welcome!
[History page]
[Mark's homepage]
[CPSC homepage]
[Clemson Univ. homepage]
[email protected]
However, the rest of the story includes
The computer reacts to an "overflow" situation automatically. The
sequence of instructions is interrupted, and the pair of instructions
in memory location 000 is inserted. This insertion is effected after
both instructions of the original pair have been executed even though
overflow may have been caused by the first instruction of the pair.
If memory location 000 contains an instruction which transfers
control, a new sequence is initiated. It is important to note that,
if no transfer of control is ordered, the original sequence of
instructions is resumed after executing the pair contained in 000.
There is a rudimentary interrupt system for machine errors. When the
stop condition of the Machine Error indicator in [sic] not enabled by
its mask switch, it causes a trap. The next instruction is now taken
from the console switches, word 8000, instead of from the specified
location. There is no status preservation whatever; there is no way
to know where the offending trap occurred. Moreover, the Distributor
and Accumulator are reset; the main purpose is to get a fresh restart
after an intermittent error.
Each input-output instruction ... indicates whether or not a
Program-Jump operation is desired after completion of the
input-output operation. If a Program-Jump is desired, then a
signal is produced after the input-output operation is completed
which causes the program to jump, i.e., the counter-register being
used as the source of the next instruction is temporarily
abandoned, and the instruction word in the address specified by
the other counter-register is executed in its stead. ...
After effecting a program-jump, the new program that is initiated
may, as soon as its final instruction is performed, cause the
machine to resume the interrupted program where it left off, if
the programmer so desires.
...
It might be noted again that any consecutive areas of the memory in
DYSEAC, ranging in size from a single word to the entire memory, can
be loaded or printed out even while a program of computation is
proceeding. Automatic interlocks are provided to guard against
inadvertent attempts to use a memory location for conflicting
purposes. For example, if a print-out order is given, the machine
is automatically prevented from writing into any memory location
affected by the print-out order until the word in that location
has been printed out.
...
The Concurrent Input-Output Control has the function of regulating
the detailed progress of all input-output operations requested in
the course of the internal program. It directs the flow of traffic
between the memory and the Input-Output Buffer, ....
It receives signals from the Input-Output Buffer as each complete
word is transferred, and it not only keeps count of the total number
of words handled, but also keeps track of which address in the
high-speed memory contains the word currently to be transferred.
This information is transmitted to the Memory Address Switches at
the proper time.
In the comparatively unlikely event that both the Input-Output Buffer
and some internal unit should simultaneously demand access to the
high-speed memory, the Concurrent Input-Output Control resolves the
conflict by according temporary priority to the external operation.
Likewise it referees conflicts or inconsistencies between the internal
program and the progress of external operations. It also notifies the
Program Control unit at the termination of an input-output operation
so that the program-jump may take place.
For example, if the programmer directs that a given section of the
memory be loaded from an external input unit and then some time
afterwards directs that the contents of a memory location in this
section be used as the source of an instruction, the program will
automatically be temporarily halted until the sought-for memory
location has actually received the word intended for it from the
input unit.
The clever feature was that rather than requiring the processor to use
its precious time, swapping memory in and out of the drum storage space,
the transfers would be automatically done on demand. This was implemented
using another clever technique. If a request was made for data not
currently in the core memory, an interrupt, (then called an extracode
instruction), was called. This paused the execution of the program, and
automatically loaded the page of memory which the data was in, (a page
being a 512 word block of memory).
(http://hoc.co.umist.ac.uk/storylines/compdev/commercialisation/atlas.html)
A further optimisation to this technique was also implemented. Rather
than check for every instruction to ensure it is in core memory, which
would largely waste time, as the sequential nature of instruction reads
means they are more than likely to be in the current page, a different
method was used. They eliminated the check for each instruction, and
instead implemented an exception handler to deal with the error accesses.
Strachey's comments on interrupts
Denning's comments on interrupts
Dijkstra's comments on interrupts
In this connection the history of the real-time interrupt is
illuminating. This was an invention from the second half of the 50s,
which enabled the completion of a communication with the external
world to interrupt the execution of one program in favour of another.
It's advantage was that it enabled the implementation of rapid
reaction to changed external circumstances without paying the price
of a lot of processor time lost in unproductive waiting. The
disadvantage was that the operating system had to ensure correct
execution of the various computations despite the unpredictability
of the moments at which the interrupts would take place and the
central processor would be switched from one computation to another;
the nondeterminism implied by this unpredictability has caused
endless headaches for those operating system designers that did
not know how to cope with it. We have seen two reactions to the
challenge of this added complexity.
The one reaction was to enhance the debugging facilities, as IBM
did for the design of OS/360. (This was the operating system IBM
tried to design for its 360-Series of machines, which were introduced
in the first half of the 60s; IBM's problems with this design
facilitated in 1968 the recognition of the world-wide phenomenon
that became known as "the software crisis".) IBM built, in fact,
special-purpose monitors that exactly recorded when the central
processor honoured which interrupt; when something had gone wrong,
the monitor could be turned into a controller, thus forcing a
replay of the suspect history and making the "experiment" repeatable.
The other reaction could be observed at the THE (Technological
University Eindhoven), viz. to determine the conditions under which
one could feasibly and safely reason about such nondeterministic
programs and subsequently to see to it that these conditions were
met by hardware and software.
The difference was striking, showing once more that debugging is
no alternative for intellectual control. While OS/360 remained a
mess forever after, the Multiprogramming System designed at the
THE was so robust that no system malfunction ever gave rise to a
spurious call for hardware maintenance. Needless to say, the whole
episode has made a lasting impression on me.
One moral is that the real-time interrupt was only the wave,
whereas the tide was the introduction of nondeterminism and the
development of the mathematical techniques to cope with it.
The third arrangement, known as "the interrupt", circumvents all
these dilemmas. While the computer calculates at full speed, a
piece of dedicated hardware monitors the outside world for
completion signals from communication devices. When a completion
is detected, the program under execution is interrupted after the
current instruction and in such a fashion that it can be resumed
at a later moment as if nothing had happened, thus instantaneously
freeing the central processor for a suddenly more urgent task.
After the interrupt the processor would execute a standard program
establishing the source of the interruption and taking appropriate action.
It was a great invention, but also a Box of Pandora. Because the
exact moments of the interrupts were unpredictable and outside our
control, the interrupt mechanism turned the computer into a
nondeterministic machine with a nonreproducible behavior, and
could we control such a beast?
In the mean time a pattern emerged for the cooperation between me
and my hardware colleagues Bram J. Loopstra and Carel S Scholten.
After the functional specification of the next machine had been
written down (usually by me), that document served as a kind of
contract between us: it told them what machine to design and
construct, while I knew what I could count upon while writing
all the basic software for the machine. The target of this
division of labour was that my programs would be ready by the
time the construction of the machine had been completed.
Looking back I now observe that the above arrangement has had
a profound influence on how I grew up as programmer: I found it
perfectly normal to program for not yet existing machines. As a
byproduct it became firmly ingrained in my mind that I programmed
for the abstract machine as specified in the original document,
and not for the actual piece of hardware: the original document
was not a description but a prescription, and in the case of a
discrepancy not the text but the actual hardware would be at fault.
...
Of course I could not exclude from my designs typographical errors
and similar blemishes, but such shortcomings did not matter as long
as the machine was not ready yet, and after the completion of the
machine they could be readily identified as soon as they manifested
themselves, but this last comforting thought was denied to me in 1957
with the introduction of the real-time interrupt. When Loopstra and
Scholten suggested this feature for the X1, our next machine, I got
visions of my program causing irreproducible errors and I panicked.
Eventually, Loopstra and Scholten flattered me out of my resistance
and I studied their proposal. The first thing I investigated was
whether I could demonstrate that the machine state could be saved
and restored in such a way that interrupted programs could be
continued as if nothing had happened. I demonstrated instead that
it could not be done and my friends had to change their proposal.
Admittedly the scenarios under which the original proposal would
fail were very unlikely, but this can have only strengthened my
conviction that I had to rely an arguments rather than on experiments.
At the time that conviction was apparently not so widespread, for
up to seven years later I would find flaws in the interrupt hardware
of new commercial machines.
Hardy's comments on interrupts
Design Tree
Performance techniques
As far as the areas that I've been personally involved in -- mostly
high-speed networking -- the best hardware/software tradeoffs have been
mostly just judgment calls by very experienced folks. What I've noticed
is that a *LOT* of "lessons learned" decades ago are still being re-learned
by later generations, over and over again. We as an industry don't seem
to have been doing a very good job of passing on the "secret sauce" to
subsequent generations [in many cases, even *within* the same companies!].
For example, way back in the early 1970s at Digital Communications
Assoc. (in Atlanta, made communications front-ends for DEC PDP-10s
and IBM 360s using DEC PDP-8e's, successfully sold in *competition*
with DEC's own PDP-11-based front-ends!], we made simple interrupt-per-
character PIO-based terminal controllers that were -- in terms of host
CPU cycles -- *more* efficient (and a lot cheaper!) than DEC's complex
DMA-based controllers, partly because we used three simple techniques,
two programming and one hardware: (1) interrupt "coalescing", (2) "dallying"
before dismissing an interrupt, and (3) interrupt "holdoff". That is,
(1) during a single interrupt, process *all* of the data that's available or
that *becomes* available (looping to repeat the availability test as needed)
during a single interrupt; (2) spin-wait/test a certain amount (which may
even be context/data-dependent!) before dismissing an interrupt, so as to
catch new data and process it without having to dismiss/interrupt again;
and (3) once you finally *do* dismiss an interrupt, arrange the hardware
so that you won't get another one until a certain (sometimes dynamically)
chosen time interval has expired (also known as "interrupt rate-limiting",
which, together with the other two, prevents "thrashing" in the interrupt
service routine).
[There's another variant of #2 that's worth mentioning: when doing PIO
writes to a FIFO and hitting a FIFO-full condition, "dallying" (spin-waiting)
a certain amount first rather than enabling a watermark interrupt and
going away. If you pick the dally amount appropriately, by "wasting" a
few cycles you actually can save *lots* of total CPU time, since you
(hopefully) avoid a later heavy-weight interrupt/context-switch/dismiss.]
These techniques were *NOT* unique to DCA!! In talking to other engineers
at conferences & trade shows, we learned that such things were generally
widely known among workers in the field (especially embedded systems,
datacomm, and real-time folks), but were not often discussed openly,
being considered somewhat "trade secrets". [That is, why tell your
competitor why his performance sucks and yours doesn't?!?]
In the 30+ years since then, I've been astounded how many times the
techniques of coalescing/dallying/holdoff have been rediscovered, but
I've been *more* astounded how many times they haven't been used *at all*
in many places where they were definitely needed, or how they were
reinvented badly. [E.g., if you're implementing hardware assistance
for interrupt holdoff, it is *extremely* important that the holdoff
period be effective only *after* the dismissing of an interrupt, and
not delay the response to or processing of a "new" event that arrives
when the system has been idle for longer than the holdoff.] "Computer
Science" courses don't seem to ever discuss such practicalities, either.
Deferred interrupt handler structure
Montague, op cit., also mentions the IBM TSS (mid-1960s) as using
deferred handling.
