Part 7 of 7 · 4 min read
Exercises
Easy
Easy 1: One EAT with faults (20 minutes)
A memory access takes 200 ns and a fault takes 8 ms to service. One access in 1,000 faults. Find the EAT.
Done when: 0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8,000 = 8,199.8 ns, about 41 times slower.
Hint
(1 − 0.001) × 200 plus 0.001 × 8,000,000.
Easy 2: Name the fault (20 minutes)
Say whether each event is a minor fault, a major fault, or a segmentation fault: (a) the first write to a new heap page; (b) a read of a code page of a program that was never run before, on a machine whose file cache is empty; (c) a write to the first page of the program's code region; (d) a read of an address in no region.
Done when: (a) minor, (b) major, (c) segmentation fault, since code is read-only, (d) segmentation fault.
Hint
Code regions are read-only; an address in no region is never legal.
Easy 3: Order the steps (20 minutes)
Put in order: update the page table entry; trap to the kernel; check that the address is legal; run the instruction again; fill the frame; find a free frame.
Done when: trap, check the address, find a frame, fill the frame, update the entry, run the instruction again.
Hint
The legality check comes before the search for a frame.
Medium
Medium 1: The largest fault rate (45 minutes)
With a 200 ns access and an 8 ms service time, find the largest fault rate that keeps the slowdown at 10% or less. Say how many accesses may pass for each fault.
Done when: p ≤ 20 / 7,999,800, about 2.5 × 10⁻⁶, which is one fault in 400,000 accesses.
Hint
Solve (1 − p) × 200 + p × 8,000,000 ≤ 220.
Medium 2: Count faults in a reference string (45 minutes)
A process uses pure demand paging and has enough frames for all its pages. It reads pages 0 1 0 2 1 3 0 2 in this order. Count the faults and name the references that fault.
Done when: 4 faults, on the first uses of pages 0, 1, 2 and 3 (the 1st, 2nd, 4th and 6th references).
Hint
A page faults only on its first use when memory is large enough.
Medium 3: Count minor faults (60 minutes)
Compile the program of section 3 and run it. Change the size to 128 MiB and the loop to touch each page twice. Report the minor faults for both sizes.
Done when: 16,384 and 32,768 faults for the first touch (plus a few from the C library), with a note that the second touch added none.
Hint
Use getrusage before and after, as in the listing.
Hard
Hard 1: Touch only some pages (90 minutes)
Map 64 MiB and write to one page in every 16. Report the faults, and read the resident size of the process from /proc/self/status (the VmRSS line) before and after.
Done when: 1,024 minor faults, and a resident size that grew by about 4 MiB, not 64 MiB.
Hint
Use a step of 16 pages in the loop, and keep madvise with MADV_NOHUGEPAGE.
Hard 2: Fault-around on a file (90 minutes)
Create a 64 MiB file, map it, and read one byte in each page. Compare the minor faults with those of the anonymous test. Then call madvise with MADV_RANDOM on the mapping and run again.
Done when: a table of fault counts for both cases and one sentence on how the hint changes the kernel's prefetching.
Hint
Open the file with open, map it with PROT_READ and MAP_PRIVATE.
Hard 3: Cost of a major fault (90 minutes)
Create a 256 MiB file and drop it from the file cache (run sync and write 3 to /proc/sys/vm/drop_caches as the administrator, or use posix_fadvise with POSIX_FADV_DONTNEED). Map it and read one byte in each page, once in order and once in random order. Report the major faults and the time per page for both.
Done when: two numbers per run, and a sentence on how the type of storage (solid state or spinning disk) changes the answer.
Hint
Use a shuffled list of page numbers for the random run, and time only the reads.