Section 7 Solutions

Solutions

1) Virtual Memory Review

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

A1: The first two are valid (the first accesses page 0, the second page 1), but the third is not, because it accesses page 3, which is marked not present. The first one would really access physical address 0x125221 (physical page number 0x125, offset 0x221), and the second one would really access physical address 0x621223 (physical page number 0x621, offset 0x223).

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?

A2: First, we would kick virtual page #1 to disk, meaning we would mark its entry as present = 0. Then, we would reuse physical page 0x621 in the mapping for virtual page 2, which would now be marked as present = 1. The page table would thus look like the following (with XXXXX marked for any no-longer-valid values):

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

2) Implementing Demand Paging Translation

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.

A3: a solution could look something like this:

char *VirtualMemory::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;

  // If the page is not present, we must make a new mapping
  if (page_map.find(vpage_start) == page_map.end()) {
    // We will either get an unused physical page, or swap one
    char *ppage_start = nullptr;

    // If we are out of physical pages, kick one out and reuse it
    if (page_map.size() == nphysical_pages) {
      char *vpage_to_remove = get_random_vpage();
      disk.store_page_to_disk(vpage_to_remove, page_map[vpage_to_remove]);
      ppage_start = page_map[vpage_to_remove];
      page_map.erase(vpage_to_remove);
    } else {
      // Otherwise, get a new physical page
      ppage_start = (char *)malloc(PAGE_SIZE);
    }

    // Add a new mapping
    page_map[vpage_start] = ppage_start;

    // If this page was swapped previously, load its contents back in
    if (disk.is_page_stored_on_disk(vpage_start)) {
      disk.load_page_from_disk(vpage_start, ppage_start);
    }
  } 

  // Translate by adding the page start with the offset
  return page_map[vpage_start] + offset;
}

(Side note - why do some of the DiskRegion methods take both a physical page and a virtual page parameter? Because we are only guaranteed to be able to write to/from the physical page within translate. Here, we can't read from the virtual page because that would call translate again, and we'd be stuck in an infinite loop. Similarly, we can't write to the virtual page either. So we must copy to/from the physical page, but we need the virtual page parameter so the disk knows the key under which the data is stored).

And the output for ./test should look like this:

Data at virtual address 0 is: a
 [DiskRegion: storing page 0] Data at virtual address 0x1000 is: b
 [DiskRegion: storing page 0x1000] Data at virtual address 0x2000 is: c
 [DiskRegion: storing page 0x2000] Data at virtual address 0x3000 is: d
 [DiskRegion: storing page 0x3000] Data at virtual address 0x4000 is: e
Data at virtual address 0 is:  [DiskRegion: storing page 0x4000]  [DiskRegion: loading page 0] a
Data at virtual address 0x1000 is:  [DiskRegion: storing page 0]  [DiskRegion: loading page 0x1000] b
Data at virtual address 0x2000 is:  [DiskRegion: storing page 0x1000]  [DiskRegion: loading page 0x2000] c
Data at virtual address 0x3000 is:  [DiskRegion: storing page 0x2000]  [DiskRegion: loading page 0x3000] d
Data at virtual address 0x4000 is:  [DiskRegion: storing page 0x3000]  [DiskRegion: loading page 0x4000] e

Since there's only 1 physical page, every access of a new page after the first one results in writing to disk and potentially reading from disk. We are always writing the existing page to disk, and if we already stored the new page on disk, reading its previous contents.

Checkoff Questions

  1. [Q1] In the provided example page table, what physical address would really be accessed when we access virtual address 0x0221?

    • See A1.

  2. [Q2] Explain one benefit of the paging approach vs. the multiple segments approach (where there is a base and bound for each segment).

    • For paging, there is no external fragmentation because all pages are the same size; with the multiple segments approach, the size of each segment can vary, which can cause problems when trying to find space for them in physical memory. With paging, we always know that space will be requested in increments of pages. (Paging has internal fragmentation issues, however, since even if a program may not need an entire additional page's worth of memory, it would get a full page anyway).

  3. [Q3] In the translate method, once you add or confirm a mapping in your page map, how do you go about translating it to a physical address?

    • We add the physical page start to the virtual address's offset and return that result.