Programming Project 8:
Due Date: ______________________________
Project Duration: One week
In this project, you will implement a device driver and will modify the syscall interface to allow application programs to access this device, which is the serial terminal interface. The goals include learning how the kernel makes the connection between syscalls and device drivers and gaining additional experience in concurrent programming in the context of an OS kernel.
With the addition of serial I/O to the kernel, your growing OS will now be able to run a “shell” program. This will give you the ability to interact with the OS in the same way Unix users interact with a Unix shell.
The files for this project are available in:
The following files are new to this project:
The following files have been modified from the last project:
The makefile has been modified to compile the new programs. The DISK file has been enlarged, since the previous version was too small to accommodate all these new files.
All remaining files are unchanged from the last project.
In this project, you will alter a couple of the syscalls to allow the user program to access the serial device. The serial device is an ASCII “dumb” terminal; individual characters can be sent and received asynchronously, one-by-one. Characters sent as output to the BLITZ serial device will appear directly on the screen (in the window where the emulator is being run) and characters typed at the keyboard will appear as input to the BLITZ serial device.
Unix divides all I/O into 2 class called “character” and “block.” In Unix, user programs can operate character-oriented devices (like keyboards, dumb terminals, tapes, etc.) using the same syscalls as for block devices (like the disk). Your kernel will also use the same syscalls, so in this project you will not add any new syscalls.
To send or receive characters to/from the serial terminal device, the user program will first invoke the Open syscall to get a file descriptor. Then the user program will invoke Read to get several characters or Write to put several characters to the terminal.
In the last project, the Open syscall was passed a filename. In this project, the behavior of Open will be modified slightly: if the filename argument happens to be the special string “terminal”, your kernel will not search the disk for a file with that name; instead your kernel will return a file descriptor that refers to the serial terminal device. Sometimes we call this the “terminal file,” but it is not really a file at all.
The Close syscall is passed a file descriptor. When Close is passed a file descriptor referring to the terminal “file,” it will work pretty much the same (from the user-level view) as with a disk file. The file descriptor will be marked as unused and free and any further attempt to read or write with that file descriptor will cause errors.
It is an error to use the Seek syscall on the terminal file. If passed a file descriptor referring to the terminal file, Seek should return –1.
When the Read syscall is applied to the terminal file, it will return characters up to either the sizeInBytes of the buffer or to the next newline character (\n), whichever occurs first. Read will return the number of characters gotten, including the newline character. Read will wait for characters to be typed, if necessary.
When the Write syscall is applied to the terminal file, it will send the characters in the buffer to the serial terminal device, so they will appear on the screen.
The following sections from the document titled “The BLITZ Emulator” are relevant:
Emulating the BLITZ Input/Output Devices (near page 25)
Memory-Mapped I/O (near page 25)
The Serial I/O Device (near page 27)
Echoing and Buffering of Raw and Cooked Serial Input (near page 28)
You might want to stop and read this material before continuing with this document.
In this section, we will make some suggestions about how you might implement the required functionality. You are free to follow our design but you might want to stop here and think about how you might design it, before you read about the design we are providing. You may have some very different—and better—ideas. It may also be more rewarding and fun to work through your own design.
Here are the changes our design would require you to make to Kernel.h. These will be discussed below as we describe our suggested approach, but all the changes are given here, for your reference.
The following should already be in your Kernel.h file:
SERIAL_GET_BUFFER_SIZE = 10
SERIAL_PUT_BUFFER_SIZE = 10
enum FILE, TERMINAL, PIPE
The following should also be there; uncomment it.
Add a new global variable:
Add a new class called SerialDriver:
------------------------ SerialDriver ----------------------------
-- There is only one instance of this class.
SERIAL_CHARACTER_AVAILABLE_BIT = 0x00000001
SERIAL_OUTPUT_READY_BIT = 0x00000002
SERIAL_STATUS_WORD_ADDRESS = 0x00FFFF00
SERIAL_DATA_WORD_ADDRESS = 0x00FFFF04
serial_status_word_address: ptr to int
serial_data_word_address: ptr to int
getBuffer: array [SERIAL_GET_BUFFER_SIZE] of char
putBuffer: array [SERIAL_PUT_BUFFER_SIZE] of char
PutChar (value: char)
GetChar () returns char
The following field should already be present in class FileManager:
The following field should already be present in class OpenFile:
kind: int -- FILE, TERMINAL, or PIPE
The serial device driver code will go into the class SerialDriver, of which there will be exactly one instance called serialDriver. In analogy to the disk driver, the single SerialDriver object should be created in Main at startup time and the Init method should be called during startup to initialize it. You’ll need to modify Main.c accordingly.
The SerialDriver has many fields, but basically it maintains two FIFO queues called putBuffer and getBuffer. The putBuffer contains all the characters that are waiting to be printed and the getBuffer contains all the characters that have been typed but not yet requested by a user program. The getBuffer allows users to type ahead.
There will be only two methods that users of the serial device will invoke: PutChar and GetChar. PutChar is passed a character, which it will add to the putBuffer queue. If the putBuffer is full, the PutChar method will block; otherwise it will return immediately after buffering the character. PutChar will not wait for the I/O to complete.
The GetChar method will get a character from the getBuffer queue and return it. If the getBuffer queue is empty (i.e., there is no type-ahead), GetChar will block and wait for the user to type a character before returning.
The Read syscall handler should invoke the GetChar method and the Write syscall handler should invoke the PutChar method.
Each of these buffers is a shared resource and the SerialDevice class is a monitor, regulating concurrent access by several threads. The buffers will be read and updated in the GetChar, PutChar and SerialHandler methods, so the data must be protected from getting corrupted. To regulate access to the shared data in the SerialDriver, the field serialLock is a mutex lock which must be acquired before accessing either of the buffers. (Our design uses only one lock for both buffers, but using two locks would allow more concurrency.)
Look at getBuffer first. The GetChar routine is an entry method. As such it must acquire the serialLock as its first operation. The variables getBufferSize, getBufferIn, and getBufferOut describe the status of the buffer.
Here is a getBuffer containing “abc”. The next character to be fetched by GetChar is “a”. The most recently typed character is “c”.
If the getBufferSize is zero, then GetChar must wait on the condition getCharacterAvail, which will be signaled with a Down() operation after a new character is received from the device and added to the buffer. After getting a character, GetChar must adjust getBufferNextOut and getBufferSize before releasing serialLock and returning the character.
Next look at PutChar. There is a similar buffer called putBuffer. Here is an example containing “xyz”.
enum FILE, TERMINAL, PIPE
One of the simulation constants used by the emulator is
The value of this number tells the emulator how fast the serial terminal device is. In particular, it tells about how many instructions are to be executed between serial interrupts.
If, for some reason, your kernel does not retrieve an incoming character from the terminal device fast enough, the character might get lost when the next character comes in. If this happens, the emulator (which checks for various program errors) will notice that your OS is failing to get incoming characters fast enough and will print out a message such as:
ERROR: The serial input character "g" was not fetched in a timely way and has been lost!
If you see this message, it indicates that your kernel has an error. It is not getting the incoming characters when it should.
The default value for KEYBOARD_WAIT_TIME (30,000) should be more than enough to give your device driver time to process each character and add it to the type-ahead buffer. If you run into this error, the solution is to fix your kernel, not modify the simulation constant!
Of course the user program may fail to call Write fast enough to prevent the type-ahead buffer from overflowing, but that is a different problem.
Review the material in the document “The BLITZ Emulator” regarding “raw” and “cooked” input. You should play around with your program using both “raw” and “cooked” mode. See the raw and cooked commands or the –raw command line option.
In cooked mode, which is the default, the host Unix system will echo all characters as you type them. Only after you hit the “enter” key will any characters get delivered to the emulator and hence to the BLITZ serial device and to your BLITZ kernel code.
In general, cooked mode is very nice because it lets the user edit his/her input (using the backspace key) and relieves most Unix programs from the burden of echoing keystrokes and dealing with the backspace character.
But be aware that with cooked mode, the BLITZ emulator may get frozen, waiting for you to hit the enter key. Or it may not. Since this may be rather confusing, the BLITZ emulator will print a message whenever it stops executing BLITZ code and is just waiting for user input.
The emulator takes a command line parameter –wait that tells it what to do when there is nothing more to do. If you go back and look at the code in the thread scheduler, you’ll see that when a thread goes to sleep and there are no remaining threads on the ready list, the “idle thread” will execute the “wait” instruction, which suspends CPU execution and waits on an interrupt.
In the past projects, we did not use the –wait option, so when a “wait” instructions was executed, the emulator would print out the familiar message:
A 'wait' instruction was executed and no more interrupts are scheduled... halting emulation!
With this project, the user is now able to type input so we don’t want the emulator to just quit. We want the kernel to wait for incoming events—keystrokes, in particular—wake up, service the interrupts, and possibly resume execution in some user-level thread.
So in this project you’ll need to use –wait on the command line, e.g.,
% blitz –g os –wait
% blitz –g os –wait -raw
Now, you’ll might see a different message:
Execution suspended on 'wait' instruction; waiting for additional user input
When you see this message, the emulator has stopped executing instructions and is waiting for you to enter something. This message only appears when the emulator is running in cooked mode; in raw mode the emulator will just quietly wait for the next keystroke.
But now there is another problem: How can you stop the emulator? The answer is by hitting control-C.
Hitting control-C once will suspend BLITZ instruction emulation and put you back in the debugging command line loop. You might see something like this:
================== KPL PROGRAM STARTING ==================
Initializing Thread Scheduler...
Initializing Process Manager...
Initializing Thread Manager...
Initializing Frame Manager...
***** Control-C *****
Done! The next instruction to execute will be:
026C5C: A3FFFFF8 bne 0xFFFFF8 ! targetAddr = _Label_168_2
Control-C behaves a little funny when in “cooked” mode. You may need to hit the ENTER/RETURN key one or two times after hitting control-C before you see the “>” prompt.
Hitting control-C twice in a row will terminate the BLITZ emulator, which could be useful if the emulator has a bug. (As if...!)
In the Read syscall handler, you should replace any incoming \r characters by \n and treat the character just like the \n character (i.e., return from the Read syscall immediately without waiting for additional characters).
Why? Because if you are running the emulator in “raw” mode, some terminals will send a \r character whenever the key marked “enter” or “return” is struck. By substituting \n for \r, the BLITZ user-level program will never see a \r character and can work only with \n characters.
In the Write syscall handler, whenever the user-level program tries to send the \n character to the serial device, you should insert an additional call to send a \r as well. Perhaps this code will work:
if ch == '\n'
This may be helpful in raw mode and should not have any effect in cooked mode. You might enjoy experimenting to see what your terminal does if this additional \r is left out. (Try hitting control-J which will send a \n to your program. Try hitting control-M which will send \r to your program.)
Ideally, an OS would perform character editing and everything associated with cooked mode in the terminal driver code. Ideally, you would run your kernel using the –raw option in the emulator and your driver would perform all echoing and character editing. You might wish to experiment with such modifications, but they are not part of the assignment.
Up to now, you have been using functions such as print, printInt, printIntVar, and printHex to assist in debugging your kernel code. These functions do not work like normal I/O on any real computer. Instead, these functions all make use of a BLITZ instruction called “debug2” which would not be found on any real computer. This magic little instruction will cause some string or number to be immediately printed out. There are no devices to interface with, no delays, and no interrupts. The output occurs “atomically” (i.e., all at once, with no intervening instructions) which turns out to be very, very useful in being able to read output from concurrent programs.
In a real kernel, there is a similar mechanism for printing to facilitate debugging. However, the output is written to an in-memory buffer (rather than displayed), where it can be examined (after the kernel has crashed) by some simpler program that copies the “output” sitting in memory to somewhere where it can be read by a human. A real nuisance, but debugging kernel code is only for the strongest of programmers!
In order for user-level programs to print, they should call Write on the serial terminal file. Technically, any use of the “debug2” instruction ought to be removed, but we have left it in. The print, printInt, printIntVar, etc. functions are for debugging use only; they are not like anything found in a real kernel. To print, a user-level program needs to call a function (such as printf in C) which in turn will invoke the Write syscall.
In our test programs, we will dispense with library functions like printf which call Write and just invoke Write directly. Likewise, we will not get around to implementing input functions like scanf, but will just invoke the Read syscall directly.
After completing this project, your kernel will have enough functionality to support a Unix-like shell. In particular, your kernel can support the following features:
(1) Print a prompt (such as %), read in the name of a program, and execute that program loaded. For example:
The file called “prog” will be executed with file descriptor 0 (stdin) pointing at the terminal and file descriptor 1 (stdout) pointing at the terminal.
(2) Redirect input using the < character, so that stdin comes from a file. For example:
% cat < myFile
(3) Redirect stdout using the > character, so that stdout goes to a file. For example:
% ls > temp
(4) Deal with stderr (file descriptor 2), perhaps using >2 for redirection.
(5) Deal with starting jobs, without waiting for their completion. For example:
% cat < myFile > temp &
In this example, 723 is the process id. We could also implement some other job-control functions like fg and bg.
(7) Nested shell invocation, for example
% sh < script > output
(8) We even have enough to implement some fancy (and complex) features such as some shell programming constructs and command-line editing and history.
(9) If we include the implementation of pipes (as discussed below), we could also add the ability to pipe the output of one program to another program. For example:
% cat | wc
What we don’t have yet is any ability to pass command-line arguments to the program, as in:
% blitz –g os -raw
As part of the testing suite, we are providing a shell program called sh. After finishing this project, see if your kernel can execute this shell!
As an extension (if you have enough time) you might consider adding pipes to your kernel.
You’ll need to add a new syscall, Pipe, which takes no arguments. This syscall will create a new pipe and return a file descriptor which refers to it. It is much like the Open syscall. It will need to allocate a new OpenFile object. The kind of this new OpenFile object will be neither FILE nor TERMINAL, but PIPE. You’ll need to modify the OpenFile class to add some sort of a buffer to it. (How many bytes should the buffer be? Only one byte is really necessary but more will allow greater efficiency for programs using pipes when a producer outruns a consumer.)
You’ll also need to add something to control the concurrency and synchronization between producers and consumers. (When the buffer is full, any process trying to write to it must be suspended. When the buffer is empty, any process trying to read from it must be suspended.) The code in Read and Write will be quite similar to the code for dealing with the terminal file.
The p8 directory contains a new user-level program called:
Please modify your code to load TestProgram5 as the initial process.