Disk Access Time

$\text{Access Time} = \underbrace{\text{Seek Time} + \text{Rotational Latency}}_\text{OS can optimize this} + \text{Transfer Time}$ An average seek needs a half rotation. Example Suppose a disk has 7200 RPM, an average seek time of 8ms, and a transfer rate of 100 MB/s. State the average time to read 4KB at random. 7200 rotations in 60 seconds $\rightarrow$ 1 rotation in $\frac{60}{7200}\times 1000\text{ms}=8.3\text{ms}$ $\Rightarrow$ average seek $4.15\text{ms}$ Transfer time for $4\text{KB}$ is $\frac{4\text{KB}}{100 \frac{\text{MB}}{\text{s}}} = 0.

Disk Scheduling

First in, First out. There will be long seeks! Shortest Seek Time First. Might lead to starvation (=single, long seeks) SCAN("elevator") [=cocktailshaker] Anticipatory Scheduling [=wait a bit, apps are likely to schedule many reads one after another]


Single Extents Allocate files as sequence of contigious disk blocks -> single extent Keep a free list of unused extents on disk Pro Con Easy sequential and random access, few seeks Horrible disk fragmentation, large files difficult to alloc Simple Design Difficult to predict file needs at creation time Multiple Extents Table of base/size pairs (pointers) Pro Con Easy to find free extents Fuller disk -> lot of small extents -> many seeks External Fragmentation


Named collection of bytes stored on disk OS View: Ordered set of blocks stored on block device File System: Packs bytes in disk blocks, unpacks on reading

Flash Translation Layer

In-memory remap table of logical pages to physical flash pages. On write to physical page: write to new physical page, update logical -> physical mapping Problem Get FTL on boot. Solution Store logical page number in metadata of physical page.

Hard Disk Drives - Overheads

Moving between tracks Find sector in track Transfer time 5-50ms 0-5ms some microseconds

Hard Disk Drives Basics

Imagine a layer of CDs referred to as 'platters'. They are read by arms. A platter contains thousands of tracks, which are collections of sectors. A sector is a basic read-write unit, typically 512-4096 bytes big. A sector typically looks like [ID | Data | ECC], so some data to identify it, the actual data, and some error-correcting code that can be used in case of minor physical failures.

Non-Volatile Random Access Memory - Basics

Speed: DRAM > NVRAM > SSD Capacity: DRAM < NVRAM < SSD

Solid State Drive - Basics

NAND-Flash based No moving parts -> silent Contains 'erasure blocks' sized 128 - 512 KB. Comprises 4KB pages, 128 Byte of Metadata, such as error correcting code (ECC). Always accesses data+metadata. Read Erasure Fast Slow $10\mu\text{s}$ some $\text{ms}$ Writing to new page: hundreds of $\mu\text{s}$ Erasures and writes cause wear! Device will die over time!

Types of persistent storage

Hard Disk Drives (HDDs) Solid State Drives (SSDs) Non-Volatile Random Access Memory (NVRAM)

Wear Leveling

Shift blocks around, make sure to use all blocks equally often. Since firmware may remap to spare pages and erasure blocks, slowdown due to retries