Unit 1.8 · about 4 h
237 / 324I/O access patterns and storage devices
Assume Programming's data-formats-ingestion and profiling-benchmarking units. Keep parsing out of the timed region. This unit owns the access path and cache-state controls, not a second serialization throughput benchmark.
- measure
You can now
- Compare sequential, seeded-random and strided reads under explicitly matched warm-cache conditions.
- Explain buffered versus mapped I/O work and report the correct byte denominator for each measurement.
- Explain HDD positioning, SSD translation/garbage collection, NVMe queues and RAID failure boundaries without inferring device behavior from cache-hit timings.
Covers
- Sequential, random, strided, buffered and memory-mapped I/O
- RAID, SSD and device scheduling vocabulary
Study, in this order
4 steps
- Device service mechanismsOperating Systems: Three Easy Pieces - selected foundations
Chapter 36, Sections 36.3 to 36.5 and 36.7
Depth · Draw polling, interrupts and DMA ownership. DMA moves bytes without a CPU copy loop; it does not eliminate setup, completion or coherence work.
- The Page Cache and Write-BackAlgoMaster Operating Systems - selected observation route
The Cached Read Path; Read-ahead; The Shared Cache for Memory-Mapped Files; Write-Back: Moving Dirty Data Toward Storage
Depth · Relate mmap faults to the shared file cache. A warm read can still pay syscall, copy, translation and interpreter costs.
- Storage HardwareAlgoMaster: hardware and container storage companions
Hard Disk Drives; Solid-State Drives; NVMe Exposure of SSD Parallelism
Depth · Use seek/rotation/transfer, FTL, erase blocks, garbage collection and write amplification as vocabulary. No cold-device or endurance benchmark is required.
- RAID FundamentalsAlgoMaster: hardware and container storage companions
Comparing the Common Levels; Data-Integrity Limits of RAID; RAID vs. Backups
Depth · Optional device repair reading only. Distinguish capacity and disk-failure tolerance from corruption, deletion and independent backup recovery.
Focus on
- Buffered read copies cache bytes into user buffers. Mmap installs mappings and faults as needed; reading one byte per block does less user-level copying than reading every block into a buffer.
- Prewarm the whole file before each variant. Warm page-cache state is not a promise of warm CPU caches or installed mmap PTEs; fsync and reopening do not evict cached pages. Never drop global caches on a shared host.
- HDD access combines positioning and transfer. SSD random access avoids mechanical seeks but still depends on queues, flash layout, controller policy and garbage collection.
- RAID is not a backup. Corruption, application deletion and correlated failures can affect every replica or parity set; usable capacity and tolerated disk losses depend on the level.
Reproduce closed-book
i with byte i%256, flush and fsync outside timing. Prepare orders range(4096), a copy shuffled by random.Random(7), and [(j*17)%4096 for j in range(4096)]; assert each visits every block once. Before every trial, read the full file in 1 MiB chunks to prewarm the page cache. Time with perf_counter_ns: os.pread(fd,4096,i*4096)[0] over each order; a fresh read-only mmap over each order reading mapping[i*4096]; and buffered f.read(4096)[0] in sequential order after seek(0). Include mapping creation/close in its timed scope. Sum sampled bytes; every result must equal 522240. Run five trials of every variant with TMPDIR on a disk-backed filesystem (findmnt -T; /tmp is often tmpfs): TMPDIR="$PWD" taskset -c 2 python3 -I io.py with CPython 3.14.4. Record all raw times, filesystem/mount, CPU, kernel and Python versions, block size, order, prewarm and scope. Pread/buffered return 16 MiB per pass, while mmap explicitly samples only 4096 bytes and incurs page-level access. Do not call their timing ratio a device-bandwidth speedup or require a winning order.Traps
- Labeling the
mmapsampled-byte loop a full 16 MiB copy, or dividing every variant by file size and calling the result physical-device bandwidth. - Comparing one cold first variant with warm later variants, or keeping a mapping warm for one case while charging setup to another.
- Applying an HDD scheduling model or optional RAID capacity equation as a measured property of your SSD.
Practice
OSTEP `disk.py`: HDD positioning and scheduling
README Overview; -s 1 and -s 2 with -A 5,-1,0 -p FIFO, then -p SATF
Use the README's starting head position and default seek/rotation geometry. Predict request order and seek/rotation/transfer totals before -c. Keep units as simulator time units, not host milliseconds. The warm-cache experiment supplies the section mini-project's observation rather than validating this HDD model on an SSD.
Self-test
-
Why does stride 17 visit all 4096 block indices?
17 and 4096 are coprime. Multiplication by 17 modulo 4096 is a permutation, so the pass covers each block exactly once. -
What is the sampled checksum for the file?
There are 16 repeats of bytes 0 through 255: \(16 \times (255 \times 256/2) = 522240\). The file length is \(4096 \times 4096 = 16777216\) bytes = 16 MiB. -
Does a faster warm-cache random pass show that random SSD reads beat sequential reads?
No. It measures this application's warm-cache path, including syscall/copy or mapping costs. No device read or throughput claim follows without device-level evidence and cache controls. -
For four equal \(D\)-byte disks, what are ideal usable RAID 0, 5 and 6 capacities?
\(4D\), \(3D\) and \(2D\) respectively, ignoring metadata. They tolerate zero, one and two disk failures in the ideal level model; none protects against all corruption or deletion.
Completion criterion
Stop when
All five-repeat checksums agree, each timing states cache condition and work scope, and both two-seed disk predictions separate positioning from transfer without a host-device speed claim.
Mark passed, then open 1.9 Only mark this when you can do it without notes.Leads to
- 1.9 Namespaces, cgroups and container boundaries Locate the mount and resource boundary around the same I/O path.
Comes after
- 1.5 Virtual memory, page tables, TLBs, page faults and mmapCompare mapping and buffered reads under matched cache conditions.
- 1.7 Files, page cache, fsync, atomic rename and durabilityMeasure reads without confusing page-cache hits with device service.
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.
- 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.
- 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.
Also in this section
- 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.
- 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.
- 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.
- 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.