CSc 335

Objectives

• To implement a memory manager that will support a multiprogramming environment
• To implement the system calls Exec and Exit (and possibly Join)
• To understand how a paging scheme works
• To learn a lot about how Nachos deals with address spaces, system calls, and user processes
• To finally allow user programs to run (and spawn off other threads!)

Your Mission

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

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 4^th.

   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?

Part 2: Paging

• Make a Table class to support a frame table. This can be used to tell which frames are in use and which are free. To generalize it, you could use an array of void pointers as the underlying implementation.

• Create a memmgr class to act as a memory manager. This allocates free frames to the pages that a thread needs. It would also deallocate frames when the address space is destroyed.

• Create a PCB table to hold PCBs. You'll only have 1 PCB to store for this part, but since you're already making a Table class, go ahead and do this now. I recommend a PCBmgr class to act as a PCB manager. This would be a central place to create and destroy PCBs, search for a specific PCB, etc. You can make a frame table entry point to a PCB as an easy way of keeping track of the thread to whom the frame is allocated.

  PITFALL ALERT: Don't forget about concurrency issues! Your frame table and PCB table are going to be global shared data structures and thus need to be protected! Lock up appropriate functions.

• When you modify the way you load a thread into its address space in AddrSpace.cc, remember that you are doing everything in terms of pages now. So you will want to load one page at a time. I recommend creating a function LoadPage that, given a page number, will load the correct information from a code or data section of an executable file into the appropriate frame in memory. An appropriate prototype would be:

  // Load the right stuff from segment s found in file executable into page pagenumber
  void LoadPage(unsigned int pagenumber, Segment s, OpenFile *executable)
  

  though you may be able to come up with a prototype that isn't so messy. Having a LoadPage function will be a big help when you do virtual memory in the next project.

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:

CODE SEGMENT LOAD
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
...

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

• When you execute Nachos with the -x option, that first thread runs courtesy of the StartProcess function in progtest.cc. Use that as a guide as to how Exec will get new threads running.

• There are addressing issues with the argument of Exec. Namely, each character of the string (the string represents the file to be run in the new thread) will be stored in a logical address. This must be translated to the physical address by your code before you can use it!

• Pay attention to the instructions about incrementing the PC manually when you do a system call. That's easy to forget.

• It would be helpful in your debugging if your user programs could print, so here is an implementation of the Write system call that you can use to do just that. It will also be helpful to you as another example of a system call.

• EXTRA CREDIT ALERT: The project guide also has you implementing the Join system call, but I'm not requiring it. However, implementing it successfully nets you an additional 5 points (10%) of extra credit. As we've discussed in class, implementing Join complicates Exit since exiting PCBs may need to wait for their parents to finish.

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.

Grading

• 10 points for the write-up of Part 1.
• 20 points for a working paging system detailed in Part 2.
• 15 points for a working Exec system call
• 5 points for a working Exit system call

What to turn in

• For Part 1, just turn in your write-up.

• For Part 2, turn in a paper copy of your output showing your frames being allocated (using the DEBUG stmts mentioned above). Make sure to have at least one test where discontiguous frames are being allocated. Label your tests well and include explanations so I can tell what is going on. Also, turn in paper copies of source code for all code you have written for this project.

  Electronically, please submit your entire nachos directory (the code directory) using our submission script.

• For Part 3, please do the same thing you did for Part 2: turn in paper copies of your output tests and source code where you modified it. Then submit nachos in its entirety electronically:

  /home/csc335pub/submit csc335 <full path to your code directory>

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

Administrative statement