I/O and Storage Management

01 Lab overview

This lab contributes to U11.1 through U11.7, and to course learning outcomes CLO5, CLO6, and CLO8.

02 Learning objectives

03 Background

3.1 I/O hardware

A computer's I/O system consists of a bus (PCI Express, USB, SATA) that connects the CPU and memory to device controllers, which in turn control devices (disks, network cards, keyboards). Each controller exposes one or more ports — registers that the CPU can read and write to issue commands, read status, and transfer small amounts of data. Device registers are either memory-mapped (they appear at fixed physical addresses) or accessed through a separate I/O address space (as on x86 with the in and out instructions).

3.2 Interrupts and polling

Polling: the CPU repeatedly reads the device's status register until the device is ready. Simple, but wastes CPU cycles when the device is slow. Interrupts: the device raises an interrupt when it needs attention; the CPU suspends its current work, saves state, and runs the device's interrupt handler. Interrupts free the CPU to do other work while the device is busy, at the cost of the interrupt-handling overhead (saving and restoring registers, cache effects). Modern systems use interrupt coalescing to reduce the interrupt rate: the controller delays raising an interrupt until several events have accumulated or a timer expires.

3.3 DMA

Direct memory access allows a device to transfer data to or from main memory without CPU involvement per byte. The CPU programs the DMA controller with the source, destination, and length, and the DMA controller performs the transfer in the background. When the transfer is complete, the DMA controller raises an interrupt. DMA is essential for high-bandwidth devices (disk, network, GPU): without it, the CPU would have to execute a load-store loop for every byte, which is impossible at modern data rates.

3.4 Device drivers

A device driver is the kernel module that knows how to talk to a particular device. It translates the generic operations of the kernel's I/O subsystem (read, write, ioctl) into the device-specific commands the controller understands. In Linux, character devices and block devices expose a file_operations structure to the kernel, and are identified by a major number (the driver) and a minor number (the specific device the driver manages).

3.5 Disk scheduling

A hard disk's cost is dominated by seek time (moving the head to the right track) and rotational latency (waiting for the right sector to come under the head). Disk scheduling algorithms try to minimise the total head movement for a batch of requests:

• FCFS: serve in arrival order. Fair but can involve large back-and-forth seeks.
• SSTF: serve the request closest to the current head position. Minimises head movement in the short term but can starve far requests.
• SCAN (elevator): move the head in one direction, serving requests as they are encountered, then reverse. Bounded wait time; no starvation.
• C-SCAN: move in one direction only, serving requests; on reaching the end, return to the start without serving. More uniform wait times.
• LOOK / C-LOOK: like SCAN / C-SCAN, but reverse at the last request rather than at the last cylinder.

3.6 RAID

RAID (Redundant Array of Independent Disks) combines multiple disks to improve performance, reliability, or both.

• RAID 0 (striping): data is split across disks. Capacity = N × disk; no redundancy.
• RAID 1 (mirroring): each disk is duplicated. Capacity = N/2 × disk; tolerates N/2 failures.
• RAID 5 (striping with distributed parity): one disk's worth of parity is distributed across all disks. Capacity = (N − 1) × disk; tolerates one failure.
• RAID 6 (dual parity): two independent parity blocks are distributed. Capacity = (N − 2) × disk; tolerates two failures.

3.7 Solid-state drives

An SSD stores data in NAND flash cells. Unlike a hard disk, it has no moving parts, so seek time is essentially zero. But flash has important quirks: it is written in pages (typically 4 KB) and erased in blocks (typically 256 KB to 1 MB); a page cannot be overwritten without erasing the whole block first. The flash translation layer (FTL) hides this: it maps logical block addresses to physical pages and, when a page is rewritten, writes the new data to a fresh page and updates the mapping — the old page becomes garbage. Garbage collection reclaims the garbage blocks, and wear levelling distributes writes across all blocks so that no block wears out first.

04 Guided activities

Activity 4.1 — Inspecting the I/O subsystem

1. Create the lab directory:

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

2. List the block devices with lsblk and the character devices with ls -l /dev. Identify the major and minor numbers of your disk, your terminal, and /dev/null.
3. Inspect /proc/interrupts before and after running a disk-intensive command such as find / -type f -exec cat {} \; > /dev/null. Record the increase in interrupt count for the storage controller and the network interface. Explain why interrupt counts differ across CPUs.
4. Inspect /proc/diskstats before and after running fio (or dd) with different block sizes. Compute the read and write throughput for each block size and the average request size. Explain why larger requests achieve higher throughput.
5. Use iostat -x 1 during a disk workload to observe the utilisation, the average request queue length, and the average service time. Explain each metric and what it says about the device's behaviour.

Activity 4.2 — Writing a character device driver

1. Write a minimal character device driver hello_dev.c. The module registers a character device with a major number allocated dynamically, and implements the read, write, and open operations of a struct file_operations. On read, it returns a fixed message; on write, it prints what was written to the kernel log.
2. Write a Makefile that builds the module against the running kernel's headers:

   obj-m := hello_dev.o
   KDIR  := /lib/modules/$(shell uname -r)/build
   all:
   	$(MAKE) -C $(KDIR) M=$(PWD) modules
   clean:
   	$(MAKE) -C $(KDIR) M=$(PWD) clean

