CSc 335

Objectives

• To implement virtual memory so that processes can take up more space than physical memory can hold
• To implement demand paging
• To understand and implement a page replacement algorithm (maybe more than one!)

Your Mission

Part 1: Pages on demand

• For now, when a page fault happens, you can assume that you will have a free frame available. That is, you won't need to choose a victim frame yet. That's for Part 2. You'll implement this assumption simply by testing user programs that you know in advance will completely fit in memory, like halt or my two paging tests on Blackboard. All of the other programs in the "test" directory, like sort and matmult, won't work until Part 2 is finished.

• There is already a "valid" field in each page table entry. You just have to use it.

• If you check out machine.h, you'll see a list of all the possible exceptions (traps) in Nachos. You worked with SyscallException in Project 3. You'll work with PageFaultException now. Do a grep for PageFaultException so you can see how and where it is being used. In Nachos, a page fault causing a trap to the OS will manifest itself as just another exception to deal with in ExceptionHandler. So you're on familiar ground. Make sure you understand what this means! (And ask me if you don't!)

• Remember, do NOT advance the PC when you're done servicing the page fault. You want the instruction that originally caused the page fault to be redone. It just shouldn't cause a page fault the second time around.

  PITFALL ALERT: There is the possibility that a page fault might occur not just in a user program, but also inside the kernel itself. Why? (Hint: think about Exec and what we've already discussed in class regarding address translation.) If a page fault occurs in the kernel, you don't have control over the PC in this instance because to Linux, the Nachos kernel is just another C++ program and you don't have control over the real Linux PC! To solve this, whenever you issue a ReadMem command in the kernel (this is where the page fault would happen), do it twice. If there's a page fault on the first ReadMem, the second one will be valid. We'll talk more about this pitfall in class.

Part 2: The Big Swap Out

• Implement a page replacement algorithm. You should implement it as a separate file so that you can easily switch to a different one. Please use one of the following global replacement strategies:
  • Random

  • FIFO

  • EXTRA CREDIT ALERT: if you implement Second Chance or Third Chance, it's worth 5 points of extra credit.

• Create a swap file that can be used to write out dirty pages. A swap file is just a file stored on the simulated disk. Check out the filesys and openfile classes in the filesys directory. They'll have the functions you need to create, open, read, and write to a swap file.

  I suggest using a single swap file for all of your swaps. Just read and write to the swap file in page-sized chunks. Add an int field to each page table entry called "swapPage" that holds the page of the swap file containing that page's data. Initialize swapPage to -1 indicating that no swap file exists for that page at the beginning. Then, once your page replacement algorithm identifies a victim frame, do the following:

  1. Check the dirty field to see if a swap out is needed. If so...

  2. Write the victim frame's contents to the end of the swap file. Keep a global counter to indicate the number of pages the swap file already has so you know where to write. For example, if the counter's value is 5, this means the swap file already contains 5 pages (0 through 4). Write the page out starting at location 5 * PageSize = 5 * 128 = 640.

  3. Record the counter value (5 in our example) in the swapPage field of the appropriate page table entry and increment the counter.

  Remember, you also need to consult the swapPage field when swapping in the new page to see if the new page should be coming from the original executable file or from the swap file.

EXTRA CREDIT ALERT: Part 3: PRA comparison

Write a report that explains what you did, what experiments you ran, what you were trying to test, what you measured, and what your conclusions are. Under what circumstances does one algorithm fare better than the other?

Remember

Grading

• 25 points for Part 1.
• 25 points for Part 2.

There is a maximum of 10 points of extra credit to be gained in this project.

What to turn in

Label your tests well and include explanations so I can tell what is happening. 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;

/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