Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 67 ยท Projects

Project: A Virtual Memory Manager

Build a virtual memory simulator with a two-level page table, a TLB, demand paging and FIFO, LRU and Clock replacement, then measure address traces.

Every address your program uses is fiction. The processor and the operating system together translate each virtual address into a real physical address, using page tables to find the mapping, a small cache called the TLB to make it fast, and the disk as a backing store when physical memory runs out. In this project you build that machinery in about a hundred lines of Python and watch it work on address traces.

It puts together Virtual Memory and Paging and TLBs and Page Replacement Algorithms. You will implement translation, demand paging, three replacement policies and dirty-page tracking, then measure page faults, TLB hit rates and the memory the page tables themselves need.

The design

To keep the numbers small, the simulated machine has 16-bit virtual addresses and 256-byte pages. An address splits into three fields:

Bits 15 to 12 11 to 8 7 to 0
Field level-1 index level-2 index page offset

The top 8 bits together are the virtual page number (VPN). The page table is two-level: the level-1 table has 16 slots, each pointing to a level-2 table of 16 entries. A level-2 table is only created when a page in its range is first used, which is how multi-level tables save memory for sparse address spaces.

Each page table entry (PTE) holds a valid bit, a frame number and a dirty bit. Physical memory is a small set of frames, so the simulator needs a replacement policy to choose a victim when all frames are in use. It supports:

  • FIFO: evict the page that has been in memory the longest.
  • LRU: evict the page whose last use is the oldest.
  • Clock: an approximation of LRU. Each frame has a reference bit that is set on use. A hand sweeps through the frames; a frame with the bit set gets a second chance (the bit is cleared), and the first frame found with the bit clear is evicted.

The TLB caches recent translations (VPN to frame). It is searched first; on a TLB miss the hardware walks the two-level table, and on a missing page (invalid PTE) the operating system takes a page fault, loads the page into a frame and updates the table.

flowchart TD
  A["Virtual address"] --> T{"VPN in TLB?"}
  T -->|"yes"| P["Physical address = frame + offset"]
  T -->|"no"| W["Walk level-1 then level-2 table"]
  W --> V{"PTE valid?"}
  V -->|"yes"| U["Fill the TLB"]
  V -->|"no: page fault"| F["Pick a frame<br/>evict a victim if none is free"]
  F --> L["Load the page, update the PTE"]
  L --> U
  U --> P

Translation: a TLB hit finishes at once; a miss walks the table; an invalid entry triggers a page fault.

Step 1: translate a trace by hand

The class below is the whole manager. access(vaddr, write) performs one memory reference and returns the physical address plus a log of what happened. The detail that is easy to miss: when a page is evicted, its PTE must be marked invalid and its TLB entry removed, or the TLB would keep translating addresses to a frame that now belongs to another page. Dirty pages are counted as write-backs, because they would have to be written to disk before the frame is reused.

The first program makes a small machine with only 3 frames and a 2-entry TLB so that every kind of event shows up in 8 references.

Python Translate addresses, faults and evictions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the first rows. The reference to 0x0123 splits into level-1 index 0, level-2 index 1 and offset 35 (0x23). The TLB is empty, so the manager walks the table, finds no valid entry and takes a page fault, loading the page into the free frame 0. The physical address is frame 0 followed by the same offset: 0x0023. The page offset never changes in translation. The next reference, 0x0145, is in the same page (VPN 0x01), so it is a TLB hit with no table walk.

Skip to the sixth line. All three frames are full, the least recently used page is 0x12 (frame 1), and it was written to earlier, so evicting it is marked as dirty and costs a write-back. The final two references show the cost of a too-small memory: the page 0x1210 and then 0x0123 have to be brought back immediately after being evicted. The last lines also count page-table memory: 4 second-level tables are enough for 4 touched regions, so the table uses 80 entries instead of the 256 a flat table would need.

True LRU needs a timestamp update on every memory reference, which hardware cannot afford. That is why real operating systems approximate it with reference bits, as the Clock policy does here.

Step 2: measure policies on a realistic trace

A handful of references proves the mechanics, but policy comparisons need thousands. The next program builds a trace of 6,000 references in six phases. In each phase, 90% of references go to a small working set of 5 to 8 adjacent pages, and 10% go to random pages. A quarter of the references are writes. The seed is fixed, so everyone gets the same trace.

It then runs every policy with different amounts of physical memory and prints the number of page faults, and finally varies the TLB size.

Python Page faults by policy and memory size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The page-fault table shows the standard picture. More frames mean fewer faults for every policy, with diminishing returns. LRU wins at every size: with 8 frames it takes 923 faults against FIFO's 1,418. FIFO is the worst because it evicts the oldest page, and a page in the hot working set is often the oldest. Clock lands in between (1,138 faults at 8 frames) at a fraction of LRU's bookkeeping cost, which is why it is the basis of many real implementations. When memory is very small (4 frames, smaller than most working sets), all three policies do badly and are only a few percent apart: no policy can rescue a working set that does not fit.

