Digital Computer Structure

381-1-0103
1

Lecture 5 – Interrupts

Shlomo Greenberg

Web site: http://moodle2.bgu.ac.il

2 Interrupts - Background
 Interrupts
3

 Definition: an event external to the

currently executing process that causes
a change in the normal flow of
instruction execution; usually generated
by hardware devices external to the CPU
From “Design and Implementation of the FreeBSD Operating
System”, Glossary
 Key point is that interrupts are
asynchronous w.r.t. current process
 Typically indicate that some device needs
service
 Why Interrupts?
4

 People like connecting devices

 A computer is much more than the CPU
 Keyboard, mouse, screen, disk drives
 Scanner, printer, sound card, camera, etc.

 These devices occasionally need CPU service

 But we can’t predict when
 External events typically occur on a
macroscopic timescale
 we want to keep the CPU busy between events
 => Need a way for CPU to find out devices
need attention
Interrupts - Background
 Interrupts are primarily to support
the OS – it allows a program to be
suspended and later resumed (e.g.
for printing, I/O, and more)
 Another way to look at that -

synchronize micro-computer with the

“outer world”
 Possible Solution: Polling
6

 CPU periodically checks each device to

see if it needs service
 Cons: takes CPU time even when no
requests are pending. Overhead may be
reduced at the expense of response time
 Pros: can be efficient if events arrive
rapidly
“Polling is like picking
up your phone every
few seconds to see if
you have a call. …”
 Programmed I/O - Polling
7

 Basically, start device

and poll for completion
 Looping on “poll on input
status” and wait until
device is ready
 Pros: simple
implementation
 Cons: loops, waste of
cycle count
 Alternative: Interrupts
8

 Give each device a wire (interrupt line)

that it can use to signal the processor
 When interrupt signaled, processor
executes a routine called an interrupt
handler to deal with the interrupt
 No overhead when no requests pending
(IRQ)
 Interrupt I/O
9

 Basically, an interrupt is connected to a

service routine pointer. Once an
interrupt occurs, registers and flags are
saved, routine is executed and then
return from interrupt (recover registers
and flags)
 Pros: Minimal time
 Cons: Complex implementation
 Polling vs. Interrupts
10

“Polling is like picking up your phone every

few seconds to see if you have a call.
Interrupts are like waiting for the phone to
ring.”

 Interrupts win if processor has other

work to do and event response time is
not critical
 Polling can be better if processor has to
respond to an event ASAP
 May be used in device controller that
 Hardware Interrupt
11
Handling
 Interrupt controller signals CPU that interrupt has
occurred, passes interrupt number
 Interrupts are assigned priorities to handle simultaneous
interrupts
 Lower priority interrupts may be disabled during service
 CPU senses (checks) interrupt request line after every
instruction; if raised, then:
 uses interrupt number to determine which handler to start
 interrupt vector associates handlers with interrupts
 Basic program state saved (as for system call)
 CPU jumps to interrupt handler
 When interrupt done, program state reloaded and
program resumes
Remark: Details are architecture depende
 CPU’s ‘fetch-execute’
cycle
User
Program
Example
Fetch instruction at IP
ld
add
Decode the fetched instruction Save context
IP st
mul
Get INTR ID
ld Execute the decoded instruction
sub
Lookup ISR
bne
add Advance IP to next instruction
Execute ISR
jmp
…
Interrupt? yes IRET

no
 Interrupt Sequence
13

 Current instruction finishes execution

 Flags are pushed on the stack
 Disable maskable interrupts & single Interrupt
step Latency*
 Save current CS & IP on the stack
 Read new CS & IP (address of interrupt
routine) from interrupt vector table (IVT)
 Jump to interrupt routine
 Execute interrupt routine
 Pop registers and flags
 Remark:
