Assignment 6: Virtual Memory

Due: Fri Mar 17 11:59 pm
No late submissions accepted.

Original assignment by David Mazières and John Ousterhout, with modifications by Nick Troccoli.

Assignment 6 Overview Session: Fri. 3/10 in lecture (1:30-2:20PM in NVIDIA). The video and slides are incorporated as part of lecture 25: slides here, video here.

No late days are permitted for this assignment. Late submissions are accepted only with an instructor-approved extension.

In this project, you'll have a chance to implement the core components of a virtual memory system using demand paging. You'll maintain a per-process page map, map virtual pages to physical pages, and swap physical pages to disk if physical memory fills up. Normally, code like this would be written inside the operating system kernel. For this project, we have used the Linux mmap facility to simulate features that are typically available in the kernel (such as page faults), so you can write your code at user level.

(Note: you may assume that your code is used only in single-threaded environments; you do not need to worry about synchronization for this project.)

This spec is long, but its length is due to the detail with which it walks you through the code required for each part. We strongly recommend using the provided milestones to work incrementally through the assignment!

Learning Goals

The goal of this project is for you to get further experience learning how demand paging works, and how virtual addresses can be mapped to physical ones. This assignment will help you:

  • more fully understand paging mechanisms and how page maps are used
  • learn about demand paging and how it works
  • get practice navigating a large code base where multiple classes interact

Getting Started

To get started on the assignment, clone the starter project using the command

    git clone /afs/ir/class/cs111/repos/assign6/$USER assign6

This line creates a new folder called assign6 in your current working directory containing a copy of the starter code.

Here are the relevant files for your work on the assignment:

  • virtualmemoryregion.hh/cc: Defines a class VirtualMemoryRegion representing a single process's virtual address space. You will edit the header file to add state to maintain the page map, and edit the cc file to write code that handles things like page faults.
  • physicalmemory.hh/cc: Defines a class PhysicalMemory representing the physical address space (a collection of physical pages shared across all processes). You will edit the header file to add necessary state, and edit the cc file to implement the mechanism for deciding which page to swap to disk if memory fills up.
  • diskregion.hh/cc: Defines a fully-implemented class DiskRegion representing the disk data for a single process (its executable and its swap space). You do not need to modify this class.
  • test_harness.cc: a program that can run tests for your virtual memory and physical memory classes written as script files - this allows you to write .txt files in a special format to test your implementation, without writing any code.
  • custom_tests - a file where will write your own tests for the assignment.
  • samples: a symbolic link to the shared directory for this assignment. It contains:
    • test_harness_soln: a provided sample test_harness solution executable that you can use to run script files, but which runs them with our sample solution implementations of virtualmemoryregion and physicalmemory instead of your own.
    • scripts: a folder containing provided test scripts for testing your code

This project consists of two parts: in part 1, you will implement a paging system for processes without demand paging, meaning you will assume that there are enough physical pages to store all memory contents. In part 2, you will no longer assume this, and implement demand paging with the clock algorithm to handle the case where physical memory fills up and pages must be swapped to disk.

Additionally, this project builds on the prior one in its use of C++ classes, methods and instance variables, and uses some additional C++ features, some of which you may have used before, and others that might be new. Check out this C++ guide/refresher to get up to speed!

Open assign6 C++ Guide

Testing and Debugging

Test cases for this assignment are written as script files. Script files are txt files in a special format that the test_harness.cc program understands. The test harness can read script files and "run" them - based on the commands in the script file, it will call various methods on your code. This allows testing without having to write any code yourself - neat!

You can run the test harness on a script like this:

./test_harness somescript.txt

The sanity check tests all run a command like this, use provided script files in the samples/scripts folder - you can open any of them to see what that test is evaluating. For instance, the first sanity check test runs the script file at samples/scripts/one_page_read.txt, which contains the following:

# Make a VMRegion with 1 page, and read it
1
INIT 1 1
READ 1 0

