| CPSC 220 | Introduction to Computer Architecture | Fall 2008 |
In this lab, you will write a crucial piece of modern operating systems: a trap handler. Your trap handler, which you will implement on a Larc machine, will essentially implement system calls performed by the user program, which is closer to how it works in real computing systems (i.e., system calls are not atomic instructions). To implement a system call, you will need to write Larc code that will communicate directly with the Input/Output (I/O) devices. In the case of Larc, there are only two I/O devices you will need to worry about: the keyboard and the display.
Polling. One problem with programming I/O is that the processor and I/O devices, such as the keyboard and display, work at very different speeds (i.e., the processor is much faster than the I/O devices). Consequently, we need some way to synchronize the processor and I/O devices. There are two possibilities: polling or interrupt-driven I/O. In polling, the trap handler repeatedly checks if the device is ready and, when it is, exchanges data with the device. In interrupt-driven I/O, the trap handler executes another program while the device is busy and when the device is finished it interrupts the running program and a trap occurs back into the trap handler, which can then exchange data with the device. Polling is simpler to implement but less efficient than interrupt-driven I/O. Because polling is simpler, Larc supports polling and not interrupt-driven I/O.
To determine if a device is ready, your trap handler, will need to implement the following loop (written in pseudocode):
repeat infinitely
check if device is ready
if it is ready then break
Memory-mapped I/O. Obviously, your trap handler can not make use of a system call since that is what you are implementing. Instead, it must communicate with the devices using the other 15 instructions. Each device has a set of registers (called device registers), which the trap handler can read or write in order to communicate with the particular device. These registers are read and written in a different way than the processor registers. They are read and written by reading or writing specific memory locations (called memory-mapped I/O). In this way, we do not have to use up space in the ISA for device registers, but instead can make use of existing instructions (lw and sw). It does require alloting a part of memory to I/O devices, but since memory is large, this is generally not a big deal.
Here are the Larc device registers along with their corresponding memory-mapped address:
| kbcr | keyboard control register | 0xFE00 |
| kbdr | keyboard data register | 0xFE01 |
| dcr | display control register | 0xFE02 |
| ddr | display data register | 0xFE03 |
| mcr | machine control register | 0xFFFF |
The kbcr and dcr device registers indicate when the corresponding device is ready. If the leftmost bit (sign bit) is 1, then the device is ready, otherwise it is not. The other 15 bits are unused. The kbdr and ddr registers are used to pass characters from or to, respectively, the corresponding device. The rightmost 8 bits (low-order 8 bits) are used to hold the character, the leftmost 8 bits (high-order 8 bits) are unused. The mcr register can be used to halt the machine. If the rightmost bit (low-order bit) is set to 1, then the machine halts. Otherwise, it continues running.
Memory layout. Your trap handler will be loaded into memory along with a user program (e.g., nim.out), meaning that when the user program is first copied into memory your trap handler will be copied into memory as well (at a different location). Whenever, the user program needs to perform a system call, the Larc machine will transfer control to your trap handler, which will perform the task on behalf of the user program.
Because we now have a user program, a trap handler, and memory-mapped I/O, which each must be put somewhere into memory, the layout of memory is somewhat more complicated than in past labs. Memory will look as follows:
|
|
Note: both the user program and trap handler areas will further be broken up into instruction and data areas.
Memory protection. With the trap handler and device registers sharing memory with the user program, there must be ways to prevent the user program from corrupting the trap handler and/or devices. Larc has a very simple mechanism for doing this. It uses a base address and limit to confine the program to one area of memory. Register 14 holds the limit (in our case 0xF000), which defines the highest address it can use. If the program attempts to use a higher address, a trap will occur to the operating system (with the simulator, it simply terminates the program). Register 13 holds the base (or starting) address of the user program (in our case 0). Whenever the user program attempts to access memory, the base address is added to the program's address. This allows a user program to start at an address besides 0. While not necessary in this assignment, it would allow for running multiple programs simultaneously with all of the programs sharing memory.
Of course, a user program might attempt to modify register 13 or 14 and subvert this mechanism. For this reason, register 15 holds a bit indicating whether the program is running in kernel mode. If this bit is not set, then the program cannot modify registers 13-15. If it attempts to write any of these registers a trap will occur to the operating system. So you might wonder then how the kernel mode bit ever gets set. The machine automatically sets it when transferring control to the trap handler. It automatically unsets it when transferring control back to a user program.
System call steps. Unlike in previous labs, the system call is no longer atomic. It will consist of several steps. In particular, the following steps will occur:
Writing the trap handler. You will write your trap handler in Larc assembly code. Your trap handler will be much larger than the assembly code you wrote in the previous lab. As such, you will split the trap handler into several subroutines to make it more manageable. Because it will be placed into the middle of memory rather than at address 0, you will also have to assemble it differently than assembling a user program. Otherwise, load addresses will not work properly (they will end up loading address in the user program part of memory). To handle this issue, you just have to tell the assembler what the starting address is (otherwise, it assumes it starts at 0) using the "-s" flag (shown below). In particular, you want to use the starting address 0xF000 or 61440.
Create a lab10 directory within the ~/cs220 directory that you created in lab 1 for use in this lab. Change to the newly-created lab10 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab10 to your new lab10 directory. The following commands should work (note: the "-r" in the cp command allows for copying directories as well as files):
bash$ mkdir ~/cs220/lab10 bash$ cd ~/cs220/lab10/ bash$ cp -r /classes/f08/cs220/labs/lab10/* ~/cs220/lab10/
Note: the rest of this lab assumes you are in your lab10 directory.
Your directory should now contain a file os.s which contains skeleton code for your trap handler. You must complete this code in this lab.
Your directory should also now contain 3 files for assembling, running, and debugging Larc programs as well as your trap handler: asm, sim, and db. See the previous lab assignments for details on how to run these. The discussion below outlines only the new features of these tools that you will be using.
In this lab, unlike in the last lab where you wrote a conventional program, you will write a program that is placed into the middle of memory (0xF000 or 61440). This requires a special assembler process to account for this (otherwise load addresses will fail). To assemble the trap handler, you will do the following:
bash$ ./asm -s 61440 os.s
The "-s" flag specifies the start address of 61440 or 0xF000 (it must be specified in decimal). This will create an assembly program called os.out, which can be used as a trap handler. For example, if you want to run the program foo.out using the trap handler os.out, you could do the following:
bash$ ./sim -t os.out foo.out
The "-t" flag specifies the trap handler machine code file. When a trap handler is specified, a system call will not be executed atomically. Instead, a trap will occur to address 0xF000 or 61440 and the code at that location (your trap handler) will be executed.
You can also debug both the user program and trap handler with db. To do this, you would do the following:
bash$ ./db -s "-t os.out" foo.out
The "-s" flag specifies the simulator flags that should be used, in this case "-t os.out" (don't forget the quotes -- they are not optional). You will then be able to debug your program as you have in the past. Note: the program will start in the user program, which you did not write. But as soon as a system call is executed, control will transfer to the trap handler, which you did write.
Note: because the assembler converts some assembly instructions into several machine instructions it can be hard to understand what machine instructions correspond with what assembly instructions. Unfortunately, there is no way to debug the trap handler as assembly code (there is a way to debug the user program as an assembly program as you saw in the previous lab). So you will have to work through this problem.
Finally, your directory contains a directory called tests, which contains some test programs. Note: not all of them will work unless you do the extra credit (i.e., the ones that perform print or read int system calls).
There is one exercise for this week's lab due in two weeks.
In this exercise, you will write a trap handler for handling all system calls. The skeleton code for the trap handler is provided in the file os.s. One system call, exit, is already implemented for you. Your task is to implement the print string (1) and read string (3) system calls. For extra credit, you can also implement the print int (2) and read int (4) system calls.
There are some requirements in how you write your trap handler. First, any register you modify must be restored before returning with the exception of 10 (sp), which you can assume the program is not using. You also cannot modify any of the user program's memory. In addition, you must break the code up into several subroutines. In particular, you must define the following subroutines (in addition, to the main subroutine and exit subroutine):
If you do the extra credit, then you should define subroutines print_int and read_int for printing and reading an int. In addition, feel free to add other subroutines as you see fit.
Finally, you will need to do some error checking. In particular, you will need to verify that the system call identifier is valid. You will also need to make sure the program isn't trying to read or write a string from the OS or I/O areas of memory. If any of these errors occur, you should print an error message and exit.
Verify that your lab10 folder contains all of the files you created or modified for this lab (e.g., os.s), then copy your entire lab10 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). For example, if your working directory is ~/cs220/lab10/ then you could do the following:
cp -r ~/cs220/lab10 ~mcorliss/handin/cs220/username
where username is replaced with your particular username (e.g., mcorliss).