Interrupts is one of the topics that students are always having problems with in CS61C. I can't hope to cover everything in one discussion, so for the really specific stuff, I suggest you go read the textbook. What I'll be dealing with mostly here will be concepts rather than the details of MIPS interrupt programming, which you can read from the textbook.

Memory-Mapped I/O

We can design computers with special instructions to communicate with I/O devices, but the method that MIPS designers chose is using memory-mapped I/O. This is a very clean and simple way to interact with I/O devices. The hardware is designed in such a way that a certain region of memory is really not memory at all but channels to I/O devices. To do output, you simply write to that portion of memory, and to do input you just read from there.

SPIM simulates only the keyboard and display. Two pairs of Data and Control "registers" (note that they are not registers) taking up 4 words (16 bytes) are used in the memory-mapped I/O region.

A quick summary of the MIPS memory-mapped I/O registers

Receiver Control      0xffff0000    (Keyboard)
Receiver Data         0xffff0004
Transmitter Control   0xffff0008    (Display)
Transmitter Data      0xffff000c

Transmitter
Ready bit: 1 - display is ready to accept another byte.
           0 - display is not ready yet, don't clobber the data register!

Receiver
Ready bit: 1 - there is data at the keyboard, please read it from the data register
           0 - no input yet

Caution: Endianness again

Because the data in the data register is a byte, be careful how you read the register. The recommended way is to read the register as a word and mask out the top 3 bytes. Do not assume the address of the data byte because that depends on Endianness of the machine.

Polling

How do we know if data needs to be read at an input device and if an output device is ready? One obvious method is to check on each device at regular intervals. This is called polling, also called programmed I/O. Here, your program is in charge of ensuring that the I/O devices are each dealt with properly.

Obviously this is not a good method. Firstly, for input devices, most of the time when you check on them there is no data to be read. These CPU cycles are thus wasted. This is called spin-waiting. Even worse, what if you miss a word/byte of data? That won't do, because some input devices (such as the keyboard) cannot wait for the program.

For output devices, the program cannot send bytes when the device is busy. Again, CPU cycles are wasted. This time it is slightly better. The program is now doing the waiting for the device to become ready so the issue of the device not being able to wait for the program is not present.

The frequency of polling is a big question. Some devices require constant attention, while some require service only once in a while. Furthermore, more devices mean more time spent (and wasted) on each one. Managing this balance is too difficult and definitely should not be responsibility of the program.

One possible enhancement would be to use buffers. This will reduce the spin-waiting time, because the program writing to the buffer is much faster. The device can get data from the buffer at its own leisure. For input devices, a buffer allows the program to slack a little. However, buffers are not the answer. When they get full, either data will be lost or spin-waiting will result.

Interrupts

In an ideal world, a program runs concurrently with I/O operations (except for when you have to spin-wait because you need the data before you can proceed). This would imply multiple processors, but in real life we have only one processor to share among the program and I/O handling. Also, if the program does not handle the I/O devices, who does? The answer is interrupts.

Interrupts are actually a type of exception. There are three types of exceptions (note that the division may differ somewhat between different books).

1. Interrupts - these are raised by hardware and can happen anytime (asynchronous).

2. Traps - these result from the execution of the program (e.g. division by zero). Traps are synchronous in that they can be reproduced at the exact same spot if the program parameters are the same as before.

3. System Calls - you've used them so you know what they are. They are services provided by the operating system to perform certain common I/O tasks (print a character, open a file, etc). These are sometimes called software interrupts, but they are not the same as the hardware interrupts above.

Note: You do not call (hardware) interrupts. They are caused by hardware events. The operating system will handle them, your program need not worry about them.

Interrupts and system calls are handled by the exception (interrupt) handler, which is the place where control is transferred to when an interrupt occurs. The interrupt handler first saves the state of the running program before redirecting control to sections of code that does the actual handling of that particular interrupt. It does this through an interrupt vector table, which is simply a jump table pointing to the interrupt hanlding routines to jump to. Before the interrupt handler returns, the state of the interrupted program is restored, and the program continues executing as if nothing has happened.

