Project 4: Virtual Memory Simulator

Build a trace-driven VM simulator that translates addresses, models TLBs, and compares page-replacement policies.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 12-18 hours
Main Programming Language C or Python
Alternative Programming Languages Rust, Go
Coolness Level High
Business Potential Medium (performance tooling)
Prerequisites Bitwise math, data structures
Key Topics page tables, TLB, replacement algorithms

1. Learning Objectives

By completing this project, you will:

  1. Implement address translation with page tables.
  2. Simulate TLB hits/misses and page faults.
  3. Compare FIFO, LRU, and Clock replacement policies.
  4. Explain locality and working set behavior.

2. All Theory Needed (Per-Concept Breakdown)

Address Translation and Page Replacement

Fundamentals

Virtual memory gives each process the illusion of a private, contiguous address space. The CPU translates virtual addresses into physical addresses using page tables. Each page table entry (PTE) contains metadata like present, dirty, and accessed bits. When a page is not present in RAM, a page fault occurs and the OS must load the page from disk, potentially evicting another page if memory is full. Replacement algorithms decide which page to evict, and TLBs cache recent translations to speed up access. Locality of reference means programs tend to access nearby addresses and reuse recently accessed pages, which is why LRU-like policies often outperform FIFO.

Deep Dive into the concept

Address translation is a layered cache hierarchy. A virtual address is split into a page number and an offset. The page number indexes the page table to find the physical frame number, which is then combined with the offset to form the physical address. A TLB caches recent page table entries, reducing the need to read memory for translation. In hardware, TLB misses can trigger a page table walk, which is itself a multi-step process on 64-bit systems with multi-level tables.

When RAM is limited, not all pages can stay resident. The OS maintains a set of resident pages (the resident set). If a page fault occurs and no free frames exist, the OS must evict a page. FIFO evicts the oldest loaded page. LRU evicts the least recently used page, which matches locality but is costly to implement exactly. The Clock algorithm approximates LRU by using a circular list of pages and a reference bit; it clears bits on the first pass and evicts when it finds a page with a cleared bit. These algorithms trade accuracy for overhead.

A simulator lets you explore these trade-offs without kernel code. You feed it a trace of virtual addresses and let it perform translation. Each access updates the accessed bit. Each miss triggers a replacement policy. You can model a simplified TLB as a small fully associative cache or direct-mapped cache. This shows how TLB size affects hit rates and overall performance.

Locality is the deeper concept behind these policies. Temporal locality means recently used pages are likely to be used again. Spatial locality means neighboring addresses are likely to be accessed together. LRU leverages temporal locality, while large page sizes exploit spatial locality. But larger pages can increase internal fragmentation. The simulator can show how page size affects fault rates by re-running traces with different page sizes.

The working set model states that a program has a set of pages it actively uses during a time window. If the number of frames is less than the working set size, thrashing occurs: continuous page faults with little progress. A simulator can demonstrate thrashing by reducing the frame count and observing fault rates explode. This provides a concrete, quantitative understanding of why memory pressure degrades performance.

How this fit on projects

This concept powers Section 3.2 (requirements), Section 4 (architecture), and Section 6 (testing). It connects to allocation (Project 3) and scheduling (Project 5).

Definitions & key terms

  • Page: Fixed-size block of virtual memory.
  • Frame: Fixed-size block of physical memory.
  • TLB: Cache of recent page table entries.
  • Page fault: Exception on access to a non-resident page.
  • Working set: Pages used within a recent time window.

Mental model diagram (ASCII)

Virtual Addr -> [VPN | offset]
   |
   v
Page Table -> frame
   |
   v
Physical Addr -> [PFN | offset]

How it works (step-by-step)

  1. Split virtual address into page number and offset.
  2. Check TLB for page number.
  3. If hit, use frame number.
  4. If miss, consult page table.
  5. If not present, handle page fault and replace a page.
  6. Update TLB and statistics.

Minimal concrete example

