Virtual Memory

01 Lab overview

This lab contributes to U9.1 through U9.7, and to course learning outcomes CLO4 and CLO8.

02 Learning objectives

03 Background

3.1 Paging

Paging divides the virtual address space into fixed-size pages and physical memory into the same-size frames. A virtual address is split into a page number and an offset. The page table maps the page number to a frame number; the offset is unchanged. Because any page can be placed in any free frame, external fragmentation disappears. The cost is that the last page of a region is partly unused (internal fragmentation) and that every memory access requires an address translation.

3.2 Multi-level page tables

A single-level page table for a 48-bit address space with a 4 KB page size would have 2³⁶ entries — far too large to store per process. Modern systems use multi-level tables, in which the page number is split into several indices and only the parts of the table that correspond to used pages are allocated. On x86-64 the address is split into four 9-bit indices (PML4, PDPT, PD, PT) and a 12-bit offset. The MMU performs the four-level walk in hardware.

3.3 The TLB

The translation lookaside buffer (TLB) is a small, fully-associative or set-associative cache of recent page-table entries. On a TLB hit, the translation costs one cycle; on a miss, the MMU must walk the page table (in hardware) and the result is cached. For a program with good locality, the TLB hit rate is very high, and the effective cost of translation approaches zero. Huge pages (2 MB or 1 GB) increase the coverage of each TLB entry and are used for large working sets such as databases and virtual machines.

3.4 Demand paging

With demand paging, a page is loaded only when it is first referenced. The page table entry for a page that has never been loaded has its valid bit cleared; accessing it raises a page-fault trap. The kernel checks whether the reference is legal, finds a free frame (or evicts a page), reads the page from backing store (for a major fault) or maps it from an existing physical page (for a minor fault), updates the page table, and restarts the faulting instruction.

3.5 Page replacement

When no free frame is available, the kernel must evict a page. The classical algorithms are:

• FIFO: evict the oldest page. Simple; suffers Belady's anomaly.
• Optimal (OPT/MIN): evict the page whose next use is farthest in the future. Provides the minimum possible fault rate; used as a benchmark.
• LRU: evict the least-recently-used page. Approximates OPT; expensive to implement exactly.
• Clock (second-chance): an approximation of LRU using a reference bit; the standard in real kernels.
• LFU / MFU: least- and most-frequently-used; used in some database and cache settings.

3.6 Thrashing

Thrashing occurs when the sum of the working sets of the running processes exceeds physical memory. Every process faults constantly, the CPU is spent on page-fault handling and disk I/O, and useful throughput collapses. The kernel responds by suspending some processes (reducing the degree of multiprogramming) or by using a working-set or page-fault-frequency policy to decide which processes to run.

04 Guided activities

Activity 4.1 — Address translation by hand

1. Create the lab directory:

   mkdir -p ~/comp3150/lab8 && cd ~/comp3150/lab8

2. Given a 32-bit virtual address space with a 4 KB page size and a single-level page table, translate these virtual addresses to physical addresses given the following page table:

   Page  Frame
   0     5
   1     2
   2     9
   3     1
   4     7

   (a) 0x00000ABC, (b) 0x00001004, (c) 0x00002F00, (d) 0x00003FFC.
3. Write translate.c that performs the translation programmatically for a given page table and virtual address. Verify your hand calculations.
4. Extend the program to a two-level page table with 10 bits per level and a 12-bit offset. Translate the same addresses and confirm the result. Show the intermediate indices at each level.

Activity 4.2 — TLB simulation

1. Write tlb.c that simulates a fully-associative TLB with T entries and an LRU replacement policy. The program reads a stream of virtual page numbers and reports the hit rate.
2. Use a synthetic reference string with strong temporal locality (for example, a loop over a small array) and one with no locality (uniformly random page numbers). Compare the hit rates for T = 16, 64, and 256.
3. Reproduce a real-world workload from /proc/self/maps by interpreting the file as a sequence of page references (interleave the region start and end addresses). Report the TLB hit rate for the two traversal patterns from Lab 7 Activity 4.1.
4. Model a two-level TLB (a small L1 with 8 entries, a larger L2 with 64 entries). Report the L1 hit rate, L2 hit rate, and the average access cost (assume 1 cycle for L1, 5 for L2, 100 for a page-table walk).

Activity 4.3 — Demand-paging simulator

1. Write demand_paging.c that simulates a process with P virtual pages and F physical frames. The program takes a reference string (a sequence of page numbers) and an algorithm name, and reports the number of page faults and the fault rate.
2. Generate reference strings with the following characteristics and run each under FIFO, LRU, Clock, and OPT:
   • Sequential: 0, 1, 2, …, P−1, 0, 1, 2, …
   • Loop: repeated random picks from a small set of W pages (working set of size W).
   • Random: uniform random in [0, P).
   • Locality: 80% of references within a window of 16 pages, 20% outside.
3. For each combination, plot the fault rate against the number of frames F. Confirm the expected relationships: OPT is always at or below the others; LRU and Clock track each other closely; FIFO is worse and can be non-monotonic.
4. Demonstrate Belady's anomaly: construct a reference string on which FIFO has more faults with more frames. Report the string and the two fault counts.

