Learning Goals

During this section, you will:

become more familiar with the "demand paging" approach to virtual memory
write your own code to translate a virtual address to a physical one using the "demand paging" design

Get Started

Clone the section starter code by using the command below. This command creates a section7 directory containing the project files.

git clone /afs/ir/class/cs111/repos/lab7/shared section7

Next, pull up the online section checkoff and have it open in a browser so you can jot things down as you go.

In lecture, we saw the third approach we will discuss for implementing virtual memory: paging (and its variant, demand paging). With paging, we chop the virtual and physical address spaces up into fixed-size pages (for our purposes, 4KB, or 4096 bytes), where a virtual page maps to a physical one. Demand paging adds to this, where, if we run out of physical pages, we can swap one to disk, reuse that page for something else and load the prior data back later when it's actually needed again.

We'll start by reviewing the mechanisms for paging and demand paging, and then we'll implement the translation code so you can see what it could look like!

1) Virtual Memory Review

Say a process has a page map with the following information:

Index | phys. page | present
------|------------|---------
3     |  0x621     |    0
2     |  0x125     |    0
1     |  0x621     |    1
0     |  0x125     |    1

Q1: Assume that we are not using demand paging (so accessing a not-present page is an error). For each of the following memory accesses, are they valid? And if so, what physical address would they really access? Assume a page size of 4KB, so the lowest 3 hexadecimal digits encode the offset, and the upper digits encode the virtual page number.

accessing virtual address 0x0221
accessing virtual address 0x1223
accessing virtual address 0x3112

Q2: Now assume we are using demand paging, and have only 2 physical pages in total in memory to use. The process requests a mapping for virtual page #2, and the demand paging system picks virtual page #1 to kick to disk. Describe how the page table should be updated to reflect this change.

2) Implementing Demand Paging Translation

Now you'll get a chance to implement the code for the "demand paging" design. Like in the previous section, we've provided a class VirtualMemory that represents a program's virtual address space, but this time managed using the "demand paging" design. In this new version, you create one and don't need to specify the virtual address space size - it's assumed to be as big as you'd like, and accessing any address is considered valid. But you must now specify how many physical pages can be used at most at one time. For instance, here we create a new virtual address space, and we can access any addresses within it, but ultimately the physical address space contains just 1 physical page:

VirtualMemory v_mem(1);

You can get a pointer to the start of the virtual address space like this:

VirtualPointer ptr = v_mem.get_start_ptr();

A VirtualPointer is the same simulated pointer type that we used on lab6 that calls translate whenever we try to dereference it.

Internally, VirtualMemory has a page_map instance variable which maps from virtual pages to physical pages:

std::map<char *, char *> page_map;

In lecture, we saw that the page map is a contiguous array and works with virtual and physical page numbers. However, to make things easier in this implementation, we will implement it slightly differently:

we will make the page map be an std::map just containing present pages, rather than an array containing all pages.
With page numbers and offsets, combining the two requires bit concatenation - but we'd rather use addition to make translation easier. So instead of keys being virtual page numbers, we will have them be the base address of the virtual page. In other words, for virtual page #2, instead of the key being 0x2, it will be 0x2000, which is the address of the start of page 2 (i.e. with offset = 0). We will do the same for physical pages - instead of storing physical page numbers, we will store the base address of the physical pages. In this way, we can translate by adding the base address to the offset (instead of doing bit concatenation of the page number and the offset).

Your task is to implement the translate method within VirtualMemory; it takes in a VirtualPointer (a virtual address) and should use the page_map to translate it to a physical address (represented as a char *) and return that. Each VirtualPointer has an addr instance variable which is the virtual address it stores. And if we have reached our limit of physical pages and need to add a new mapping, we must swap one to disk. We provide some code to get you started that extracts the page start and offset:

char *translate(const VirtualPointer& p) {
    /* The offset is the part of the address 
     * not divisible by PAGE_SIZE
     */
    size_t offset = (unsigned long)p.addr % PAGE_SIZE;
    // The start of the page is just offset 0
    char *vpage_start = p.addr - offset;

    ...
}

Take a minute to parse through these lines - how do these get the offset and the page base pointer?

Now it's up to you to implement the rest of translate. Here is a pseudocode outline of what it needs to do - for this implementation we'll just pick a page at random if we need to kick one to disk:

if the page is not in the map:
    if we have no more free physical pages:
        pick a page at random
        swap it to disk
        remove it from our map

    make a new mapping with a new physical page
    if this page was previously swapped out:
        load its contents from disk

return the translation

Here are some notes on how to implement this:

We are modeling a physical page as a heap allocation - whenever we need a new page, just make a new heap allocation of size PAGE_SIZE.
You can check if a map does not contain a key using the following syntax: if (page_map.find(vpage_start) == page_map.end())
VirtualMemory has an instance variable nphysical_pages which is the most entries the page map can have at once. If there are this many entries, then we cannot get any more physical pages until we swap one to disk.
The get_random_vpage() method returns a randomly-selected key in the map
The .erase(key) method on map erases an entry from a map

Lastly, there is a DiskRegion instance variable called disk that handles the task of swapping to and from disk. (Note: DiskRegion is something you'll use on assign6!)

disk.store_page_to_disk(vpage, ppage) copies a page's contents to disk. The contents of the physical page are copied to disk and labeled as being for the given virtual page.
disk.is_page_stored_on_disk(vpage) tells you if a virtual page has contents swapped to disk
disk.load_page_from_disk(vpage, ppage) loads the specified virtual page from disk. It pulls data labeled with the given virtual page and copies it into the given physical page. Make sure to check there are contents before calling this.
We've set up DiskRegion for this section problem to log to the terminal every time it performs an operation.

Q3: implement the translate method and test it by running the provided test program, which attempts to write to 5 separate pages, and then read from those pages.

int main(int argc, char *argv[]) {
  // Initialize with just 1 physical page
  VirtualMemory v_mem(1);

  /* Get a virtual pointer to the start of the address space.
   * A VirtualPointer can be used just like a 
   * regular char * pointer.
   */
  VirtualPointer ptr = v_mem.get_start_ptr();

  /* Write to the first byte of the first 5 pages
   * Only one of these can really be mapped at a time
   */
  for (int i = 0; i < 5; i++) {
    VirtualPointer newPtr = ptr + (i * PAGE_SIZE);
    *newPtr = 'a' + i;
    cout << "Data at virtual address " << newPtr 
         << " is: " << *newPtr << endl;
  }

  /* Now read the first byte of the first 5 pages
   * This will require swapping to/from disk
   */
  for (int i = 0; i < 5; i++) {
    VirtualPointer newPtr = ptr + (i * PAGE_SIZE);
    cout << "Data at virtual address " << newPtr 
         << " is: " << *newPtr << endl;
  }

  return 0;
}

To see what should be outputted, try running the sample solution samples/test_soln.

NOTE: in a real virtual memory system, only the OS can see physical addresses; a user program is only aware of virtual addresses. You might imagine that test.cc is a user program, and translate is in the OS.