Lines beginning with # are comments, and ignored. The first line of the script must be a single number specifying how many physical pages in total there are to use. The lines following that can be one of several different commands:

  • INIT [ID] [N] will make a new VirtualMemoryRegion (with id ID) with N virtual pages.
  • All other commands are in the format [COMMAND] [ID] [PAGENUM]. They perform that command on the specified virtual page number in the VirtualMemoryRegion with that ID. For instance, the script above makes one VirtualMemoryRegion with ID 1, and reads its virtual page 0. Valid commands include: READ, WRITE, STORE (pre-stores arbitrary generated data for a page on disk), SWEEP (calls clock_sweep), REMOVE (calls clock_remove) and CHECK_SHOULD_REMOVE (calls clock_should_remove).
  • If you include the line CHECK_CLEANUP somewhere in your script, the test harness will also check to make sure all of a VirtualMemoryRegion's pages are unmapped and all its physical pages freed when a VirtualMemoryRegion goes away.

When the test harness runs a script file, it outputs log information to the terminal about the operations it's performing. Additionally, there are log statements printed when you do things like call map or unmap. If your output for a script doesn't match the sample solution, try to narrow in on what is different and use the output to understand where the implementation issue might be.

As you work through the assignment, you should also create at least 2 of your own script files, each part of their own documented test in custom_tests, that show thoughtful effort to develop comprehensive test coverage. In other words, your custom_tests file should have at least 2 additional lines, each representing a test of your own using its own script file that you create. The tests supplied with the default SanityCheck are a start that you should build on, with the goal of finding and fixing any bugs before submitting, just like how a professional developer is responsible for vetting any code through comprehensive testing before adding it to a team repository.

You can run GDB on your code by running it on test_harness, setting breakpoints as needed, and running on a script. For example:

gdb test_harness
...
(gdb) b VirtualMemoryRegion::handle_fault
(gdb) run samples/scripts/one_page_read.txt

IMPORTANT NOTE: the assignment page faulting system works by relying on SIGSEGV (segmentation fault) signals. In other words, you may find that, when you run the program in GDB, it seems to crash at some places due to SIGSEGV, but if you type "continue" it will continue running - if it does, this means that SIGSEGV is really representing a page fault, not an error. However, you can disable this behavior with the following gdb command: handle SIGSEGV noprint nostop pass. The arguments indicate that, when SIGSEGV signals occur, they should be passed to the application; gdb will not stop the application or print any indication that the signal occurred.

We provide a compiled test harness in samples/test_harness_soln which is a version compiled with our solution implementation.

1. Paging

In this first part, you will write code just in virtualmemoryregion.hh/cc to implement a virtual memory paging mechanism.

Because the code we are writing is not actually in the OS, it's difficult to intercept every memory request for translation. Instead, we will use a similar, but slightly modified, mechanism for implementing a virtual memory system:

  • A process can create a virtual address space by creating a VirtualMemoryRegion and specifying its size. The size cannot change after creation.
  • The process will not explicitly request pages from the OS; instead, it will just access what it wants to use within the virtual memory region, and we will assume those accesses are valid.
  • Whenever the process accesses an address that is not currently mapped (not present), it will trigger a page fault and call a function you will write. At that point, your code should map a physical page for that virtual page and update the page map.
  • If the process accesses that same page again in the same way, your code does not run since that page is already mapped - the setup automatically handles translation from there. Your code only runs when there is a page fault.

In this assignment, there are a few convenience features you can use:

  • VPage is a type representing the starting address of a virtual page. It's really just a pointer - however, using it in your code can make it clearer that you are referring to a virtual page.
  • PPage is a type representing the starting address of a physical page. It's really just a pointer - however, using it in your code can make it clearer that you are referring to a physical page.
  • get_page_size() returns the system page size, in bytes. You can assume the page size is a power of 2, but don't make any assumptions beyond that.

In part 1, you will implement the handle_fault function that is called whenever a page fault occurs, and the VirtualMemoryRegion destructor, which is called when the region goes away. We have already written the code to initialize a VirtualMemoryRegion and given it two pre-initialized instance variables:

  • physical_memory_: this is the instance of PhysicalMemory you should use when you need to get physical pages.
  • disk_: this is the instance of DiskRegion you should use when you need to read or write on disk.

We recommend the following implementation milestones:

Milestone 1: Read-only Pages

For the first milestone we'll add code to handle_fault to get comfortable using some of the provided code to map virtual pages to physical ones. There's only a few lines to write, but they help understand the provided code and classes. We won't maintain a page map yet, and we'll assume all pages are read-only for now.

