Project 19: Virtual Memory Simulator

Project 19: Virtual Memory Simulator

Make virtual memory visible by simulating page tables, a TLB, and page replacement on real address traces.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate ~2 weeks
Language C (Alternatives: C++, Rust)
Prerequisites Comfortable with bitfields/masks, basic data structures
Key Topics Page tables, TLB, page faults, replacement policies, dirty/writeback
CS:APP Chapters 9

1. Learning Objectives

By completing this project, you will:

  1. Translate virtual addresses to physical frames using a multi-level page table model
  2. Implement a TLB cache and quantify hit rates vs. page-table-walk costs
  3. Implement FIFO/LRU/Clock replacement and compare fault/writeback tradeoffs
  4. Produce a reproducible report from a trace file (stats + optional visualization)

2. Project Specification

2.1 What You Will Build

A CLI called vmsim that consumes an address trace and simulates:

  • Configurable page size (e.g., 4 KiB)
  • Configurable physical frames (e.g., 4, 64, 1024)
  • Optional TLB with capacity and replacement policy
  • Page replacement policies: FIFO, LRU, Clock
  • Dirty tracking and writeback accounting

2.2 Example Output

$ ./vmsim --frames=64 --page-size=4096 --tlb=32 --replace=clock trace.txt
accesses=100000 tlb_hits=87234 tlb_misses=12766
page_hits=99012 page_faults=988 writebacks=234

3. Solution Architecture

3.1 Data Model

  • Page table: represent levels explicitly (arrays) or sparsely (hash maps) depending on trace size.
  • Frame table: per-frame metadata {vpn, valid, dirty, refbit, last_used}.
  • TLB: fixed-size entries {vpn, pfn, valid, dirty/ref} + policy metadata.

3.2 Address Breakdown (Typical x86-64-style)

Virtual Address:
  [ VPN (high bits) | Offset (low bits) ]
                 page_size = 2^k  => offset = k bits

Your simulator doesn’t need to exactly match a real CPU’s 4-level structure, but it should mimic the idea: hierarchical translation + caching.

4. Phased Implementation

  1. Parse trace lines into {op, vaddr} and compute {vpn, offset}
  2. Single-level page table + FIFO replacement
  3. Dirty bit + writeback accounting
  4. LRU via timestamps/counters (or an LRU list)
  5. Clock algorithm with reference bit
  6. Add a TLB, measure impact, and produce a summary report

5. Testing Strategy

  • Tiny hand-written traces where you can predict faults/hits exactly.
  • Property tests: frame count 1 behaves like “every new vpn faults”.
  • Cross-check replacement logic with an independent reference implementation for small traces.

6. Extensions

  • Visualize “working set” size over time.
  • Model copy-on-write and shared pages (two processes, same vpn mapping).
  • Add huge pages and compare TLB hit rates.

7. Reference Reading

  • CS:APP 3e — Ch. 9 (Virtual Memory)
  • Operating Systems: Three Easy Pieces — memory chapters (replacement)