Project 3 -- Run that Code
Part 1: Wednesday, May 6, 2009
Part 2: Wednesday, May 13, 2009
Part 3: Wednesday, May 20, 2009
- 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
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
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:
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.
- 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.
- 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.
- 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.
- Finally, based on your readings, answer the following questions
on the same sheet where you put your own questions.
- What does the -rs option for Nachos do?
At what point would we want to run that?
- 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.
- 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.
- 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?
- 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
Based on the instructions in the project guide,
modify AddrSpace to support multiprogramming
using a paging memory management scheme. I recommend
- 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
- 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
- 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
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:
- 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.
This project is worth 50 points:
- 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
Having trouble? Don't wait until the last minute! Come see me and get
Programming assignments, like homework
assignments, are individual projects. I encourage you to
others about the general nature of the project and ideas about how to
However, the technical work, the writing, and the inspiration behind
be substantially your own. If any person besides you contributes in any
the project, you must credit their work on your homework. Similarly, if
include information that you have gleaned from other published sources,
cite them as references. Looking at, and/or copying, other people's
written work is inappropriate, and will be considered cheating.