In order to map a new page, we must do 3 things in this milestone:

  1. Figure out which virtual page was being accessed
  2. Get a new physical page to map it to
  3. Map the virtual page to the physical one

For step 3, to record a new mapping you must call the already-implemented VirtualMemoryRegion map function. It takes a pointer to the start of a virtual page, a pointer to the start of a physical page, and access protections (e.g. read, read/write), and sets that virtual page to map to that physical page with the specified protections:

void map(VPage va, PPage pa, Prot prot);

For now, we will assume pages are read-only, so the prot parameter should always be PROT_READ. For the other two parameters, we must get a pointer to the start of the virtual and physical pages (steps 1 and 2).

For step 1, the fault_addr parameter is the address whose access caused the page fault. To get the address of the start of the virtual page it's in, we can subtract off the offset (the portion of the address not divisible by the page size):

VPage virtual_page = fault_addr - ((unsigned long)fault_addr % get_page_size());

For step 2, we can call the get_new_ppage method in PhysicalMemory to get a new physical page. Check out physicalmemory.hh to see the function's documentation.

This milestone consists of just 1 line of code per step; once you finish this, you should pass the first two sanity check tests, ReadOne and ReadTwo, which try to read virtual pages.

Milestone 2: Reading From Disk

Demand paging and swapping don't come into play until later in the assignment; but even without those, sometimes we must read contents from disk to initialize pages. For instance, if a page is part of the code segment for a process, that should initially contain contents from the executable, where the compiled code is stored. On the other hand, stack or heap pages don't contain any initial contents.

For this milestone we will add support for reading initial page contents from disk if appropriate. The DiskRegion class is provided for you and lets you check if the disk is storing any contents we should load in for a page, and read that contents. Check out diskregion.hh for an overview of the is_page_stored_on_disk and load_page_from_disk methods, and add a few lines of code to your fault handler to check if the page being mapped has initial contents stored on disk, and if it does, copy them into the mapped page.

Once you do this, you should pass the next two sanity check tests, ReadOneFromDisk and ReadTwoFromDisk, which read virtual pages that are expected to have initial contents.

Milestone 3: Read/Write Pages

So far, we have marked all pages read-only. Because the code we are writing is not actually in the OS, it's difficult to know whether a page should be marked as read-only vs. read-write. For this assignment, the mechanism we'll use to determine this is we'll initially set all pages to be read-only; and if the process tries to write to a read-only page, this will trigger another page fault, at which point we'll assume the page they are accessing should be read/write. Therefore, if we get a page-fault for a page that we have already mapped, that must mean we should update its mapping to have read/write protections instead of just read. And if we have not mapped the page before, we should do as we did before and add a new mapping with read protections. You can call map again with an existing mapping to change the protections, and you can specify read-write protections by passing in PROT_READ | PROT_WRITE. You can assume if we get a fault, it's either an unmapped page, or a mapped read-only page.

