CS 45: Lab 4

Handy References:

Lab 4 Goals:

Design and implement a single-level paging system.
Compare and contrast page replacement policies.
Use the mmap() function to map a file into a process's virtual address space.
Reason about the sizes and number of bits used to track pages and frames.

Overview

For this lab, you'll be translating a sequence of virtual memory accesses into their corresponding physical memory addresses. You'll build a simulator that will keep a single-level page table for one process and update the page-to-frame memory mappings as the process accesses virtual memory addresses. You'll be simulating the page table and physical memory rather than using Linux because:

The details of memory hardware are nasty, particularly for architectures like x86 that have been around for a long time and support lots of backwards-compatibility features.
If your non-simulated implementation breaks, you're unlikely to get much feedback, making development very frustrating.
Building an abstract simulator should cover the important high-level concepts without bogging us down in architectural details.

The provided starter code has three main components:

frames.h & frames.c: Simulates physical memory (frames).
pages.h & pages.c: Simulates virtual memory mappings (page table) and tracks the page replacement policy.
simulator.c: The main file that reads a sequence of addresses, performs memory mappings, and prints the results.

Your simulator will take several parameters to vary the characteristics of the memory system you're simulating, including the size in bytes of a page/frame, the size in bytes of the virtual address space, the size in bytes of the physical address space, and the page replacement policy to use.

Requirements

Your simulator should read a sequence of virtual memory addresses from a memory-mapped file. The file will contain addresses that are stored as 64-bit integers in a little-endian binary format (the native format for integers on x86).

The simulator already reads in sizes of a page/frame, virtual address space, and physical address space (all in bytes). It passes those values to the physical and virtual memory initializers, which you will write. Those initializers should set up the memory based on the provided sizes. You may assume that:
1. The page/frame size will evenly divide the VAS and PAS sizes.
2. The page/frame size will be a power of two.
3. The VAS size will be a power of two.

Your simulator can print any debugging information you'd like to the standard error stream, but standard out should be reserved for you results, which should be formatted as follows: for each input virtual address, you should print the corresponding full physical address that it maps to, followed by a newline (\n). Each address should be printed as a 64-bit hexadecimal number with a "0x" prefix and any necessary leading zeroes to pad the length of the address to 16 hex digits. The starter code has an example of the printf format you should use.

Finally, after all the addresses have been translated and printed, you should print the total number of page faults that occurred during your translations.

When initializing physical memory, frame 0 should be permanently reserved for the OS. You should initialize all other frames as free. When you detect a page fault (you are asked to map a page that is not in physical memory), you should first check physical memory to see if any frames are available. If so, you should give the faulting page the lowest numbered free frame and mark the frame as in-use.

When you detect a page fault after all frames are full, you'll need to evict a mapped page to make room for the one that's faulting. Your simulator should support two page replacement policies to choose a victim page: LRU and Clock. The selected policy will be passed in as a command line parameter as in integer using constants that are defined in pages.h: POL_LRU (1) and POL_CLOCK (2). For LRU, you should track the full order of page usage and evict the least recently used page. For clock, you should initialize the clock hand to page 0.

You're welcome to add or modify structs, but you should not change any of the function prototypes in pages.h and frames.h. Any global state or helper functions you add to pages.c and frames.c should be static (only accessible in the file it's defined in). Adding helper functions in those files is strongly encouraged, but the simulator should ONLY be able to interact with physical memory using the functions declared in frames.h and the page table using functions declared in pages.h.

Your simulator should free all memory, close all files it's no longer using, and get a clean bill of health from valgrind: no invalid memory accesses, uninitialized variables, or memory leaks.

Tips

When getting started, you should sketch out your translate() function using the functions that are available to you in pages.h and frames.h, even if you haven't implemented them yet.

You can test your own memory address sequences by using the write_bytes.py python script to create a new mmapable input file.

Even though you'll only be using one page replacement algorithm at a time, it's probably easiest to keep state for both algorithms in your page struct rather than trying to dynamically allocate just one or the other (e.g., using lots void *'s, casting, and/or function pointers).

Bonus Competition

This portion of the lab is not required. It's for fun and a small amount of extra credit.

For a chance at extra credit and eternal CS 45 glory, you may optionally design and submit your very own page replacement algorithm.

Rules for participation:

To participate, you must define a third replacement policy, numbered 3, and write a brief description of the intuition behind your policy in a file named "competition.txt".

You may NOT look ahead in the stream of memory accesses. That is, your simulator must only consider the address it's currently translating plus any past information that it has seen, but it may not look at the addresses that will be accessed in the future.

You may NOT submit your LRU or Clock implementation as your competition submission. It needs to be a new algorithm of your design!

Prizes

I'll run your new policy on two address streams: one that has good locality, and another that has poor-ish locality. For each of the two inputs, I'll declare a winner and runner-up based on the total number of page faults. The winner gets 1 extra lab point, and the runner-up gets 1/2. In the interest of balance, a group can only win one of the two files, with the good locality file being determined first.

Submitting

Please remove any excessive debugging output prior to submitting.

To submit your code, commit your changes locally using git add and git commit. Then run git push while in your lab directory.

CS 45 Lab 4: Simulating a Page Table