Assignment 2: Virtual Memory

Due: Midnight on Monday, November 10

Introduction

You have three tasks in this assignment. The first is to use valgrind to capture memory traces of interesting programs and do some analysis of how these programs use memory. The second task is to complete a virtual memory simulator to implement four different page replacement algorithms: OPT, FIFO, exact LRU, and Clock. The third task is to create a memory reference trace that illustrates Belady's anomoly.

Before you start work, you should complete a set of readings about memory:

• Paging: Introduction

Starter Code

Programs with different memory access behaviours:

• simpleloop.c
• timer.h (used by matmul and blocked)
• matmul.c
• blocked.c
  

The starter code for the simulator:

• Makefile
• avl.h
• avl.c
• pagetable.h
• pagetable.c
• sim.c
• clock.c
• fifo.c
• lru.c
• opt.c
• rand.c

Requirements

Task 1

Read each of the programs and figure out how they access memory. Then, use one of the valgrind tools to record the memory access trace of each program. Run it as valgrind --tool=lackey --trace-mem=yes <prog> where prog is the executable file. Look at the trace file. Notice that there is a lot of memory activity to get a program ready to run, before it begins executing the program code!

How do you know where the "main" part of the code starts? In simpleloop.c you will see an example of using special variables (MARKER_START and MARKER_END) to separate initial loading of the program and the final shutdown of the program from the code and data accesses of the program itself. The addresses of MARKER_START and MARKER_END are written to a file, so we know which addresses these variables have after the program finishes executing. Then a value is stored in MARKER_START just before the first "real" instruction in main and a value is stored in MARKER_END just before main returns. You will need to add these marker variables to the other programs you are analyzing.

Produce a memory reference trace for each of the programs provided. (Use the argument "100" for matmul and the arguments "100 25" for blocked.) In addition, produce a memory reference trace running make on the simulation starter code as well as on another interesting program of your choice. (That's a total of 5 programs.)

Important: valgrind will take some time to produce these traces, and they will be quite large. Make sure to delete them as soon as you have finished analyzing them.

Using your scripting knowledge (shell, python, or some other language), write a short script to analyze the traces and produce a table with the following information:

• Number of unique code pages (I)
• Number of unique data pages (S, L, M)
• Number of memory accesses before and after the markers
• Number of memory accesses in algorithm component of the program (in between the markers)

You will have to do a little math to compute which virtual page each address belongs to. Assume 4096 byte pages. (You can verify this on your system using the getpagesize function, but regardless, assume 4096 byte pages for the table you're producing.)

Task 2

Using the starter code, implement each of the four different page replacement algorithms. The main program in sim.c reads memory reference traces in the format produced by the valgrind tool shown above. Physical memory is represented by the coremap array. Each element of the array represents a physical page frame. It records if the physical frame is in use, the address of virtual page that is using it, and the type of the page (I for instruction, D for data).

A second data structure is used as the virtual page table. Since the page table is essentially a lookup table, we are using an open source implementation of an AVL tree. Each element in the page table records which physical frame the virtual page is mapped to and its type (Instruction or Data).

You will find that you want to add fields to the struct page and struct frame for the different page replacement algorithms. You can add them in pagetable.h, but please label them clearly.

Once you're done implementing the heuristics, run all five programs from Task 1 using each of your heuristics. For each heuristic, run the programs on memory sizes 50, 100, 150, and 200. Use the data from these runs to create a set of tables that include:

• Overall hit count and hit rate
• Overall miss count and miss rate
• Hit count and rate before marker start
• Hit count and rate between the markers

To calculate the last two hit rates, you will need to modify the code to look for the marker accesses (or add a special flag to your trace). You can't just trim the traces; then, you'll end up with a low hit rate "between the markers".

Task 3

Create a trace that illustrates Belady's anomaly. The anomaly must be revealed when run in the simulator using FIFO page replacement with coremap sizes (memsizes) 20 and 21. (These sizes are artificially small to make it easier to produce the trace.) The trace should be artificially generated -- you do not have to write a program that exhibits Belady's anomaly when it runs!

Write up

Include a file called README.txt or README.pdf that includes the following information.

• The table prepared in Task 1, together with a sentence or two describing how each program accesses memory
• The tables prepared in Task 2, along with two paragraphs. The first paragraph should compare the various heuristics in terms of performance and ease of implementation. The second paragraph should explain the data you obtained for LRU as the size of memory increases.
• A paragraph explaining the how the trace from Task 3 illustrates Belady's anomaly. Make reference to the hit rate in each case.

Submission

The assignment should be submitted to an a2 directory in your svn repository. Don't forget to add and commit your updated simulator code and your README (in text or pdf format). We will pull the last commit before the deadline for marking.