One analogy I like (as far as I know it's my original analogy) is that interrupts are like alien abductions. The environment before and after the interrupt is still the same, except that you feel a sense of a loss of time, and some things may suddenly appear from nowhere (data has been read from input devices) and some things may suddenly disappear (data has successfully went through an output device). And no, I don't watch the X-files.

Interrupts do not occur in the middle of an instruction.

Interrupts should be lean and mean and fast.

Interrupts are an ABSTRACTION.

Protection

User programs should not interact with the I/O devices directly. All communication must go through the OS. To do this, there is a special region of memory reserved for the OS and inaccessible by user programs, called the kernel space. The OS itself runs inside this space in kernel mode. Note that this feature must be built into the hardware itself. You cannot use memory-mapped I/O now because user programs cannot access the I/O devices directly. The only way is to use the system calls.

Re-entrant Interrupts

There are two types of interrupts:

1. Cannot be interrupted

All other interrupts are disabled while an interrupt is being handled. It does not mean that interrupts which occur during this time are lost. They are just pending. When interrupts are re-enabled again after completion of the current interrupt, the pending interrupts will assert themselves.

Note that only interrupts are disabled, but not exceptions in general. For example, a divide by zero in your interrupt handler will raise the exception regardless. Anyway, your interrupt should not be causing any exceptions at all.

2. Can be interrupted (re-entrant)

If an interrupt can be interrupted halfway, then the state of the old interrupt must be saved when control is transferred to the new one. Interrupts should be disabled while the old state is being saved (Why?). Of course, we cannot let just any interrupt interrupt the current one, otherwise it is fairly easy to think of a condition where an interrupt gets interrupted halfway, and the new one gets interrupted again, and again, and again... Thus we have priority levels. The current interrupt can only be interrupted by an interrupt whose priority level is higher than it. E.g. keyboard interrupt is of higher priority than the hard disk, because the hard disk knows how to wait a while but not the keyboard (because there is an impatient user at the keyboard). In Windows, there are Interrupt ReQuest (IRQ) levels. Do not be confused when books refer to the lower interrupt numbers as having higher prority. The system designers can number the interrupts any way they like.

MIPS Specifics

Registers of interest

CPU registers

$k0 ($26), $k1 ($27)

Try to minimize the use of registers other than these two.

$sp may be used by re-entrant handler.

It is possible to use just $k0, $k1 in the interrupt project,
but we are not going to restrict you on register usage.

The only register you must save is just $at because of pseudoinstructions.


Coprocessor 0 registers (use mtc0 and mfc0 instructions)

BadVAddr     $8   Bad memory address
Status      $12   Interrupt enable
Cause       $13   Exception type (what interrupt is it?)
EPC         $14   Exception Program Counter 
                  (value of PC when interrupt occurs)

For details of fields please see textbook or lecture notes

Where is kernel space?

Kernel space is defined by the .ktext and .kdata labels. Kernel text segment starts at address 0x80000080. Your interrupt handler must start at this address.

If you remember your project 2, this is where you may have a jump instruction and the top 4 bits are not zero.

What happens when an interrupt occurs?

1. Interrupt happens.

2. Hardware will transfer control to address 0x80000080. Processor is placed in kernel mode. Interrupts are disabled by default (you can re-enable it if the interrupt handler is re-entrant). Previous IE, UK states are saved automatically in the three-level "stack" in the Status Register.Address of interrupted instruction is already in EPC.

3. Save any registers you may use. You must save $at (important).

4. Get exception code field from Cause Register.

5. (For re-entrant interrupt handler) Use the Interrupt Mask field in the Status Register to find current priority level and then mask out the lower priority interrupts.

6. (For re-entrant interrupt handler) Enable interrupts in the Status Register IE field.

7. Jump to the appropriate interrupt handler routine based on exception code. (The lecture notes say to "jump and link", saving $ra before that, but some of us TAs feel that it is not really needed since there is only one exit point anyway)

8. After the handler is done, return (jump back).

9. (For re-entrant interrupt handler) Disable interrupts again.

10. Restore all registers.

11. Use the rfe instruction to restore the previous IE, UK bits.

12. Load EPC into $k0 and do jr $k0.

13. You are now back in the interrupted program and it happily resumes execution.

Where do you save the registers? For the project, you can save them on the stack using $sp. But to be absolutely safe, what OSes do is to have special exception frames for every priority level. Remember that only priority levels higher than the current interrupt may interrupt it, so you can get only one frame per priority level.

Direct Memory Access (DMA)

Nothing much to talk about here actually. The idea is simply that instead of interrupting the CPU with every byte of data transferred, we have a special DMA controller (a separate processor) that does it for you, and interrupts only when the transfer of the block is complete. This is much more efficient than interrupting with every byte transferred. To set up a DMA read from disk, you have to provide the controller with the location of the block of data on the disk, the destination address in memory and the size of the data, and then tell the DMA controller to proceed.

Written by : Gek Siong Low (cs61c-tb), Spring 1999