Virtual Memory
Today, we begin our unit on virtual memory and machine programming, which will culminate in your building a virtual memory system for Weensy OS. It may sound scary, but remember that the OS is just another piece of software and virtual memory is just another abstraction. You've mastered many of these to date and will be able to master this one as well!
Learning Objectives
- Explain what virtual memory is and, conceptually, how it works.
- Given mapping tables, translate between virtual and physical addresses manually
- Reason about various trade-offs in virtual memory systems
- Manipulate addresses to extract various fields
Getting the Code
You won't need any code for the first part of these exercises, but you
will for the end. You'll find it in the cs61-exercises repository in
the l22 directory.
Building on the Web Work
Let's start with some exercises that build upon the pre-class work for today. Using the x86 page tables displayed, draw a picture of the address space represented by the page tables -- in particular, identify which parts of the address space are valid and which are invalid (your picture will be similar to the one I use to remind you about address spaces -- you should have regions of valid addresses and regions of invalid addresses).
Deriving Page Tables from a Memory Map
Next, we're going to do the opposite of what we just did. Take the
canonical address space diagram that we use (repeatedly) (e.g., on slide
13 
Here are the addresses from the slide (with some filled in):
0x08048000 (start)
0x0804b008 (heap)
0x0804a024 (global)
0x08048870 (const global)
0x080484a0 (main)
0xb7e674a0 (printf)
0xbffff0b0 (stack)
To get started, let's figure out a couple of things. (This is where all that effort you put into learning binary and hex should really pay off!)
1. How large a region of the address space does each entry in the L1 Page Table represent?
2. Given your answer to #1, what are the virtual addresses corresponding to the first three entries of the L1 Page Table?
3. Figure out which entry/entries of the L1 page table must be valid to represent the different addresses on the slide. That is, for each address listed, determine which L1 page table entry ultimately references it.
4. How many entries in the L1 page table will be valid?
5. Which of the addresses above reside on the same page?
6. Let's assume that we only need to allocate at most one page for each region, how many different pages will we need?
OK, you are now ready to draw your x86 page table.
The Eensy Virtual memory System (not to be confused with Weensy OS)
Professor Seltzer loves inventing new virtual memory systems to help students determine if they've mastered how page tables and address translation work. Well, she's at it again.
This time, she's invented the Eensy virtual memory system. Eensy has an 8-bit virtual address space. Pages are 16-bytes. Eensy is so tiny that it supports a single-level page table. Your job is to figure out what that page table looks like and to figure out how to translate addresses for Eensy.
7. How many entries are there in the page table?
8. What is the page mask in binary? In hex?
9. Write a C expression that takes a virtual address and returns the page number.
10. Write a C expression that takes a virtual address and returns the page offset.
11. Describe what would go in a page table entry (PTE).
12. It is possible to have physical memory that is larger than the virtual address space. Let's imagine that we wanted to be able to support 1 KB of physical memory. How could you do that?
Practice with bit manipulation in the service of Virtual Memory
Finally, we'll put all those pesky C bit operators to use! The file bits.h describes a collection of functions for extracting fields from virtual addresses and constructing and accessing page table entries.
Read the descriptions in bits.h and then implement the functions in
bits.c.
The main program in bit_test.c will let you test your functions.
Wrapping Up
As per usual, please complete this survey.