Pop CS & IP from stack Interrupt latency includes also wait
states till interrupt routine is being served (e.g.
 Jump back in order to accumulate interrupts as in interrupt
controller – wants to react every frame and not
 Which interrupt address is
14
being served?
 Pre-defined

 Jump to a specific address included in

the interrupt

 Using interrupt vector table (IVT)

 Interrupt Vector Table (IVT)
15

 A data structure that associates a list of interrupt

handlers with a list of interrupt requests in a table
of interrupt vectors. Each entry in the IVT is the
address of the interrupt handler.
 While the concept is common across processor
architectures, each IVT may be implemented in an
architecture-specific fashion.
 When the CPU is affected by an interrupt, it looks
up the interrupt handler in the IVT, and transfers
control to it.
Interrupt Interrupt
Request #1 Handler #1
Interrupt Interrupt
Request #2 Handler #2
… …
 Handling Methods
16

 An IVT is used in several methods of finding

the starting address of the interrupt service
routine (ISR):
 Predefined - The program counter (PC) is loaded
directly with the address of the entry in the IVT.
Each entry has the code "JMP address" with the
address of the ISR for that interrupt. E.g.: Atmel
AVR and all 8051 and Microchip microcontrollers.
 Fetch - PC is loaded indirectly, using the address
of some entry inside the IVT to pull an address
out of that table, and then loading the PC with
that address. Each entry is the address of the ISR.
E.g.: Motorola/Freescale microcontrollers.
 Interrupt Vector Table (IVT)
17
in 8086
 1KB in RAM that serve 256
interrupt routines.
 Each interrupt type uses 4B to
store IP:CS, where IP is 2B and
CS is 2B
 Challenges:
 Starts with 0x0, so reset cannot
reside in address 0x0
 Uses erasable RAM => need to
load each time
 Programmer responsibility to
program the IVT based on the
routine number that he has
associated with the interrupt
18 Interrupt Types
Types of Interrupts
 Software Interrupts (also called exceptions)
 Programmed exceptions:
 Request for kernel intervention (software intr/syscalls)
 Processor-detected exceptions:
 Fault — correctable; offending instruction is retried
 Trap — often for debugging; instruction is not retried
 Abort (error exception) — major error (hardware
failure)
 Hardware Interrupts
 From external source, such as I/O device, hence
asynchronous
 Not related to instruction being executed
 Either maskable (IRQ) or non-maskable (NMI)
 Programmed Exceptions
20

 Triggered via software, and usually used IVT to

know the address of the ISR to jump to.
 in x86, Initiated with an INT instruction. E.g., INT
33h issues the interrupt with the hex number 33h.
 In x86, Uses IVT of 1KB, 256 entries and a
mechanism of offset:segment.
 Always synchronized with the program
execution. I.e. every time the program gets to
a point where there is an INT instruction, an
interrupt is issued. This is very different from
hardware interrupts and processor-detected
exceptions.
 Programmed Exceptions
21
Advantages
 Hardware independent
 Relocatable code
 Efficient use of the system
 Multitask support
 Less code redundancy
 Programmed Exceptions -
22
Example
 Processor-Detected
23
Exceptions
 Processor-Detected Exceptions originate in
the processor itself.
 The production corresponds to that of a
software interrupt, i.e.: an interrupt
whose number is set by the processor
itself is issued.
 Generally, occur when the processor can't
handle alone an internal error caused by
system software.
 There are three main classes: Fault, Trap
and Abort.
Faults
 A fault issues an exception prior to completing the
instruction. The saved IP value points to the same
instruction that created the exception. The IP can
be reloaded and the processor can re-execute the
instruction, hopefully without another exception
 Instruction would be illegal to execute
 Examples:
 Writing to a memory segment marked ‘read-only’
 Reading from an unavailable memory segment (on disk)
 Executing a ‘privileged’ instruction
 The causes of ‘faults’ can often be ‘fixed’. If a
‘problem’ can be remedied, then the CPU can just
resume its execution-cycle
Traps
 A trap issues an exception after
completing the instruction execution.
The saved IP points to the instruction
immediately following the one that gave
rise to the exception. The instruction is
not re-executed.
 Useful when program execution should
be stopped, e.g. debugger breakpoints
 A CPU might have been programmed to
automatically switch control to a
‘debugger’ program after it has executed
an instruction
Aborts (Error Exceptions)
 Aborts usually translate very serious failures,
e.g. hardware failures or invalid system tables.
Hence, sometimes, the address of the error
cannot be found. Therefore, recovering program
execution after an abort is not always possible
 Most error exceptions — divide by zero, invalid
operation, illegal memory reference, etc. —
translate directly into signals
 The kernel’s job is fairly simple: send the
appropriate signal to the current process
 That will probably kill the process, but that’s not
the concern of the exception handler
 One important exception: page fault
 An exception can (infrequently) happen in the
kernel
 Hardware Interrupts
27

 Triggered via hardware components (e.g.

hardware timer) or by peripheral devices such
as a hard disk.
 There are two basic types: Non-maskable
interrupts (NMI) and (maskable) interrupt
requests (IRQ).
 Contrary to software interrupts, asynchronous
to the program execution. E.g.: a parity error
does not always occur at the same program
execution point. This makes the detection of
program errors very difficult if they only occur
in connection with hardware interrupts.
 Hardware Interrupts Types
28

 Non Maskable Interrupts (NMI) –

 often, the result of a serious hardware problem
 E.g. a memory parity error or a erroneous bus
arbitration.
 An NMI cannot be suppressed (masked), since it
normally indicates a serious failure and a computer
with incorrectly functioning hardware must be
prevented from destroying data.
 (maskable) Interrupt Requests (IRQ) –
 Interrupt requests can be masked with an instruction
that ignores all interrupt requests. The opposite
instruction reactivates these interrupts.
 Interrupt requests are generally issued by a peripheral
device.
 Hardware Interrupts -
29
Processing

CPU
 Internal (Pre-defined)
30
Interrupts
 Pre-defined interrupts reserved by the manufacturer
 E.g. (In Intel):
 INT0 – division by 0
 INT1 – Single Step TF
 INT2 – Non-maskable interrupt
 INT3 – Breakpoint trap
 INT4 – Overflow trap
 INT5 .. INT31 – Reserved by Intel
 OS-s such as Linux are free to use the remaining
available interrupt ID numbers for their own
purposes (e.g., for service-requests from external
devices, or for other purposes such as system-calls)
31 Interrupt Priority
 Interrupt Priority
32

 There are several methods to allow

interrupt priority:
 Individual interrupt-request and
acknowledge lines
 Daisy chain
 Arrangement of Priority groups
 With or Without selective interrupt masking
 Interrupt Controller
 The priority of a device is usually
determined by the way in which it is
connected to the CPU.
 Individual interrupt-request
33
and acknowledge lines
 Priority arbitration circuit is implemented
in the CPU.
 Daisy Chain
34

 The most common method. Less lines than the previous scheme
 The interrupt request line INTR_B is common to all devices.
However, the interrupt acknowledge line (INTA) is connected in a
daisy chain fashion. When one or more devices issue an interrupt
request, the INTR_B line is activated. The CPU responds, after
some delay, by setting the INTA line to 1. The signal is received by
device 1. Device 1 passes the signal on to the next device only if it
does not require any service. If device 1 has a pending request for
an interrupt, it blocks the acknowledgement signal INTA and
proceeds to put its interrupt vector (IRQ#) on the data lines.
 The device that is electrically closest to the CPU is having the
highest priority
 Arrangement of Priority
35
groups
 Combination of the previous 2 schemes
 Additional Flexibility
 Complex control circuity in the device
(CPU) interface
 Selective Interrupt Masking
36

 The interrupt mask (practically, an

internal CPU register) precedes the
priority arbitration circuit.
37 Interrupt Controller
The `Interrupt Controller’
 Responsible for telling the CPU when a specific
external device wishes to ‘interrupt’
 Needs to tell the CPU which one among several
devices is the one needing service
 Reduces load from the CPU
 PIC translates IRQ to vector
 Raises interrupt to CPU
 Vector available in register
 Waits for acknowledge from CPU
 Interrupts can have varying priorities
 PIC also needs to prioritize multiple requests
 Possible to “mask” (disable) interrupts at PIC or
CPU
 Interrupt Hardware
Legacy PC Design
(for single-proc IRQs
systems)
Ethernet
Slave Master
PIC PIC
x86
SCSI Disk (8259) (8259)
INTR
CPU
Real-Time Clock

Keyboard Controller Programmable Interval-Timer

 I/O devices have (unique or shared) Interrupt Request Lines

(IRQs)
 IRQs are mapped by special hardware to interrupt vectors, and
passed to the CPU
 This hardware is called a Programmable Interrupt Controller (PIC)
Example: Interrupts on
8086
 8086 core has one interrupt line, one
interrupt acknowledge line
 Interrupt sequence:
 Interrupt controller raises INT line
 8086 core pulses INTA line low, allowing INT to go
low
 8086 core pulses INTA line low again, signaling
controller to put interrupt number on data bus
INT:

INTA:

Data bus: Interrupt #

 Interrupt Controller
41

 Interrupt controller routes the interrupts

to the CPU. It “hints” the CPU on the
address (type) of the interrupt routine.
 Procedure (how it works):
 CPU signals INTA (interrupt acknowledge) to
the interrupt controller. INTA is like Read.
 Interrupt controller returns a byte with the
interrupt number (type) thru DATA bus.
 CPU is calculating the address, and jumps
to the interrupt service routine
Hardware to Software
Memory Bus
0
IRQs
INTA
idtr
IVT
INTR 0
PIC CPU
vector
N
handler

Mask points
255
APIC (LAPIC, IO-APIC)
 Advanced PIC (APIC) is used in SMP
systems
 Used in all modern systems
 Interrupts “routed” to CPU over system
bus
 IPI: inter-processor interrupt
 Local APIC (LAPIC) versus “frontend”
IO-APIC
 Devices connect to front-end IO-APIC
 IO-APIC communicates (over bus) with
Local APIC
Interrupt Routing
 Allows broadcast or selective routing
of interrupts
 Ability to distribute interrupt

handling load
 Routes to lowest priority process

 Special register: Task Priority

Register (TPR)
 Arbitrates (round-robin) if equal

priority
 Multiple Logical Processors

Multi-CORE CPU

CPU CPU
0 1 I/O
APIC
LOCAL LOCAL
APIC APIC

Advanced Programmable Interrupt Controller is needed to

perform ‘routing’ of I/O requests from peripherals to CPUs

(The legacy PICs are masked when the APICs are enabled)
Assigning IRQs to Devices
 IRQ assignment is hardware-dependent
 Sometimes it’s hardwired, sometimes it’s set
physically, sometimes it’s programmable
 Some IRQs are fixed by the architecture
 IRQ0: Interval timer
 IRQ2: Cascade pin for 8259A
 Note: especially useful for dynamically-loaded
drivers, such as for USB or PCMCIA devices
 Two devices that aren’t used at the same time
can share an IRQ, even if the hardware
doesn’t support simultaneous sharing
Interrupt Masking
 Two different types: global and per-IRQ
 Global — delays all interrupts
 Selective — individual IRQs can be masked
selectively
 Selective masking is usually what’s
needed — interference most common
from two interrupts of the same type
 Interrupt Priority
48

 Fixed/Rotating priority
 Fixed: INT0 is highest priority, INTn is lowest priority.
Only an interrupt with a higher priority than the
one that is currently being served can interrupt.
 Dependent on masking
 Rotating: FIFO, first coming priority is served first,
last coming priority is served last
 SW interrupt has always lower priority than HW
interrupt, because SW interrupt is part of the
program and interrupt will be called only when
reaching that point in the program.
 SW interrupt is just like any other program
command
49
Intel 8259A Interrupt
Controller
 8259A Programmable
50
Interrupt Controller (PIC)
 The 8259A is a programmable interrupt controller designed to
work with Intel microprocessor 8080 A, 8085, 8086, 8088. The
8259 A interrupt controller can:
 Handle eight interrupt inputs. This is equivalent to providing eight
interrupt pins on the processor in place of one INTR/INTA pin.
 Vector an interrupt request anywhere in the memory map.
However, all the eight interrupt are spaced at the interval of either
four or eight location. This eliminates the major drawback, 8085
interrupt, in which all interrupts are vectored to memory location
on page 00H.
 Resolve eight levels of interrupt priorities in a variety of modes.
 Mask each interrupt request individually.
 Read the status of pending interrupts, in service interrupts, and
masked interrupts.
 Be set up to accept either the level triggered or edge triggered
interrupt request.
 Mine 8259 as can be cascade in a master slave configuration to
handle 64 interrupt inputs.
 8259A pin diagram
51

 The 8259 A is contained in a 28-

element in line package.
 Special input pins:
 CAS0-CAS2: Cascade lines: The
CAS lines form a private 8259A
bus to control a multiple 8259A
structure ie to identify a particular
slave device. These pins are
outputs of a master 8259A and
inputs for a slave 8259A
 SP/EN: Slave program/enable
buffer: This is a dual function pin.
It is used as an input to determine
whether the 8259A is to a master
(= 1) or as a slave (= 0).
 A0: A0 address line
PC System Design

INTA

8259A INTR
CPU
8259A PIC
PIC (master)
(slave)
Programming is via
I/O-ports 0x20-0x21
Programming is via
I/O-ports 0xA0-0xA1
Three internal registers

input-signals

8259A
output-signal
IRR

IMR
input-signal
ISR

IRR = Interrupt Request Register

IMR = Interrupt Mask Register
ISR = In-Service Register
 Three Internal Registers
54

 Interrupt request register (IRR):

 IRR stores all the interrupt inputs that are requesting service.
Basically, it keeps track of which interrupt inputs are asking for
service. If an interrupt input is unmasked, and has an interrupt
signal on it, then the corresponding bit in the IRR will be set.
 Interrupt mask register (IMR):
 The IMR is used to disable (Mask) or enable (Unmask) individual
interrupt inputs. Each bit in this register corresponds to the
interrupt input with the same number. The IMR operation on the
IRR. Masking of higher priority input will not affect the interrupt
request lines of lower priority. To unmask any interrupt the
corresponding bit is set ‘0’.
 In service register (ISR):
 The in service registers keeps tracks of which interrupt inputs are
currently being serviced. For each input that is currently being
serviced the corresponding bit will be set in the in service register.
 Each of these 3-reg can be read as status reg.
 8259A Block Diagram
55
 Hardware setup – Extension to 16
interrupts using cascade architecture
56
 Hardware Setup - Extension to 64
interrupts using cascade architecture
57

Interrupt controller
 Extension to 64 interrupts
using cascade architecture
58
– Cont.
 Slave is responsible for TYPE
 INTA is connected to all cascaded devices (slaves)
 Master knows which interrupt was delivered to
CPU
 CAS bus: from master to all slaves
 If an interrupt controller is connected as slave, it
has to pass TYPE to master
else the master has to pass the TYPE
 Only the device which its number is coded using
CAS bus will assert TYPE on the data bus
 Each controller has a control register which stores
whether the controller is master or slave
 8259A - Operation
59

ISR = Interrupt Service Registe

IRR = Interrupt Request Registe
 8259A – Initialization
60

 To use the controller, it must be initialized.

 This is done using 3 or 4 initialization
command words (ICW1, …, ICW4)
 Four control words ICW1 – ICW4:
 ICW1 – MODE: Single/Cascade, level/edge
 ICW2 – TYPE: Using only 5 bits (3-7)
 ICW3 – CASCADE: only in cascade mode,
shows per interrupt input whether a device or
slave interrupt controller is connected. For
slave device, this control words show the type
 ICW4 – MASK_MODE: only in fully nested
mode, special or regular mask mode
 Initialization Sequence
61
 ICW1 (mode) and ICW2
62
(IRQ#)
 ICW2: Interrupt Type
63
Selection
 Do we REALLY need 8
64
registers to interrupt TYPE?
 No! One register is enough
 Solution:
 Allocate all “hints” of the interrupt
controller sequentially in the IVT
 Need only to store the first TYPE and
concatenate that with the interrupt number
7 6 5 4 3 2 1 0

Controlled by the interrupt controlle

Controlled by the programmer
3’b000 = IR0
3’b001 = IR1
…
3’b111 = IR7
 ICW3 (master/slave)
65

 Used in cascade mode only

 The master and each slave device have
different ICW3-s.
 Setting-up ICW3
66
 ICW4 (priority)
67
 8259A – Control
68

 Once initialized, operation can be

controlled or modified with any one of 3
operational command words (OCW1, …,
OCW3)
 These registers control various operating
modes
 Three additional control words OCW1 –
OCW3:
 OCW1 – MASK / UNMASK
 OCW2 – Priorities and EOI
 OCW3
 Operating Modes
69

 Fully nested - The default mode. IR0 has the

highest priority and IR7 lowest priority.
 Special fully nested - Selected mode for cascade
system. Similar to fully nested but with slave.
 Nonspecific rotating - Intended for systems with
several interrupt sources, all of equal priority.
 Specific rotating - Allows priority to be rotated,
but the EOI can indicate the specific IS bit to reset.
 Special mask - Allow interrupts on all inputs
excepts the one in service.
 Poll - The PIC is used as prioritized poller.
 Fully Nested Mode
70

 Entered by default upon initialization

 If an interrupt level is in service, further

interrupts from that level and all lower
priority levels are inhibited until an
End-Of-Interrupt (EOI) is issued.
 Nested Interrupt - Example
71

 IR7 (Interrupt routine #7) is

currently being served
 Simultaneously, two interrupt
requests have been filed (IR5, IR1)
 IR1 is chosen
 Checking if IR1 is masked
 Checking priority of IR1 vs.
currently served routine (IR7) based
on ISR
 As priority of IR1 is higher than IR7,
IR1 is serviced, and marked in
ISR[1]
 Nested Interrupt – Example
72
#2
 ISR can have multiple bits enabled,
based on the order of interrupt call:

 EOI will be performed in reverse order

 Dummy Interrupt
73

 An interrupt which was caused out of

noise, is called a dummy interrupt.
 Noise can cause the CPU to detect an
interrupt request, and send INTA. As
interrupt doesn’t exist, CPU can wait for
the interrupt type forever.
 CPU might read the bus, but the data on
the bus is not valid.
 Noise can occur on each of the
interrupts.
 Dummy Interrupt - Solution
74

 Allocate IR7 for dummy interrupts.

Interrupt routine #7 includes only IRET,
and no EOI (and hence, doesn’t update
ISR, which is important if priority scheme
is rotating priority).
Dummy interrupt

“Real”
Interrupt in
priority 7
 Dummy Interrupt – Cont.
75

 Noise can be on any of the lines of the

interrupts.
 E.g.
 IR1 has passed all stages unmasked with
highest priority
 => CPU sends INTA
 But: In IRR pending, it doesn’t exist
 => Interrupt controller sends IR7 and
ISR[7] is NOT asserted
 Rotating Priorities
76
 Operational Command
Words –
77
OCW1, OCW2
 Operational Command
Words –
78
OCW3
 Interrupts - Summary
79

 Forcibly change normal flow of control

 Many different types of interrupts
(exceptions/software, hardware
interrupts)
 In complex, multi accelerator chips,
interrupt controllers are used to collide,
mask and handle multiple interrupts
 8259A interrupt controller is a basic
example of such a PIC
80 End of lecture 5
 References
81

 8259A Programmable Interrupt Controller,

Vikram, 2014
 Resolving interrupt conflicts - An
introduction to reprogramming of the 8259A
Interrupt Controllers, Allan B. Cruse, 2006
 Interrupts and Exceptions (COMS W6998), S.
Bellovin and E. Nahum, 2010
 Presentation On 8259, Shabbir Hasan, 2012
 Lecture 6: Interrupts, Angela Demke Brown,
2006
 Intel 8259A datasheet, 1988
 Intel 8259A Application Note, 1999