FIFO has a strange failure mode called Belady's anomaly: for some traces, giving it more frames increases the number of faults. LRU never behaves this way, but Clock, which is FIFO with second chances, still can. This trace does not trigger it, but you can search for a trace that does by testing small hand-written sequences.

The TLB table behaves differently. Page faults are the same (923) for every TLB size, because the TLB only caches translations; it does not decide what is in memory. The hit rate grows from 14.5% for one entry to 84.6% for eight, and then stops. At that point, every reference to the 5 to 8 page working set hits, and the remaining 15% are the random strays, which no small TLB can capture. This is the reach of a TLB: entries multiplied by page size is how much memory it can cover (here 8 entries cover 2 KB).

The last line reports 915 evictions with 387 write-backs. Each write-back is a disk write that would take milliseconds on a real system. Operating systems reduce this by writing dirty pages back in the background before the frame is needed.

Step 3: how much memory do page tables use?

The page table itself lives in memory, and a table that maps every page of a big address space would be huge. The two reasons for multi-level tables show up in numbers. The program below counts the table entries needed for a process with three regions (code, heap and stack), first in a 32-bit machine with 4 KB pages and a 10 + 10 bit split, then on a 48-bit machine with 4 levels of 9 bits and 8-byte entries, similar to x86-64.

It ends with the effective access time (EAT) formula. Every access pays the TLB lookup; on a TLB miss it pays one memory read per table level; and a page fault adds a disk access of about 8 milliseconds.

Python Page table size and effective access time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The process maps 592 pages, 2,368 KB of real memory. A flat 32-bit table would take 4,096 KB for 1,048,576 entries, more than the process itself. The two-level table needs only 4,096 entries, or 16 KB: one top-level table and three second-level tables for the three regions. On a 48-bit machine, the gap is astronomical: a flat table would need 2^36 entries, 512 GB, while four levels need 40 KB for the same process.

The EAT table has the lesson every systems programmer remembers. With a 99% TLB hit rate and no faults, an access takes about 103 ns, barely more than memory alone. Lowering the TLB hit rate to 50% doubles that to 201 ns. But page faults are in another league: just one fault per 10,000 accesses (a rate of 0.0001) pushes the average to 903 ns, nine times slower, and one per 1,000 reaches 8,103 ns. Because a fault is about 80,000 times more expensive than a memory access, the fault rate must be kept extremely low, which is why a program whose working set does not fit in RAM "falls off a cliff" (thrashing).

Ideas to extend it

  • Add the Optimal policy (evict the page used farthest in the future) as a benchmark; it needs the whole trace in advance, so only a simulator can run it.
  • Add per-process address spaces with an address-space ID in each TLB entry, so that a context switch does not flush the TLB.
  • Support huge pages: let a level-1 entry map a whole 4 KB region directly, and see how much the TLB reach grows.
  • Add protection bits (read, write, execute) and raise a fault on a write to a read-only page; copy-on-write follows naturally.
  • Add a page-fault frequency monitor that warns when the fault rate suggests thrashing.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A page is evicted from physical memory. What else must the manager do besides marking its PTE invalid?

    The TLB caches the old VPN to frame mapping. If it stayed, a later access would use a frame that holds a different page.
  2. 2. In the 16-bit design with 256-byte pages, how many bits make the page offset?

    256 bytes is 2^8, so the low 8 bits are the offset and are copied unchanged into the physical address.
  3. 3. Why did FIFO produce more page faults than LRU on the phase-based trace?

    Age since loading says nothing about recent use. LRU evicts the page unused the longest, which is a better guess about the future.
  4. 4. Why does the TLB size not change the number of page faults in the second experiment?

    A TLB miss just costs a table walk. A fault happens when the page is not in physical memory, which the TLB does not control.
  5. 5. What is the main reason for using a multi-level page table?

    A flat table must have an entry for every possible page; a multi-level table allocates only the branches that are actually used.

Summary

  • A virtual address splits into table indexes and a page offset; translation replaces the page number with a frame number and keeps the offset.
  • The TLB caches translations. A miss triggers a table walk; an invalid entry triggers a page fault handled by the operating system.
  • Evicting a page means invalidating its PTE and its TLB entry, and writing it back if it is dirty.
  • FIFO, LRU and Clock give different fault counts for the same trace: LRU is best here, Clock is a cheap approximation, FIFO is worst.
  • TLB reach is entries times page size; once the working set fits, a bigger TLB does nothing.
  • Multi-level tables allocate only the tables that are used, saving enormous memory in sparse address spaces.
  • Page faults dominate the effective access time, so keeping the fault rate tiny matters far more than any other tuning.

The last project goes down to the bottom of the stack: Project: A Gate-Level Logic Simulator.