CS61C Machine Structures. Fall 2004, UC Berkeley
CS61C Fall 2004: Project 4 - Interrupt driven I/O

TA in Charge: Slav Petrov

Due Wednesday, December 8, 2004, 11:59pm


Project Specification | Frequently Asked Questions | Contact



Project Specification

Introduction

Before you begin, copy the files
      ~cs61c/lib/iout.s
      ~cs61c/lib/iecho.s
to your proj4 directory. You will modify those files to complete the assignment.
To submit your project, create a directory named proj4 that contains your prob1.txt, iout.s and iecho.s files. From within that directory, type "submit proj4".

NOTE: For this assignment you must tell spim (or xspim) that you are providing your own interrupt handler. From the shell, give the commands
      % stty min 1
      % [x]spim -memio -quiet

In this assignment you will build an interrupt-driven mechanism for buffered I/O to and from the terminal. In the first part of the assignment you will do output only, and in the second part you will do both input and output. The file iout.s contains a skeleton for the output-only program. There are three parts to the program:
  1. A main program, starting at __START, which initializes the stack then repeatedly calls procedure print to print the string "Just wasting time".
  2. The procedure PRINT which stores the output characters in a buffer shared by it and the interrupt routine.
  3. An interrupt routine (whose code starts at INTRP), which copies characters from the output buffer to the transmitter.
The main program and the PRINT procedure are already written; all you have to write is the interrupt routine. However, you'll need to understand how PRINT works in order to write the interrupt routine, and in order to understand PRINT you'll need to understand how the buffering works.

The output buffer has space for up to 32 characters starting at symbol BUFFER. Two variables, nextIn and nextOut, are used to keep track of the buffer space that's currently occupied by characters waiting to be output. Both variables are indices into the buffer; nextIn gives the index where the next character will be added to the buffer by print, and nextOut gives the position of the next character that will be removed from the buffer by the interrupt routine. If nextIn and nextOut are equal, the buffer is empty (there are no characters waiting to be output). If nextIn and nextOut are not equal, then the characters waiting to be output start at the position given by nextOut and continue up to the position just before the position given by nextIn. For example, if nextOut is 4 and nextIn is 7 then there are 3 characters in the buffer (at positions 4, 5, and 6).

The buffer is managed circularly: each time PRINT adds a character to the buffer, it adds one to nextIn. When nextIn reaches 32 PRINT sets it back to zero again. This is implemented in PRINT by ANDing the new value with 31 (0x1f). Your interupt routine will advance nextOut in the same circular fashion.

The PRINT procedure takes a string as argument and adds the characters of the string to the output buffer one at a time, advancing the nextIn pointer circularly. PRINT does not manipulate the terminal device registers directly except to make sure that transmitter interrupts are enabled. PRINT contains additional code to deal with a full output buffer. The main program generates characters much faster than they can be output, so the buffer will quickly fill up. In a real system such as Unix, if the output buffer fills up the operating system will stop running the current user's process and switch to a different process. Your MIPS program doesn't support multiple users, so PRINT takes a simpler approach: it just checks the buffer over and over again until eventually it isn't full anymore. The buffer is full if nextOut is at the position just after nextIn (e.g., if nextOut is 4 and nextIn is 3, or if nextOut is 0 and nextIn is 31).

Part 1.

Answer the following questions. Put your answers in the file proj4/prob1.

  1. Suppose nextIn is 3 and nextOut is 28. How many characters are waiting in the output buffer? Which characters are they (give their indices)? Give the index of the character that has been in the buffer the longest.
  2. How many characters are stored in the buffer when it is "full"? Why can't all 32 characters in the buffer be used at once?
  3. The skeleton interrupt routine in iout.s returns immediately without actually doing anything. What will happen if you run iout.s in its current form? How many characters will be output on the terminal? How many characters will be added to the output buffer? What will the program be doing after it has run for a while? See if you can figure out what will happen without actually running the program. If you're not certain of your answer, try running iout.s: load the file into spim and step through the program starting at main.

Part 2.

Fill in the body of the interrupt routine in iout.s (you should not modify either the PRINT procedure or the main program). Here is a list of things the interrupt routine must do:
  1. If the transmitter is not ready, then the interrupt routine should not do anything (you shouldn't have gotten an interrupt in the first place if the transmitter isn't ready, but it's a good idea to check anyway; you'll need the check in Problem 3 below).
  2. If the output buffer isn't empty, copy the next character from the output buffer to the Transmitter Data Register and advance nextOut circularly.
  3. If the output buffer is empty, turn off the "interrupt enable" bit in the transmitter control register. Otherwise continuous interrupts will occur.
  4. Don't forget that you must save and restore any registers that you use in the interrupt routine, even temporary registers like $8 and $9 ($t0, $t1). This is necessary because interrupts can occur at any time and those registers could have been in use at the time of the interrupt. You must save the registers on the stack. The only exceptions to this rule are registers $26 and $27 ($k0, $k1), which are reserved for use by interrupt routines; these registers need not be saved and restored. One of these registers, $26 ($k0), is used to return from the interrupt routine back to the code that was interrupted.