3. Load the module with sudo insmod hello_dev.ko. Read the kernel log with dmesg | tail to find the major number the kernel assigned. Create the device node with sudo mknod /dev/hello c <major> 0 and set its permissions.
4. Read from /dev/hello with cat. Write to it with echo "test" > /dev/hello. Verify the messages in dmesg.
5. Unload the module with sudo rmmod hello_dev and remove the device node. Explain the role of the major and minor numbers: the major number selects the driver, the minor number selects the specific device the driver is managing.

Activity 4.3 — Disk-scheduling simulator

1. Write disk_sched.c that reads a list of cylinder requests from the command line (or standard input), a starting cylinder, and a direction. It computes the total head movement and the order in which requests are served for each algorithm: FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK.
2. Test with the queue: 98, 183, 37, 122, 14, 124, 65, 67, starting at cylinder 53 with the head moving towards higher numbers. The disk has 200 cylinders.
3. For each algorithm, report the service order and the total head movement. Verify the expected values:
   • FCFS: 640 cylinders moved.
   • SSTF: 236 cylinders moved.
   • SCAN: 208 cylinders moved.
   • C-SCAN: 382 cylinders moved.
   • LOOK: 299 cylinders moved (varies with the exact queue).
4. Run the simulator on a workload with a strong locality pattern (requests clustered around a few cylinders) and one with a uniform distribution. For each, report which algorithm gives the smallest head movement and which gives the most uniform wait time.

Activity 4.4 — RAID simulator

1. Write raid.c that simulates RAID 0, 1, 5, and 6 with N disks of B blocks each. The simulator exposes a logical address space; the caller issues read and write operations of a given size and offset, and the simulator reports how many physical disk operations each logical operation requires.
2. Compare the four levels for:
   • A large sequential write (many blocks).
   • A single small random write (one block).
   • A large sequential read.
   • A single small random read.
   • The effective capacity for 4 disks of 1 TB each.
   • The number of disk failures each level can tolerate.
3. Implement a failure mode: for each RAID level, fail one disk and report whether the data is still readable, and how many reads are needed to reconstruct a lost block. For RAID 6, fail two disks and repeat.
4. Compute the write amplification for RAID 5 and RAID 6 small random writes: a single logical block write requires reading the old data and parity, computing the new parity, and writing the new data and parity — four physical I/Os for RAID 5. Explain why this is called the small-write penalty.

Activity 4.5 — SSD behaviour

1. Use fio to measure the sequential and random read and write throughput of your VM's disk. Use a 4 KB random-read workload, a 4 KB random-write workload, a 1 MB sequential-read workload, and a 1 MB sequential-write workload.
2. Compare the random-write throughput to the sequential-write throughput. On an SSD, random writes are much slower than sequential because the FTL must perform garbage collection; on a hard disk, random writes are much slower because of seek time. Explain which effect dominates on your system.
3. Measure the effect of write size on throughput: 4 KB, 16 KB, 64 KB, and 1 MB. Plot throughput against write size. Explain the curve in terms of the FTL's page granularity, the erase-block granularity, and the write buffer.
4. Run a long write workload (several GB) and observe whether throughput degrades over time. This is the write cliff: once the drive's spare area is exhausted, every write triggers garbage collection. If your system has TRIM enabled (lsblk -D shows DISC-GRAN and DISC-MAX), issue sudo fstrim / and measure whether performance recovers.

05 Exercises

06 Deliverables

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

• hello_dev.c and its Makefile — Activity 4.2.
• disk_sched.c — Activity 4.3.
• raid.c — Activity 4.4.
• fio/ — the fio workload files and results for Activity 4.5.
• interrupts_before.txt and interrupts_after.txt — Activity 4.1.
• outputs.txt — the output logs of all programs with the commands that produced them.
• report.md (or report.pdf) — the lab report described below.

Lab report

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

1. I/O subsystem inspection. The lsblk, /proc/interrupts, and /proc/diskstats data, with an explanation of each field and a discussion of what the interrupt counts reveal about the device's activity.
2. Character device driver. The module source, the Makefile, the dmesg output on load and unload, and an explanation of the major/minor device numbering scheme.
3. Disk-scheduling comparison. A table with one row per algorithm and columns for total head movement, maximum wait, and average wait, for both the clustered and the uniform workloads.
4. RAID analysis. The comparison table from Activity 4.4, the failure-mode analysis, and the write-amplification calculation.
5. SSD behaviour. The fio results plotted against block size, with an explanation of the write cliff, the read-modify-write penalty, and the effect of TRIM.
6. Reflection. A discussion of how the kernel's block layer, I/O scheduler, device driver, and storage device divide the responsibilities of performance, reliability, and fairness — and how that division changes when the storage is an SSD rather than a hard disk.

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

09 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 12.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 36–38.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 5.
• Corbet, J., Rubini, A., & Kroah-Hartman, G. Linux Device Drivers, 3rd ed. O'Reilly, 2005.
• Patterson, D. A., Gibson, G., & Katz, R. H. A Case for Redundant Arrays of Inexpensive Disks (RAID). ACM SIGMOD, 1988.
• Agrawal, N., Prabhakaran, V., Wobber, T., Davis, J. D., Manasse, M., & Panigrahy, R. Design Tradeoffs for SSD Performance. USENIX ATC, 2008.
• Linux man-pages: man 4 sd, man 4 hd, man 8 lsblk, man 8 mdadm, man 1 fio.
• Linux kernel documentation: Documentation/block/, Documentation/driver-api/.