CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes third

In this module you will

  • Split a virtual address into a page number and an offset for any page size that is a power of two.
  • Translate an address through a page table by hand and in C, and spot the case that causes a trap.
  • Read the fields of a page table entry.
  • Compute the size of a flat page table, and the average internal waste, for different page sizes.
  • Read real page table entries from the kernel on a Linux machine.

Page 2 ended with a problem and a hint: memory cut into variable-sized regions fragments badly, and equal-sized pieces would solve it. This page makes that idea exact. It is the central idea of the whole level: nearly everything later, from the TLB to page faults and replacement, builds on the translation described here. The sources are OSTEP chapters 18 and 19, OSC chapter 9 and MOS chapter 3. The C code was compiled with gcc -O2 -Wall -Wextra and run on a two-processor Linux machine with 4,096-byte pages.

About this example About this example

Real: The C programs, commands and outputs on this page were compiled with gcc -Wall -Wextra -pthread and run on a Linux test machine (2 processors, kernel 6.18, glibc 2.39).

Scripted: The worked traces use small numbers chosen so they can be followed by hand.

Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.