In order to load or save $1 ($at), you must use the assembler directive .SET like this:

      .set noat
      sw $1, foo
      .set at

The first line tells the assembler that it can't use $1 ($at) as its temporary register because you're going to use it explicitly. Be careful; while NOAT is in effect, you can't use assembler pseudo-instructions that would require a temporary register!
Try to minimize the use of registers other than the CPU registers $k0 and $k1 ($26, $27).

Test your code. It should output lines continuously, with each line containing the characters "Just wasting time". Debugging interrupt- driven software is very tricky. You can't always single-step to get to the point of a problem, because it may take a large number of instructions before an interrupt occurs. In these cases you'll have to set breakpoints at key places (like the beginning of the interrupt routine) and then single-step from there. Turn in a copy of the file iout.s along with a text file that shows the program generating a few lines of output.

Part 3.

Extend the code you've already written to handle interrupt-driven input. The file iecho.s contains a skeleton for the program. This program does output in the same way as iout.s: there is a copy of the PRINT procedure in iecho.s and you should copy your interrupt routine from iout.s to iecho.s. However, you'll need to add buffered interrupt-driven input to the program. It should work in the same fashion as the buffering in iout.s except that the roles of the interrupt and background routines are reversed: the interrupt routine will add characters to the input buffer and a background routine getchar will remove characters from the input buffer. You should do the following:
  1. Define variables for an input buffer that are analogous to the BUFFER, nextIn, and nextOut variables used for the output buffer. The input buffer should only contain 8 characters worth of space in contrast to the output buffer's 32 characters. This will make it easier to test the "buffer-full" condition below.
  2. Extend your interrupt routine to check the receiver also. If the receiver is ready, the interrupt routine should read the input character from the Receiver Data Register, place it in the input buffer, and advance the appropriate index variable circularly. If the input buffer is already full, then the interrupt routine should discard the character read from the receiver: don't add it to the input buffer.
  3. Fill in the body of the procedure GETCHAR. This procedure takes no arguments and returns the next character from the input buffer. If the input buffer is empty then GETCHAR should just check the input buffer indices over and over again until eventually a character appears in the buffer (in a real system like Unix the operating system will run a different user's process while waiting for a character to arrive).
We've already written a main program to test both the input and output. The main program is an infinite loop: it calls GETCHAR to wait for a character to be typed, then it places the character in the middle of a string, then it calls PRINT to output the string. The result should be one line of output for each character you type. For example, if you type the character "z", the following output line should appear:

Received character 'z'

If you type some other character, the same line should appear with the Z replaced by the character you typed. The program will not stop until you type control-C.

Try typing characters rapidly to make sure your program can handle the case where either the output buffer or the input buffer fills up. For example, if you type two or three characters rapidly the output buffer should fill up. However, no output should be lost: the print procedure will simply have to spin for a bit, during which time additional input characters will be buffered in the input buffer. If you type eight or ten characters very rapidly then the input buffer will fill up. When this happens your interrupt routine will have to discard characters: the program should continue to function but there won't be any printout for the discarded input characters you typed. Once the output catches up with the input your program should accept input again just as if the input buffer had never filled up. We'd suggest setting a stop at an instruction in your interrupt routine that is only executed when an input character is about to be discarded; this way you can be sure that the code is being exercised. In a real system like UNIX the input buffer is much larger than 8 characters (256 characters is common in Unix systems) so that it virtually never overflows.

If you have to type four characters before your program notices, reread the instructions at the beginning of this document!

Turn in a copy of the file iecho.s along with a short text file showing a few lines of output.

Miscellaneous Requirements

  1. You must comment your MIPS code. The graders will read it, and they need to be able to quickly understand what every section does. A common style for commenting assembly is to include a long introductory comment before every block of assembly statements, with a short comment after every line telling what it does. The introductory comment must describe the algorithm that the following block implements. The line-by-line comments must just be an easy-to-read version of the assembly code, using real variable names and perhaps more C-like constructs. If your code ends up being at least as much comment as code, this is probably a sign that you are doing a good job of commenting.
  2. Put your login name, section, and t.a. information at the top of each file.
  3. To submit your project, create a directory named proj4 that contains your prob1.txt, iout.s and iecho.s files. From within that directory, type "submit proj4".
  4. This is an individual project, not to be done in partnership. Hand in your own work, and do not collaborate with anyone else.


Revision history

2004.11.29 - Original copy of specification
2004.12.06 - Andy has set up the submission process. Please name the files with your sample output "iout.spimsession.txt" and "iecho.spimsession.txt" and submit them together with the other three files.



Frequently Asked Questions

2004.11.29 No questions yet.



Contact

Contact me by email mailto:cs61c-tb@imail.eecs.berkeley.edu


CS61C-td, http://inst.eecs.berkeley.edu/~cs61c/hw/proj4/ (Last Updated: 2004-11-17 ALS )