CSc 335

Project 3 -- Run that Code
Due Dates:
Part 1: Wednesday, May 6, 2009
Part 2: Wednesday, May 13, 2009
Part 3: Wednesday, May 20, 2009


Your Mission

Up until now, everything you have done has been inside the kernel -- running tests to make sure concurrency works. It is now time to allow user programs to run.

Some sample user programs are stored in the test directory in Nachos. Take a look at halt.c, which simply executes a Halt() system call to shut down the OS. This one already works. If you run "make" from this directory, and then look at the directory contents, you'll see a bunch of runnable user programs, including halt (runnable from Nachos, that is). What you have done is invoke a cross-compiler, which compiles code on one system (the real Linux OS on antipasto) to be run on another system (Nachos). Check out the Makefile to see how the user programs are being cross-compiled. Later on in this project, you'll be creating your own test programs in this directory to be run on Nachos.

Next, go to the userprog directory, run "make depend" and "make" there, and then use the -x option to execute "halt":

nachos -x ../test/halt

Be sure to run the right nachos (the one in userprog) to see this work. Your job for this project is to be able to write other user programs (that can even spawn off other threads themselves) and have all of those programs run in memory concurrently.

This project consists of three parts -- all non-trivial. There is a lot to digest about how NACHOS works and a lot of questions that will come up in the process. Start early. Ask lots of questions. You won't be able to proceed to a subsequent part unless you are pretty sure that each of the previous parts is working satisfactorily.

Part 1: Know your NACHOS

Nachos is already doing a lot for you in terms of memory management and handling system calls (like Halt). For this part, you need to do a lot of reading to figure out what the holes are that you need to fill. Do the following:

  1. Print out all the code in both the machine and userprog directories. Printing out a few sample user programs from test would also be good.

  2. Read "Lab 4: Multiprogrammed Kernel" from the Nachos Project Guide (available on our web page) along with your code printouts. This lab forms the basis of most of this project. Note: whenever the guide refers to SPARC, read this is as Intel. antipasto is running Linux which is running on Intel- (not SPARC-) based architecture.

    Reading section 2.5 about Creating Test Programs would also be a good idea. We also have the Roadmap through Nachos guide on our web page that can be used as a reference.

  3. Whenever there is a place in the "Lab 4" section of the guide that you don't understand, you should make a note of it and articulate the question on a separate sheet. You'll be turning in a list of these questions.

  4. Finally, based on your readings, answer the following questions on the same sheet where you put your own questions.

    1. What does the -rs option for Nachos do? At what point would we want to run that?

    2. When a user program calls a system call that is defined in syscall.h (for example, Halt) what happens? Trace through the code, starting with the call in halt.c and explain what functions get called in what order to execute the system call. Since you need to implement your own system calls for this project (see Part 3), knowing the details about the one that already works will be a tremendous help to you. Be detailed. You should understand the guts of what is happening at each step. For example, register 31 seems to be important somehow. The level of detail I am expecting is that you should be able to tell me what role register 31 is playing in all of this, and what exactly it is storing. Hint: check out the Makefile in the test directory to see what is being tacked on to each and every user program when you type "make". Hint #2: since it's a system call, you already know from a previous lecture that at some point, SVC is going to get called. But Nachos doesn't call it "SVC". What is it called here? Hint #3: Use grep to find all mentions of Halt in all subdirectories of Nachos if you are having trouble with the trace.

    3. While your DLList class was able to use statements like printf to print things out, user programs will not be able to (at least not with the code provided by Nachos). Why not?

      The following questions will be easier to answer after the lecture on Mon, May 4th.

    4. If Nachos is using dynamic binding, in what file are virtual (logical) addresses being translated into physical addresses? Is this translation already being done for you? Or is this a hole you need to fill?

    5. When a program is loaded into its address space from an executable file (like halt), is it loaded in such a way that multiprogramming is supported? Or is this a hole you need to fill? Where does it say this? What function in what file is currently doing the loading?
On the day this is due, bring two copies of your write-up to class with you. One you will turn in; the other we will be going over on that day. Remember, your write-up should have both the answers to the above questions and your own questions from your reading.

Part 2: Paging

Based on the instructions in the project guide, modify AddrSpace to support multiprogramming using a paging memory management scheme. I recommend the following:

You'll have to test this in an artificial way since true multiprogramming won't be available until you finish Part 3. I recommend putting DEBUG statements (using the DEBUG command -- it's very useful) which prints out relevant information about each page you load. Something like:

For page #1
pageStart is 128
pageEnd is 255
segStart is 0
segEnd is 303
framenumber is 1
case 1: page is subset of segment

for each page. In addition, include a printing of the frame table:

Frame Table pos 9:  pid 0
Frame Table pos 10: pid 0
Frame Table pos 11: free
When you try this with halt, you'll find that it takes up 10 pages, but that the code segment only takes up two pages (the rest is the stack and uninitialized data). And since there are no other threads, those two code segment pages will go into frames 0 and 1. That's just what static binding would do anyway! To ensure that your paging is actually working, artificially put in some temporary code that makes the memory manager allocate discontiguous frames. Then try to run halt again (with the same useful printouts as before).

You can also create your own user programs (have them do simple math or something) to use as tests. Be sure to alter Makefile in the test directory accordingly so it will recognize your new user programs!

PITFALL ALERT: When you compile your own user programs, nachos will automatically tack on a call to Exit if you don't have an explicit call to it yourself. (Where and why is it doing this?) The trouble is: you won't have Exit implemented until Part 3! My advice is: have your own test programs call Halt as the last line until we get to Part 3. At least then it will end in a predictable, if abnormal, way. Once you have Exit working, you won't need to do this anymore.

Part 3: Exec and Exit

Finally, using the project guide's instructions, implement the Exec and Exit system calls. Exec is the system call that lets user programs spawn off new threads. So Exec will eventually be calling Fork. Here are some hints and issues:

To test, create some user programs that call Exec and Exit and make sure they work. Again, DEBUG statements will be useful here to provide output.


This project is worth 50 points:

What to turn in

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Administrative statement

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.
Return to Project Index