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 learned about paging (and its variant, demand paging) as one possible virtual memory design. Paging chops 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 we do not need to keep all used pages resident in memory; we can swap a physical page to disk, reuse that page for something else and load the prior data back later when it's needed again.

Let's review 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 the following page map:

Index | phys. page | present
------|------------|---------
3     |  XXXXX     |    0
2     |  XXXXX     |    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? 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 the physical address space consists of only 2 physical pages. The process requests a mapping for virtual page #2, and the demand paging system picks virtual page #1 to kick to disk. How would the page table 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 in a simulated program we've created that enacts how virtual memory is implemented (since we can't fiddle with the actual virtual memory system).

Specifically, the VirtualMemory class represents a program's virtual address space, managed using the "demand paging" design. You create one and can assume the address space is as big as you'd like, and accessing any address is considered valid. When you create one, you also specify the size of the physical address space, in pages. For instance, here we create a new virtual address space, and we can access any addresses within it, but ultimately the physical address space is just 1 physical page:

VirtualMemory v_mem(1);

How do we get a pointer to this fake virtual address space? Like this:

VirtualPointer ptr = v_mem.get_start_ptr();

A VirtualPointer is a simulated pointer type that we've defined that hooks into VirtualMemory. It behaves like a regular char * pointer - you can dereference it, do pointer arithmetic with it, and print it out:

*ptr = 'h';
*(ptr + 5) = 'z';
cout << ptr + 5 << endl;

Why can't we use regular pointers? We need the ability to intercept every memory access, and we can't easily do that with a real program's pointers unless we're the OS :) VirtualPointer is set up so that every time one is dereferenced, it calls a method translate that we will write the code for.

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:

the page map is 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 virtual address and should use the page_map to translate it to a physical address and return that. And if we have reached our limit of physical pages and need to add a new mapping, we must swap a page to disk and reuse that page. We provide some code to get you started that extracts the page start and offset:

char *translate(char *virtual_addr) {
    /* The offset is the part of the address 
     * not divisible by PAGE_SIZE
     */
    size_t offset = (unsigned long)virtual_addr % PAGE_SIZE;
    // The start of the page is just offset 0
    char *vpage_start = virtual_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:
    ppage = nullptr
    if we have no more free physical pages:
        pick a page at random
        swap it to disk
        ppage = the physical page we just kicked out
        remove it from our map
    else:
        ppage = new physical page

    add this new mapping to our page map

    if this page was previously swapped to disk:
        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.
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

Lastly, there is a DiskRegion instance variable called disk that handles the task of swapping to and from disk - you'll use a similar type 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.