Activity 4.4 — Working set and thrashing

1. Extend demand_paging.c to compute the working set W(t, Δ) — the set of pages referenced in the last Δ references — at each step. Plot the working-set size over time for the locality reference string and for a string that switches between two disjoint working sets.
2. Run the simulator with a small number of frames (F < |working set|). Show that the fault rate exceeds a threshold and that the simulated CPU utilisation collapses. This is the thrashing regime.
3. Implement the working-set policy: if the total working-set size of the running processes exceeds F, suspend one process (remove it from the simulation) and re-run. Report the improvement in fault rate for the remaining processes.
4. Implement the page-fault-frequency policy: if a process's fault rate exceeds a threshold, remove a frame from it; if it falls below a lower threshold, give it a frame. Compare the two policies.

Activity 4.5 — Page-fault counters on a real system

1. Write fault_bench.c that (a) allocates a large array with mmap, touches every page once, and exits; (b) does the same with MAP_POPULATE (which pre-faults the pages).
2. Run each under /usr/bin/time -v and record the minor and major fault counts. Explain why the pre-faulted run has far fewer minor faults.
3. Allocate a file-backed mapping with mmap on a file that has been dropped from the page cache (use posix_fadvise(POSIX_FADV_DONTNEED) or drop the cache with echo 3 > /proc/sys/vm/drop_caches if permitted). Touch the pages and record the major faults. Explain why a major fault requires disk I/O.
4. Run the program twice in a row without dropping the cache. The second run should show mostly minor faults because the pages are already in the page cache. Record the difference.

05 Exercises

06 Deliverables

Submit a single archive named lab8-<lastname>-<studentnumber>.tar.gz containing:

• translate.c — Activity 4.1 with both single-level and two-level translation.
• tlb.c — Activity 4.2 with both fully-associative and two-level TLB simulation.
• demand_paging.c — Activities 4.3 and 4.4, with FIFO, LRU, Clock, and OPT, and with working-set computation.
• fault_bench.c — Activity 4.5 and Exercise 4 (huge pages) and Exercise 5 (copy-on-write).
• lru_exact.c — Exercise 2.
• The Makefile with one target per program and a clean target.
• outputs.txt — the output logs of all programs with the commands that produced them.
• plots/ — the fault-rate and working-set plots (PNG or PDF).
• report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 5–7 pages (excluding code) and contain:

1. Address translation. The hand-computed translations, the program's output, and a diagram of the two-level walk for one of the addresses.
2. TLB analysis. The hit rates for the two workloads and the two-level TLB, with the average access cost calculation.
3. Replacement algorithm comparison. The fault-rate plots, the OPT benchmark, and the observed Belady anomaly with its reference string.
4. Thrashing analysis. The working-set plots and the throughput measurements showing the collapse under over-commitment, and the improvement after applying the working-set policy.
5. Real-system measurements. The minor and major fault counts for the different fault_bench variants, with an explanation of each.
6. Reflection. A discussion of how Linux's page-fault handler, reverse mapping, and page-reclaim mechanism work together to keep the fault rate low, and how huge pages and transparent huge pages change the picture for large working sets.

07 Grading rubric

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

Page   Frame
0x7F   0x1A
0x7E   0x2B
0x7D   0x09

1 2 3 4 | 1 2 5 1 2 3 4 5
1: 1 F   [1]
2: 2 F   [1 2]
3: 3 F   [1 2 3]
4: 4 F   [1 2 3 4]
1: 1 H   [1 2 3 4]
2: 2 H   [1 2 3 4]
5: 5 F   evict 1 → [5 2 3 4]
1: 1 F   evict 2 → [5 1 3 4]
2: 2 F   evict 3 → [5 1 2 4]
3: 3 F   evict 4 → [5 1 2 3]
4: 4 F   evict 5 → [4 1 2 3]
5: 5 F   evict 1 → [4 5 2 3]

1 2 3 4 | 1 2 5 1 2 3 4 5
1: 1 F   [1]
2: 2 F   [2 1]
3: 3 F   [3 2 1]
4: 4 F   [4 3 2 1]
1: 1 H   [1 4 3 2]
2: 2 H   [2 1 4 3]
5: 5 F   evict 3 (LRU) → [5 2 1 4]
1: 1 H   [1 5 2 4]
2: 2 H   [2 1 5 4]
3: 3 F   evict 4 → [3 2 1 5]
4: 4 F   evict 5 → [4 3 2 1]
5: 5 F   evict 1 → [5 4 3 2]

09 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 10.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 18–23.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3.
• Denning, P. J. The Working Set Model for Program Behavior. Communications of the ACM, 1968.
• Belady, L. A., Nelson, R. A., & Shedler, G. S. An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine. Communications of the ACM, 1969.
• Corbet, J., Rubini, A., & Kroah-Hartman, G. Linux Device Drivers, 3rd ed., Chapter 15 (memory mapping and DMA).
• Linux man-pages: man 2 mmap, man 5 proc (/proc/<pid>/smaps, /proc/vmstat), man 1 perf.
• Gorman, M. Understanding the Linux Virtual Memory Manager. Prentice Hall, 2004.