VA 0x1234, page size 4096
VPN = 0x1, offset = 0x234
PTE[1] -> frame 0
PA = 0x0 + 0x234

Common misconceptions

  • “TLB miss == page fault”: TLB miss can still hit in page table.
  • “LRU is always best”: its overhead can be too high.
  • “Bigger pages always better”: large pages can waste memory.

Check-your-understanding questions

  1. What is the difference between a TLB miss and a page fault?
  2. Why does LRU usually beat FIFO on locality-heavy traces?
  3. What does the accessed bit represent?
  4. How can thrashing be detected in a simulator?

Check-your-understanding answers

  1. TLB miss means cache miss; page fault means page not resident.
  2. LRU keeps recently used pages, matching temporal locality.
  3. It marks whether a page was referenced recently.
  4. Fault rate spikes as frames drop below working set size.

Real-world applications

  • OS memory managers and performance tuning.
  • Database buffer pool eviction policies.

Where you’ll apply it

  • This project: Section 3.2, Section 4.4, Section 6.2.
  • Also used in: Project 3, Project 5.

References

  • “OSTEP” Ch. 13-22
  • “Hennessy & Patterson” memory hierarchy chapters

Key insights

Virtual memory is a cache; replacement policy is the cache eviction policy.

Summary

By simulating translation and replacement, you can see exactly why locality drives OS performance.

Homework/Exercises to practice the concept

  1. Add a parameter for page size and plot fault rates.
  2. Implement Clock replacement and compare to LRU.
  3. Add a TLB with configurable size and associativity.

Solutions to the homework/exercises

  1. Run the same trace with page sizes 1K, 4K, 16K.
  2. Track accessed bit in a circular buffer.
  3. Implement an array of TLB entries with LRU timestamps.

3. Project Specification

3.1 What You Will Build

A command-line simulator that reads a trace of virtual addresses, translates them to physical addresses, counts TLB hits and page faults, and compares FIFO, LRU, and Clock replacement policies.

3.2 Functional Requirements

  1. Parse a trace file of virtual addresses.
  2. Translate addresses with a configurable page size.
  3. Simulate TLB hits/misses and page faults.
  4. Compare at least three replacement policies.

3.3 Non-Functional Requirements

  • Performance: handle 1M addresses quickly (<2 seconds in C).
  • Reliability: deterministic results for fixed inputs.
  • Usability: clear CLI flags and output.

3.4 Example Usage / Output

$ ./vm_sim trace.txt --pages=64 --frames=8 --algo=lru --seed 42
pages=64 frames=8 page_size=4096
TLB=16 entries
faults=812 hits=8234

3.5 Data Formats / Schemas / Protocols

  • Trace file: one hex address per line.
  • Stats output: counts and rates.

3.6 Edge Cases

  • Empty trace file.
  • Frames < 1.
  • Page size not power of two.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

./vm_sim trace.txt --pages=64 --frames=8 --algo=lru --seed 42

3.7.2 Golden Path Demo (Deterministic)

  • Fixed trace file and --seed 42 for any randomized tie-breaks.

3.7.3 If CLI: exact terminal transcript

$ ./vm_sim trace.txt --pages=64 --frames=8 --algo=lru --seed 42
VM Simulator
Pages=64 Frames=8 PageSize=4096
Algorithm=LRU
Accesses=10000
PageFaults=812
TLBHits=8234

Failure demo (deterministic):

$ ./vm_sim trace.txt --pages=64 --frames=0
error: frames must be >= 1

Exit codes:

  • 0 success
  • 2 invalid arguments
  • 3 trace file read error

4. Solution Architecture

4.1 High-Level Design

Trace Reader -> Translator -> TLB -> Page Table -> Replacement

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | Trace reader | Parse addresses | hex parse, ignore comments | | Page table | Track resident pages | array of PTEs | | Replacement | Choose victim page | FIFO/LRU/Clock | | TLB | Cache translations | small associative cache |

4.3 Data Structures (No Full Code)

