Goals

This lab involves experiments with interrupt-driven input and output. In particular, we hope you get more comfortable with the sequence of read/print calls and interrupts, and with buffer management.

Reading

• P&H Appendix A, sections A.7 and A.8.

Setup

Work with a partner on these exercises.

Overview of interrupt handling

As you might guess, it's generally a waste of CPU resources to have a program constantly querying an i/o device to see if it's ready. It's like checking the clock every few minutes to see whether it's time to get out of bed. Another way to do input and output is to rely on interrupts. An interrupt is like an unplanned procedure call that's invoked only when the i/o device is ready. Setting this up requires enabling the device to interrupt.

When an interrupt-enabled device becomes ready, execution is interrupted by the hardware, kernel mode is entered, and control is transferred to a special location in kernel space. The code at that address does whatever needs to happen to service the interrupt—either making it not ready or disabling further interrupts—then returns control to the formerly executing program (leaving kernel mode if appropriate). There should be no other side effects noticeable to the interrupted program. Control flow is illustrated in the diagram below. An i/o interrupt is thus asynchronous with respect to instruction execution; it can happen in the middle of any given instruction.

MIPS details

MIPS interrupts are handled through coprocessor 0. (Recall that we discussed coprocessors earlier in the context of floating-point computation. The floating-point co-processor is coprocessor 1.) Coprocessor 0 provides several registers that a programmer may use to enable interrupts and access status information such as the address of the interrupted instruction.

Enabling keyboard and display interrupts on the MIPS is a two-step process. First, we turn on some bits in the coprocessor 0 Status register. Then we turn on the "interrupt enable" bit in the control word. This may cause an interrupt right away if the device is ready.

When an interrupt happens, control is immediately transferred to location 0x80000180. (Some computers have different entry points for the various kinds of interrupts. MIPS provides just one entry point, but provides enough information to figure out what device caused the interrupt.)

The first thing that happens in the interrupt-handling code is the saving of registers that the code will use. These include the $t registers and $at, any of which may be in use in the interrupted instruction. The choreography of doing this is sometimes complex, so by convention registers $k0 and $k1 are reserved for use by the operating system (which includes interrupt handlers).

Handler code goes on to determine what caused the interrupt, and to act accordingly. As noted earlier, loading a character from the receiver (keyboard) data register or storing a character into the transmitter (display) data register makes the device not ready, removing the possibility of an immediate subsequent interrupt on that device.

Processing both of input and of output involves the use of a buffer of characters. Webster defines "buffer" as "a device used as a cushion against the shock of fluctuations in business or financial activity." Here, we're worrying about the "shock" of connecting a fast producer of characters to a slow consumer of characters. Our buffers—one for input and one for output—are queues of characters. A print function adds characters to the end of the queue; the output interrupt handler removes and prints the character at the head of the queue.

An efficient implementation of this queue uses a circular array. A "head" variable contains the index of the first character in the queue unless the queue is empty. A "tail" variable contains the index of the first empty space in the queue. In an empty queue, head == tail. In a full queue, head == (tail+1)%size, where size is the number of elements in the array.

Interrupt-handling code

Code in two files (in ~cs61c/files/lab/13), kernel.s and exceptions.s, implement operations for interrupt-driven input and output. Run it with the following command:

    spim -exception_file exceptions.s -mapped_io kernel.s

For every character x you type to the program, it prints

    > x

on a line by itself. Read the code to familiarize yourself with its components.

Exercise 1 (2 points)

The interrupt handler disables transmitter (display) interrupts when it encounters an empty buffer, at the section of the code labeled "LAB: Exercise". Why does it do this, and what would happen if it didn't?

Predict the contents of the callSeq string after you enter a single character to the program. The code enters the following letters into callSeq:

• P for each time through the print loop;
• J for each interrupt;
• R for each receiver interrupt;
• X for each interrupt, after checking for input interrupts;
• I for each transmitter interrupt where the buffer is not empty.

Run SPIM using the command

    spim -exception_file exceptions.s -mapped_io

Then type the commands

    load kernel.s
    breakpoint loop
    run            # you hit a breakpoint here
    continue

Type a character, and then you hit the breakpoint again. At that point you can verify your prediction by typing

    print callSeq
    print 0x90000008
    print 0x9000000c
    print 0x90000010

Note that the sequence "JP" in the callSeq indicates a problem with either SPIM or our code.  Try re-running the above instructions, until you no longer have a "P" directly after a "J".  We're currently blaming a SPIM bug for this until we know more.

For checkoff, show your TA an explanation of why transmitter interrupts are disabled when the buffer is empty, and also an explanation of the sequence of interrupts and print executions.

Exercise 2 (2 points)

A buffer of 16 characters is used for input characters. If this buffer fills up without being read, subsequent characters are discarded. (Try typing quite quickly) The input interrupt handler checks for this, and tallies the number of dropped characters.

Experiment with larger buffer sizes to try find the smallest buffer size that no longer results in dropped characters, no matters how fast you type. Is this possible? (There are three places in the code to change: one in the input interrupt handler, the second in getChar, and the third at the declaration of rcvBuf. The last two are in kernel.s. Currently the buffer size must be a power of 2, since we use AND instructions to wrap around the buffer) The best way to check this is to run SPIM as in the previous activity, don't set any breakpoints, but then hit control-C after supplying some input and print the value of dropCount.

In the given code, the output buffer size is larger than the input buffer size. Why should that be the case?

For checkoff, show your TA a buffer size that results in no dropped characters and is as small as possible, or explain why it's not possible to find such a buffer size. Also explain why the output buffer size ought to be bigger than its input counterpart.