Section 4: Virtual Memory and Pagetables

In this section we're going to answer the why, what, and how about virtual memory and pagetables.

Warmup: Why use virtual memory?

In this warmup, we'll explore a few scenarios where virtual memory can help make our computers safer and more efficient.

Eve, in searching for new ways to wreak havoc, came up with a function to change memory at arbitrary locations to the dreaded 0xeb 0xfe, the machine code that creates an infinite loop!

void changeMem(char *addr) {
    *addr = 0xeb;
    *(addr + 1) = 0xfe;
}

WARMUP A. Why is this function problematic? How would virtual memory solve this problem?

Consider the following C program which allocates anywhere between 1-20 pages of memory:

#define PAGESIZE 4096
#include <stdlib.h>
#include <unistd.h>

int main() {
    int num_pages = rand() % 20 + 1;
    void *pages = malloc(num_pages * PAGESIZE);
    sleep(60);
    free(pages);
    return 0;
}

WARMUP B. Why is this program problematic? How would virtual memory solve this problem? (Hint: Think of how the operating system would need to allocate memory for multiple of these processes.)

Question 1: What enables virtual memory, and how does it work?

In this portion of the section, we'll talk about page tables, which are the data structure that makes virtual memory work on modern computers.

QUESTION 1A. What characteristics of page tables make them a good data structure to implement virtual memory? Describe the structure of page tables and their properties. [Hint: it may be helpful to draw yourself a picture!]

QUESTION 1B. Consider the following virtual address:

0xc5fc'754'69a'e05'445

Its binary expansion is given by:

1100 0101 1111 1100 0111 0101 0100 0110 1001 1010 1110 0000 0101 0100 0100 0101

How are each of the bits in the above virtual address used in translating a virtual address to the corresponding physical address?

QUESTION 1C. Explain how the operating system would translate the above virtual address into its corresponding physical address.

Question 2:

We know the specifics of how virtual address translation works with 4 KB pages and 8 byte pointers on the x86-64 architecture. However, some older computers used x86-32, which had four-byte pointers because addresses only had 32 bits and the address space was much smaller. This question investigates how virtual address translation would work with these smaller (4 byte) pointers.

QUESTION 2A. How many unique 4 byte addresses can a 4 KB (4096 byte) page hold?

QUESTION 2B. How many bits would we need to index into each address for a page table that stores 4 byte addresses?

QUESTION 2C. Consider the following 4 byte virtual address:

0x9a'e05'445

Its binary expansion is given by:

1001 1010 1110 0000 0101 0100 0100 0101

Using two levels of pagetables, how are each of the bits in the above virtual address used in translating a 4 byte virtual address to the corresponding 4 byte physical address?