Sections Wed Mar 08 to Sat Mar 11
Handout written by Nick Troccoli, with modifications by Parthiv Krishna.
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 we do not need to keep all used pages resident in memory; we can swap a page 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. We can't fiddle with the actual virtual memory system, so instead we've designed a program that enacts how virtual memory is implemented in a simulated setting.
Specifically, we've provided a class VirtualMemory
that 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. But you must 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 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
. 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 :) So instead, we defined a custom type VirtualPointer
set up so that every time someone dereferences one, it will call a function translate
that we will write the code for. A VirtualPointer
behaves just like a regular char *
pointer, though - we have implemented the functionality to allow you to dereference it (which calls translate
), do pointer arithmetic with it, and print it out:
*ptr = 'h';
*(ptr + 5) = 'z';
cout << ptr + 5 << endl;
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 be0x2000
, 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 variablenphysical_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. (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 diskdisk.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.