Unit 1.5 · about 6 h
234 / 324Virtual memory, page tables, TLBs, page faults and mmap
Assume Programming's integers-pointers-spans and ownership-raii-move units. A valid pointer is a virtual address, not a promise of residency or a cheap access. Connect translation to kernel allocation, copy-on-write and file-backed I/O before interpreting memory totals.
- explain
- measure
You can now
- Translate a virtual address with a stated page size, PTE validity and permissions.
- Explain a hardware TLB miss, a recoverable page fault and an invalid access as distinct paths.
- Measure first-touch versus repeated-touch fault deltas and verify private copy-on-write semantics.
- Choose private versus shared mappings and identify alignment, lifetime and truncation hazards.
Covers
- Virtual addresses, address translation, pages and page tables
- TLBs, page faults, copy-on-write and memory mapping
Study, in this order
6 steps
- Paging, translation caches and faultsOperating Systems: Three Easy Pieces - selected foundations
Chapter 18, Sections 18.1 to 18.4; Chapter 19, Sections 19.1 to 19.5; Chapter 20, Section 20.3; Chapter 21, Sections 21.2 to 21.5 (other chapters linked from the book contents)
Depth · Keep the models' address widths explicit. Chapter 21's swapped-page example is not every Linux fault: demand-zero, cached-file and copy-on-write faults need no storage read. Skip replacement-policy derivations beyond the short simulator practice.
- Linux fault classification and private writesAlgoMaster Operating Systems - selected observation route
Minor and Major Page Faults; TLB Miss, Minor Fault, and Major Fault; Measuring Page Faults on Linux
- Copy-on-write after forkAlgoMaster Operating Systems - selected observation route
Initial CoW Setup; The Write-Fault Path; Frame Reference Counts; What Is Shared After fork()
- Mapping semanticsAlgoMaster Operating Systems - selected observation route
On-Demand Residency of File Pages through Mapping Lifetime and File Descriptors; Visibility vs. Durability;
mmap()Versusread() - mmap API contractLinux proc and strace references
DESCRIPTION:
offset,MAP_SHARED,MAP_PRIVATEandMAP_ANONYMOUS; ERRORS:SIGBUS; NOTES on fork and file sizeDepth · Ignore
MAP_FIXED,DAXand explicit huge-page tuning. Keep ownership of mappings separate from ownership of descriptors. - Page-table inspection and ugetpid designMIT 6.1810 - selected xv6 process and memory labs
Inspect a user-process page table; Speed up system calls
Depth · Explain the handout's entries and sketch the read-only USYSCALL lifecycle. Running the lab needs the xv6 RISC-V toolchain and QEMU; stop before Print a page table and Use superpages.
Focus on
- Translation changes the frame number, not the offset. PTE permissions, the virtual region's policy and residency determine whether access proceeds or faults.
- The x86 hardware walks page tables on a TLB miss; the kernel resolves faults. A TLB miss is not necessarily a page fault or a storage access.
- Private writable pages can share frames after fork until a write fault. A sole owner may regain write permission without copying; shared mappings have different semantics.
- File mappings use the page cache. Closing the descriptor does not unmap them, and
MAP_PRIVATEis not a guaranteed snapshot against external file changes.
Reproduce closed-book
SC_PAGE_SIZE, creates a 16*1024*1024-byte anonymous mapping with explicit MAP_PRIVATE|MAP_ANONYMOUS and applies MADV_NOHUGEPAGE. Snapshot resource.getrusage(RUSAGE_SELF).ru_minflt and ru_majflt immediately before and after writing byte value 1 at range(0, length, page_size); repeat the same pass on the same mapping. Run three fresh processes with taskset -c 2 python3 -I faults.py (CPython 3.14.4), recording CPU, kernel and all deltas. Predict first-touch minor faults on the scale length/page_size: three reference runs on Linux 7.0 gave exactly 4096 minor and 0 major faults on the first pass and 0 on the second. Then fork, have the child set byte 0 to 2 and exit, reap it and assert the parent's byte remains 1. Close the mapping. State that this tests private semantics, not the number of physical copies or storage latency.Traps
- Using Python's default anonymous mmap sharing mode and expecting private copy-on-write. Pass
MAP_PRIVATEexplicitly. - Counting one fault per base page without checking huge-page policy, readahead, reclamation or counter scope.
- Treating successful mmap as prefaulting all bytes, or accessing a mapped file after unsafe truncation.
Practice
OSTEP `paging-linear-translate.py`: valid and invalid translations
README Overview; -s 1 and -s 2 with -a 16k -p 64k -P 4k -n 5 -v
Write VPN, offset, validity and physical address for every generated address before adding -c. The valid-bit model is simplified, not Linux's full fault handler.
OSTEP `paging-policy.py`: a bounded resident set
README Overview; -s 1 and -s 2 with -n 10 -C 3 -m 5 -p LRU
Predict hit/miss and each eviction before adding -c, then compare FIFO on the same traces. Stop at working-set pressure; do not infer Linux reclaim policy from this simulator. The section mini-project should retain the first-touch and private-write evidence.
Self-test
-
With 4096-byte pages, VA 0x12345 and a valid VPN-to-frame mapping 18 -> 7, what is the physical byte address?
VPN is \(0x12 = 18\), offset is \(0x345 = 837\), and PA is \(7 \times 4096+837 = 29509 = 0x7345\), provided the access permissions allow it. -
How large is a linear table for a full 32-bit virtual space with 4 KiB pages and four-byte PTEs?
\(2^{20}\) entries times four bytes = 4 MiB. This excludes extra metadata and is not a claim about the host's multi-level x86-64 tables. -
Can a resident file page cause a minor fault?
Yes. The page can be in the page cache while this process still lacks a usable PTE. Installing the mapping needs no storage read. -
Does flushing a private file mapping publish its private writes into the file?
No.MAP_PRIVATEwrites belong to private copies. A shared writable mapping or explicit file writes are needed to change the backing file.
Completion criterion
Stop when
You solve both two-seed translation and residency exercises, classify your first/repeated-touch counters without confusing faults with TLB misses, and pass the parent/child private-write assertion.
Mark passed, then open 1.6 Only mark this when you can do it without notes.Leads to
- 1.6 Resident size, virtual size and allocator retention Account for mappings, resident pages and retained allocator capacity.
- 1.8 I/O access patterns and storage devices Compare mapping and buffered reads under matched cache conditions.
Comes after
- 1.2 Caches, working sets, bandwidth and NUMAAdd translation and residency to the memory-access path.
Resources for this unit
- Operating Systems: Three Easy Pieces - selected foundations Read Chapters 4-7, 13-15, 18-21, 36, 39-40, 42 and 45. Work from process state to address translation, devices, files, journaling and integrity. For every chapter, draw the owned state and one failure boundary instead of collecting summaries.
- MIT 6.1810 - selected xv6 process and memory labs Use Fall 2025 Lectures 1, 3-6, 8 and 10-11. Complete the util lab, one syscall task, and the page-table inspection plus ugetpid task from pgtbl. Add cow only if copy-on-write remains unclear. Keep all work in your own course checkout and stop before the full xv6 sequence.
- AlgoMaster Operating Systems - selected observation route After OSTEP, use the matching lessons as a second explanation and recall check: fork, exec, wait, and exit; Zombies and Orphans; Signals; Context Switching; The Process Address Space; Paging; The TLB: Hits, Misses, and Invalidation; Page Faults; Copy-on-Write; mmap and Memory-Mapped Files; How malloc Works; VSZ, RSS, PSS, and What They Mean; File Descriptors; The Page Cache and Write-Back; Durability and fsync; Crash Consistency; Linux Namespaces; Control Groups; PID 1 and Signal Handling; Container Resource Failures; and the Investigating lessons. Treat quizzes as recall checks and keep your own traces as evidence.
- Linux proc and strace references Use proc(5), getrusage(2), mmap(2), fsync(2), rename(2), wait(2) and signal(7) while tracing a parent-child pipe, page faults, file publication and a resource-limit failure. Record exact commands and raw observations.
Also in this section
- OSTEP homework - process, paging, disk and integrity simulators Solve process-run.py, paging-linear-translate.py, paging-policy.py, disk.py, fsck.py and checksum.py for at least two seeds each before using the answer flag. Then reproduce one prediction using strace, /proc or a small local program.
- Nand2Tetris - Projects 1 and 4 only Use Project 1 for Boolean logic and Project 4 for machine-language execution only if the binary or instruction-level entry check fails. Do not take the full course as a second systems curriculum.
- Algorithmica - Algorithms for Modern Hardware Use the Instruction-Level Parallelism, SIMD Parallelism and RAM & CPU Caches chapters for measured pipeline, branch, vectorization, bandwidth, latency and cache-line effects. The figures are the author's Zen 2 measurements at a fixed 2 GHz: predict and measure your own.
- MIT 6.S894 Accelerated Computing - Throughput Processors Use Lecture 2 for the processor model behind this section: superscalar issue, out-of-order execution, speculation and SIMD's need for coherent control. The labs run on the course's remote machines and target AVX-512 and NVIDIA GPUs, so they belong to the GPU track.
- Auto-Vectorization in LLVM Use The Loop Vectorizer Usage and Diagnostics sections for the Clang remarks the pipelines unit asks for; the Features list is optional depth.
- AlgoMaster: hardware and container storage companions Use Memory Ordering, Barriers, and False Sharing (coherence and false-sharing headings only); Huge Pages, NUMA, and ASLR (NUMA headings only); Storage Hardware; RAID Fundamentals (comparison and backup boundaries); and Container File Systems. These fill hardware and image-layer gaps outside the pool's selected OS revision lessons.