Goals
- Provide you a visualization tool help you examine the structure and workings of the virtual memory system.
- Help you understand the different parameters of the VM system and how they affect performance.
Setup
You will be using a program called Camera this week. Camera is a cache and virtual memory simulator, and you will be using the virtual memory simulation features for this lab. Like MARS and Logisim, Camera is a java-based application that you can download to your home computer. You can get the jar file by copying it from ~cs61c/bin/Camera.jar on the instructional machines. To run Camera, type:
$ java -jar ~cs61c/bin/Camera.jar &
Note: If you wish to run Camera remotely, make sure you are running an X-Server (like XMing) with tunneling enabled. Tunneling does NOT work on the Orchard machines. Additionally, there is a font issue on the Hive machines that shifts most of the necessary buttons out of view. We highly recommend you run Camera remotely or connect to one of these servers.
Exercises
Exercise 1: A Sample Run (CAMERA)
Run Camera and select the VM option, opening a visualization of a virtual memory system:
- In the top left you can see the contents of physical memory. There are 4 "frames" in this simulation. (A "frame" is just a place to put a page. While you can use the terms interchangeably, we use "page" exclusively in this class.)
- Just below that is a listing of all the pages of the virtual memory of this process. There are 8 in this simulation.
- The middle column shows the contents of the TLB and the Page Table. The TLB in this simulation is fully associative and holds 4 entries. The Page Table is forced to have 8 entries. Why? Note that in order to save space, this simulator does not show the PPN mappings that are stored in the Page Table. It also does not show the other management bits (Dirty, Access Rights, LRU) that you would find in both the TLB and Page Table in reality.
- The right column has a place to add a sequence of memory accesses as well as panes to show the virtual to physical address translation.
- The bottom of the window has the "PROGRESS UPDATE" box and control buttons. The box will keep you updated on the status of your simulation as you progress through it using the control buttons.
At this point these should all be empty as we haven't done anything yet (everything is "cold"). Click the button labeled "Auto Generate Add. Ref. Str." at the right-hand side of the window. This will generate a set of ten address references. You can think of these as a series of MIPS "load word" instructions reading from the memory address specified. Click the button labeled "Next" to begin the simulation.
For the rest of this exercise you are at the mercy of the "PROGRESS UPDATE" box. After each click of the "Next" button examine the contents of the box and the current state of the memory system. Try to really get an understanding of what is going on in the TLB, the Page Table, and Physical Memory at each step. Make sure you can answer the following questions:
- How do we split a virtual address? How do we know where this split happens?
- Which gets checked first: the page table or the TLB?
- Does a TLB hit count as a page table hit?
- What happens on a page fault?
- Where exactly does the "Virtual Memory" live as shown in this simulator?
- What happens after a page is loaded from disk to physical memory?
Once you have reached the end of the simulation note the number of TLB Hits and Misses and Page Hits and Faults. Did you have any Page Hits? Why or why not?
Check-off
- There is so much VM terminology! Reset and auto-generate some new memory accesses. Go through the first access and explain clearly using proper VM terminology what is happening at each step.
- Explain to your TA why this particular simulation canNOT ever generate a Page Hit.
Exercise 2: Custom Access Patterns (CAMERA)
Now that you've seen what a random workload looks like in the VM system, let's try creating custom workloads with specific properties:
- Create a workload of 10 memory accesses that will cause 10 TLB misses and 10 page faults.
- Create a workload such that the 5th page fault replaces the page in frame 2 of physical memory. Physical memory (and the TLB) are using a LRU replacement policy.
You should be able to come up with these workloads on paper, but then you should run it in Camera to verify your work. You can specify a custom workload in Camera by clicking the button labeled "Self Generate Add. Ref. Str." and entering in the addresses you want to reference one at a time. When you are satisfied that you've got valid sequences, write them down!
Check-off
- Show and explain your 10 accesses that cause 100% miss rate in the Page Table. What is the shortest repeating sequence of memory accesses that can cause this behavior on this simulator? What is the longest?
- Show and explain your access pattern to replace the page in Frame 3. What is the minimum number of accesses required to do this starting from a "cold" system?
Exercise 3: Memory Systems Engineering (CAMERA)
Let's be more explicit about how the VM parameters affect performance. Make a copy of the table below (print or draw from scratch). Each row has a different VM parameter. Place a check mark in each column of that row if that parameter affects the property listed above it. Be prepared to explain your reasoning for each of these.
Feel free to discuss with others in lab as this can be a very confusing topic!
VM Parameter | Virtual Addresses | Physical Addresses | TLB entry width | PT entry width | max # valid entries in TLB | max # valid entries in PT | # PT entries |
Page Size | |||||||
PM Size | |||||||
VM Size | |||||||
TLB Size | |||||||
TLB Replacement Policy | |||||||
PM Replacement Policy |
Given your sequence of memory accesses from the first part of Exercise 2, can you find a change to a single parameter that would result in the same number (ten) of TLB misses but result in fewer than ten page faults?
Check-off
- Show your filled-out table to your TA, who will ask you to explain a few of the entries.
- Explain the single parameter change that will allow for page hits in this simulated system.
Exercise 4: Putting it all in Context (VMSIM)
VMSIM is a virtual memory simulator located here: http://www.cs.gmu.edu/cne/workbenches/vmsim/vm.html.
Go to the VMSIM website and inspect the VMSIM applet. What is different about the setup of this simulation as compared to CAMERA? In particular, what are P1, P2, P3, and P4? If you watch closely you'll see that this simulation reports a much higher percentage of TLB misses than the random run on CAMERA did. Why might this be?
Check-off
- Explain your answers to the questions above to your TA. When and why do we perform the action that is causing the increased TLB misses? (Hint: the name of this exercise is meant to be a pun)