Tips for NACHOS Assignment 3
Implementing Demand Paged Virtual Memory
Assignment 3 is to be done inside of the directory code/vm
(that is where the code is compiled).
There is no new source provided by Nachos for this assignment.
It makes use of the source in code/threads and code/userprog
(some of which you'll modify for this assignment).
This is again one of those assignments where you are better off
implementing little pieces at a time.
If you find that you will not be able to do all parts of the assignment
be sure to come up with a design and explain why you've chosen that
design. It will also help if you can describe what you expect will be
the difficulties in implementing your design and how you would test it.
Don't forget that one of the group members could always be thinking
about and devising/writing good tests for each portion (or phase of
implementation) of the assignment.
A Possible Strategy
Before you Start
Read all of this document first.
I've suggested a step by step approach.
Each step builds on the previous step and you should be aware
of this when working on the earlier steps.
For example, when you choose a page-out policy for paging out
when one program is running, remember that later on you will
want to page out pages from multiple programs
and that maybe you'd like to have a different policy
from the one used when only one program was executing.
Have a look at the
the Nachos
Roadmap document.
In particular the section on tips for implementing virtual memory:
A Special Tip on Improving the File System Simulation
You are not required to do this but it may help to ensure that
you don't encounter any nasty bugs in your implementation
when moving to assignment 4.
Getting Started
You may wish to start by turning off time-slicing
so that you have stricter control and a better under
standing over what is running and when.
Remember to turn it back on later.
Start off with a small portion of the assigned problem.
Come up with a clear design. Implement it. Debug it. Test it.
The tests should clearly demonstrate that what you've implemented
works (or when it doesn't).
Paging in and running one small program
-
A good place to start is to just work on
demand paging one program into memory (don't worry about
paging any pages out).
The program should be small enough so that it fits entirely
into memory. The idea is to begin by
building the mechanisms for page-in.
-
Only move to the next step when you are convinced that this step
is implemented and works correctly.
Paging in and running a few small programs
-
A simple next step is to be able to page in
more than one program and have them run.
The sum of the total pages required should be less than the
number of pages in the system so that you will not have to
page any pages out while the programs are running.
-
Move to the next step when you are convinced that this step
is implemented, debugged, tested, and works correctly.
Paging in and out one large program
-
A good next step is to work on page-out (implementing virtual memory).
Again start with one program but
now consider programs that use more
memory than the amount of physical memory in the machine.
This step is mainly about building the mechanisms for page-out.
-
Figure out where the pages that are paged out will be stored
and how they will be retrieved when needed again.
-
At this point you'll need a replacement policy.
Start with a VERY simple one.
Remember that you may wish to use a different policy
when multiple programs are running and
being paged in and out.
-
If you can get a simple policy implemented and working in a short
amount of time then it will be relatively simple for you to
implement a more complex policy later (if you have time).
-
Remember when testing this portion to verify that the contents of
the pages being paged out are the same after they are paged back in.
Without doing this you don't know if your implementation is correct.
Paging in and out a few large programs
-
Once you can run a number of programs each of which requires more
memory than is available in physical memory
-
For each of the different executing programs
remember to verify that the contents of
the pages being paged in after the same as the contents
of the pages that were paged out.
For example program A should not page in program B's pages :-)
Without doing this you don't know if your implementation is correct.
Paging in and out several large programs
-
Try running several large program at the same time.
-
Think about what happens when you run out of swap space.
-
Think about what happens to performance when programs
start to thrash.
-
Consider implementing some means of preventing thrashing.
Things to Remember (Gotcha's)
-
You should update the counter/statistic
in machine/stats.h "numPageFaults" whenever you handle a page fault.
I believe that this can be done as follows:
stats->numPageFaults++;
-
You might consider exchanging test programs and paging statistics
with another group - once you have paging implemented.
The idea is to compare how many page faults
each version produces while running the same programs.
(NOTE: this is not required and isn't used by me to claim that
one group's implementation is better than another's - I think it's
just helpful (?fun?) for you to see the differences.)
-
Devise a plan for the assignment.
Your may be better off doing a good
job of a smaller subset of the assignment than
a mediocre or poor job of the entire assignment.
-
Think about testing! Plan your testing!
-
Use the "DEBUG" and "ASSERT" statements they should
help you to find problems with your implementation.
-
Program defensively. A good (production quality) operating
system should be completely bullet proof. Your OS doesn't need
to be quite that strong - but it should have no GLARING
holes.
-
See the notes on
Assignment One
for other "Things to Remember" and
for how to hand in the assignment.
-
See the notes on
Assignment Two
for other "Things to Remember".
Modified: Nov 5, 1995
Created: Nov 5, 1995