For this milestone, because we need to remember what pages we have mapped between calls to handle_fault, you will need to add state to create your page map as an instance variable (the provided map function doesn't track any information for you that you can access). In lecture, we modeled a page map as an array of entries; however, on this assignment the virtual address space may not start at 0 (it may just be a partial region), so it's fine to use a map data structure (check out our assign6 C++ guide!) instead of an array, and store only mapped ("present") pages instead of all pages. The design of the page map is up to you, and you will likely update what it stores as you work through assignment milestones; don't start by adding all information we saw in lecture that's in the page map, since not all of that may end up being necessary on this assignment. Instead, consider just what info you need for this milestone, and then if you find later you need to store more info, you can add to it then.

Add your page map and use it in handle_fault to:

  • add a new mapping whenever you fault on an unmapped page, or
  • update a mapping's protections whenever you fault on an already-mapped page.

Note that you should only request a new physical page for a new mapping - if something's already mapped, don't request a new physical page, since you already have one.

After this milestone, you should pass the next two sanity check tests, WriteOne and WriteTwo.

Milestone 4: Destructor

Next, we will implement the destructor, ~VirtualMemoryRegion. When a VirtualMemoryRegion goes away, we need to unmap all mapped pages and free all our used physical pages. The way to tell the system to remove a mapping is to call the already-implemented VirtualMemoryRegion unmap function. It takes a pointer to the start of a virtual page and removes the mapping previously added for that page:

void unmap(VPage va);

Once you call unmap, if a process references that page in the future it will again trigger a page fault.

The way to free a physical page is to call the page_free method in PhysicalMemory and pass in the physical page you are no longer using. Check out physicalmemory.hh to see the function's documentation.

Once you implement the destructor, the next test (cleanup) should pass. Congratulations, you have an implemented virtual memory paging system!

2. Demand Paging

In part 1, we assumed that there were always enough physical pages to store memory contents. In this part, we will no longer assume that; physical memory could fill up, and if we need further physical pages we will need to swap pages to disk.

The code for this part will be in two places:

  • You will add code to VirtualMemoryRegion to handle pages being swapped to disk. There are three short methods that you will implement in VirtualMemory (and later call in PhysicalMemory) to indicate updates from the clock algorithm: clock_sweep, clock_should_remove, and clock_remove. You will also need to make modifications to your page map and destructor/handle_fault method.
  • You will change the implementation of get_new_ppage in PhysicalMemory to handle the case where there are no more physical pages and run the clock algorithm. You have called this function in part 1, and now you will implement it!

For the clock algorithm, in lecture we saw that the page map keeps a referenced bit for each entry to track whether it has been used recently. When the clock hand sweeps over a page, if referenced is 1, we set referenced to 0 and continue. If referenced is 0, then we pick it to swap to disk (as it has not been used since we previously set referenced to 0). For this assignment, instead of a dedicated referenced bit, we will rely on a third category of protection for pages along with PROT_READ and PROT_READ | PROT_WRITE, called PROT_NONE. PROT_NONE is the equivalent of referenced = 0, and if a page has one of the other two protections it's the equivalent of referenced = 1. Over the course of the milestones below, we'll update our code in VirtualMemoryRegion to account for this third protection category.

TIP: Remember to call map whenever you change the protections for a mapping!

We recommend the following implementation milestones:

Milestone 1: clock_sweep

The clock_sweep method in VirtualMemory will be called when the clock hand "sweeps over" a page, marking it as not referenced. Implement clock_sweep to update the specified mapping to have the protection PROT_NONE.

You will also need to update handle_fault because if a PROT_NONE page is accessed, it will trigger a page fault as well. If this occurs, you should update its mapping to be PROT_READ (thus indicating that it was referenced).

You will likely need to modify your page map design as now you will need to distinguish between multiple different protection categories. Make sure to keep your page map properly updated everywhere in your code!

Once you implement these changes, you should pass the next test (sweep), which reads a page, calls clock_sweep, and then reads the page again.

Milestone 2: clock_should_remove

The clock_should_remove method in VirtualMemory will be called when the clock algorithm wants to know whether this page is a candidate to be kicked out. Implement clock_should_remove to return true if the page has not been referenced since the last time clock_sweep was called, or false otherwise. This method is very short! Once you implement this, you should pass the next test (candidate).

Milestone 3: clock_remove

The clock_remove method in VirtualMemory will be called when the clock algorithm selects the specified page to kick from memory. For now, we will assume that a page being kicked to disk is read-only, meaning that we do not need to save it to disk swap before kicking it out; if the process accesses it again, we can simply load it in from the executable as we've already been doing. Implement clock_remove to remove the specified mapping and free its physical page. Make sure to call page_free after unmap (otherwise page_free complains that the page is still mapped). Once you implement this, you should pass the next test (kick).

Milestone 4: Dirty Pages

In milestone 3, we assumed that all kicked-out pages were read-only, and therefore did not need to be swapped to disk. Now we will no longer assume this; if a page is dirty, meaning it was modified since being mapped, we need to save it to disk so we can restore its contents later.

For this assignment, as a simplification we will assume that any page that the process attempts to write to is automatically dirty. However, this doesn't mean that only pages with protection PROT_READ | PROT_WRITE are dirty; it's possible that a page that is PROT_NONE is dirty if, for instance, the process wrote to it, then the clock hand swept over it, and now it is being kicked out. Update your implementation of clock_remove (and add any additional needed state) so that before you unmap it, you write a page to disk if it's dirty; check out diskregion.hh for an overview of the store_page_to_disk method.

Now, the page should be automatically read in from swap the next time it's referenced; because DiskRegion handles both reading from executable and reading from swap, and in a prior milestone we already handled the case of checking the DiskRegion for contents when a new page is referenced. Cool!

Once you implement this, you should pass the next test (swap). Your implementation of VirtualMemoryRegion is complete!

Milestone 5: Clock Algorithm

The last milestone is the most significant, and involves implementing the clock algorithm in PhysicalMemory. You will update the implementation of get_new_ppage which, for the moment, always returns a new page, assuming there are enough. You will modify it to return a new page if there is one, but if there isn't, you will first run the clock algorithm to select a page to kick out, and as part of this you will call the clock_ methods you implemented in earlier milestones.

PhysicalMemory has access to an "unallocated pool" of physical pages. Every time you call page_alloc, it takes a page from this pool, and every time someone calls page_free, it returns a page to the pool. You can check if there are pages in the pool by calling nfree(), which returns the number of unallocated pages in the pool. If there are none, get_new_ppage should run the clock algorithm. After running the clock algorithm to kick out a page, a page should be returned to the unallocated pool.

The clock algorithm requires a way to iterate over each used physical page and access information about it. Specifically, we need to know, for each physical page, which VirtualMemoryRegion is currently using it, and which virtual page they have it mapped to. This is because PhysicalMemory will need to call the clock_ methods you implemented previously to tell them e.g. that one of their pages is being kicked out. To do this:

  • You should maintain a fixed-size vector instance variable in PhysicalMemory, that stores this information for each physical page - index 0 would store information for the first physical page, index 1 would store info for the second physical page, and so on. Don't resize the vector over time, as adding/removing elements adds complexity - initialize it to a fixed size. Tip: vectors are initialized with no elements, but you can set a vector to a specific size by using resize(n) on the vector.
  • You will need to convert from physical page address (e.g. what is returned by page_alloc) to vector index. There is a method pool_base() that gives the starting address of the first physical page, and all physical pages are contiguous. You can use this information to go from physical page address to vector index. As an example, index 0 would store information for the physical page at address pool_base(), and index 1 would store information for the physical page at address pool_base() + get_page_size(). Remember that you can subtract two pointers to get the number of spaces between them!
  • Within get_new_ppage, first run the clock algorithm if needed to choose a page to kick out, and tell the VirtualMemoryRegion who is using it that it is being kicked out. Recall that clock_remove should return that physical page to the unallocated pool.
  • After this, you are guaranteed to have at least one page in the unallocated pool. So you can then call page_alloc, store info about the physical page in your vector, and return it.
  • The clock algorithm code should use the clock_remove, clock_should_remove, and clock_sweep methods you previously implemented. You can call them on a specific VirtualMemoryRegion. Review virtualmemoryregion.hh for the documentation on how to use them as a client.
  • The very first time the clock algorithm is run, the "hand" should start on page 0. Then it should advance through the pages over time and wrap back to the beginning again. Remember that beyond the first run of the clock algorithm, the hand should start at the next index after where it left off the previous run!

Once you implement the clock algorithm, you should pass the last three sanity check tests, big_swap (which tests one big region with more virtual pages than physical pages) two_regions (which tests two regions that combined have more virtual pages than physical pages) and multi_swap (which tests three regions that each modify a page, those pages get swapped to disk, and then we read them back). Congratulations, you have a fully-implemented demand paging system!

Submitting and Grading

Once you are finished working and have saved all your changes, submit by running the submit tool in the tools folder: ./tools/submit. We recommend you do a trial submit in advance of the deadline to allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work. You can confirm the timestamp of your latest submission in your course gradebook.

Your assignment will be graded using the tests we expose via sanitycheck, plus potential additional functionality tests. We will also grade your included custom tests; your custom_tests file should include at least 2 additional tests (meaning at least 2 new lines in custom_tests), each of which uses a custom script file, and which show thoughtful effort to develop comprehensive testing coverage. Please include comments that explain your choices. We will run your custom tests against your submission as well as review the cases to assess the strength of your testing efforts.

Because this assignment is due at the end of the quarter, to facilitate a quick grading turnaround, we will not be grading style for this assignment - however, good style can directly benefit debugging and functionality by having clean, well-designed, well-documented code!