struct pte {
    int present;
    int frame;
    int accessed;
    int dirty;
};

4.4 Algorithm Overview

Key Algorithm: LRU

  1. On access, update timestamp for page.
  2. On eviction, choose smallest timestamp.

Complexity Analysis:

  • Time: O(n) per eviction (or O(log n) with heap)
  • Space: O(pages)

5. Implementation Guide

5.1 Development Environment Setup

sudo apt-get install build-essential

5.2 Project Structure

project-root/
|-- vm_sim.c
|-- trace.txt
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How does the OS decide what stays in memory when RAM is smaller than the working set?”

5.4 Concepts You Must Understand First

  1. Page size and address bit splitting.
  2. Replacement policies and locality.
  3. TLB caching behavior.

5.5 Questions to Guide Your Design

  1. How will you represent time for LRU?
  2. What happens on a TLB miss but page table hit?
  3. How will you validate your simulator against expected outputs?

5.6 Thinking Exercise

Compute FIFO and LRU faults for the sequence: 1,2,3,4,1,2,5,1,2,3,4,5 with 4 frames.

5.7 The Interview Questions They’ll Ask

  1. Why are page tables multi-level?
  2. What is thrashing?
  3. Why does locality matter for performance?

5.8 Hints in Layers

Hint 1: Implement translation without replacement.

Hint 2: Add FIFO replacement.

Hint 3: Add LRU/Clock and compare.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | VM | OSTEP | 13-22 | | TLB | Hennessy & Patterson | 5 |

5.10 Implementation Phases

Phase 1: Translator (3-4 hours)

Goals: page table lookup and address translation. Checkpoint: correct translations for small examples.

Phase 2: Replacement (4-6 hours)

Goals: FIFO, LRU, Clock. Checkpoint: fault rates match hand-calculated examples.

Phase 3: TLB + metrics (3-5 hours)

Goals: TLB cache and hit rates. Checkpoint: summary output includes TLB hits.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | LRU tracking | timestamps vs list | timestamps | simpler to implement | | TLB model | direct-mapped vs assoc | fully associative | easier for first pass |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———-|———|———-| | Unit | Bit math | page number extraction | | Integration | Full trace | known fault counts | | Stress | Big trace | 1M addresses |

6.2 Critical Test Cases

  1. Frame count = 1 (max thrashing).
  2. Trace with repeated same page (near 0 faults).
  3. Page size changes shift fault rates.

6.3 Test Data

trace_small.txt:
0x0000
0x1000
0x2000
0x0004

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Wrong bit masks | incorrect pages | verify shift/mask math | | LRU not updated | LRU behaves like FIFO | update timestamps on hit | | TLB not invalidated | stale translations | clear on eviction |

7.2 Debugging Strategies

  • Print translation steps for a small trace.
  • Compare with a manual table for 10 accesses.

7.3 Performance Traps

  • O(n) scans on every access for large traces.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a pretty timeline display of frame contents.

8.2 Intermediate Extensions

  • Implement working set window measurement.

8.3 Advanced Extensions

  • Simulate multi-level page tables.

9. Real-World Connections

9.1 Industry Applications

  • OS paging systems and database caches.
  • Valgrind: heavy VM-like instrumentation.
  • Linux kernel: real replacement policies.

9.3 Interview Relevance

  • Page replacement and locality questions.

10. Resources

10.1 Essential Reading

  • OSTEP Ch. 13-22

10.2 Video Resources

  • OS course lectures on paging and TLBs

10.3 Tools & Documentation

  • man mmap for context

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain a TLB miss vs a page fault.
  • I can describe FIFO vs LRU vs Clock.

11.2 Implementation

  • Simulator outputs correct stats for known traces.

11.3 Growth

  • I can explain thrashing with evidence.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Address translation works with FIFO replacement.

Full Completion:

  • LRU and Clock implemented with TLB stats.

Excellence (Going Above & Beyond):

  • Multi-level page tables and working set visualization.