These are the notes for CS Fundamentals for Placements, episode 37. In episode 36 we decided which disk blocks hold a file. Today we go down to the hardware itself: a hard disk drive that spins, with an arm that moves. We learn its parts (platter, surface, track, sector, cylinder, read/write head), the two classic numericals (disk capacity and disk access time = seek time + rotational latency + transfer time), the six disk scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK) with numericals, the RAID levels (0, 1, 5, 6, 10) with parity, and how an SSD works inside (pages, blocks, the FTL, wear leveling, TRIM). Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 6 November 2026. The disk numbers in the programs (8 surfaces, 100,000 tracks, 9 ms seek, 7200 RPM, an erase limit of 3000) are textbook example values, not a specific product.
Quick recap
- A block is a fixed-size piece of storage (e.g. 4 KB) that the file system hands out to files.
- The file system (episode 36) records which blocks a file owns (FAT, inode) and which are free (bitmap).
- Today's question: what physically happens when the OS asks the disk for block 500, and how long does it take?
1. What is inside a hard disk
The story: an old record player
A record player has a flat disc that spins and a needle on an arm that moves in and out. A hard disk drive (HDD) works the same way.
| Record player | Hard disk | Meaning |
|---|---|---|
| The spinning record | Platter | A rigid disc coated with magnetic material. A disk has one or more, stacked on one spindle. |
| One side of the record | Surface | Each platter has 2 surfaces, both store data. |
| The needle | Read/write head | Reads and writes the magnetic bits. One head per surface. |
| The tone arm | Actuator arm | Holds all the heads. They move together. |
| The rings of the groove | Track | One ring on a surface. |
| A slice of a ring | Sector | A piece of a track; the smallest unit the disk reads or writes (classically 512 bytes). |
The cylinder
Because all heads move together, when the arm is at track 50, every head is over track 50 of its own surface. The set of tracks with the same number on all surfaces is a cylinder. Like the same floor number in every tower of a housing society. Reading a whole cylinder needs no arm movement, so file systems try to keep a file's blocks close together (in the same or nearby cylinders). In disk scheduling questions, the "position" of a request is its cylinder number.
Capacity formula
capacity = surfaces × tracks per surface × sectors per track × bytes per sector
number of cylinders = tracks per surface
2. Why one read takes milliseconds: disk access time
Reading one sector takes three steps:
- Seek time: moving the arm to the right track (cylinder). Usually the slowest part. Exams give the average seek time.
- Rotational latency: waiting for the sector to spin round under the head. On average you wait half a rotation. One rotation takes
60 / RPMseconds (RPM = rotations per minute). - Transfer time: the sector passes under the head and the data flows. = (bytes to read) / (transfer rate), or (one rotation) / (sectors per track) for one sector.
access time = seek time + rotational latency + transfer time (+ controller overhead, if given)
Live: capacity and access time
#include <stdio.h>
// A hard disk: 4 platters, 2 surfaces each, 1 head per surface
int main(void) {
long surfaces = 8, tracks = 100000, sectors = 1000, bytes = 512;
long cap = surfaces * tracks * sectors * bytes;
printf("capacity = %ld bytes = %.1f GB\n", cap, cap / 1e9);
printf("cylinders = %ld (one track on every surface)\n", tracks);
double rpm = 7200, rot = 60000.0 / rpm; // ms per rotation
double seek = 9.0, lat = rot / 2; // average seek, latency
double xfer = rot / sectors; // one sector passes the head
printf("one rotation = %.2f ms\n", rot);
printf("avg rotational lat = %.2f ms\n", lat);
printf("transfer 1 sector = %.4f ms\n", xfer);
printf("access time = %.2f ms\n", seek + lat + xfer);
}
Output:
capacity = 409600000000 bytes = 409.6 GB
cylinders = 100000 (one track on every surface)
one rotation = 8.33 ms
avg rotational lat = 4.17 ms
transfer 1 sector = 0.0083 ms
access time = 13.18 ms
Almost all of the 13 ms is seek + rotation; the data itself takes under 0.01 ms. So the thing to save is arm movement, which is what disk scheduling does.
Worked numerical
A disk spins at 6000 RPM, average seek 5 ms, 500 sectors per track of 512 bytes. Time to read one sector?
- One rotation = 60 / 6000 s = 10 ms; average latency = 5 ms.
- Transfer of one sector = 10 ms / 500 = 0.02 ms.
- Access time = 5 + 5 + 0.02 = 10.02 ms.
Reading a whole track after the seek (if the disk can start anywhere) = seek + one full rotation = 5 + 10 = 15 ms.
3. Disk scheduling
The story: a delivery rider on one long road
A rider has 8 parcels for houses 98, 183, 37, 122, 14, 124, 65, 67 on a road of houses 0-199, and he's at house 53. Delivering in booking order makes him zig-zag and burn petrol. For the disk: the road = the cylinders, the rider = the arm, petrol = seek time.
Disk scheduling is choosing the order in which the disk serves its waiting requests (the disk queue). The usual score is the total head movement: how many cylinders the arm travels in total. Less movement = less seek time = more requests per second (throughput). We also care about fairness: no request should wait forever.
All examples below use the classic queue: 98, 183, 37, 122, 14, 124, 65, 67, head at 53, cylinders 0-199.
FCFS (first come, first served)
Serve requests in arrival order. Fair (no starvation), simple, but ignores where the head is.
#include <stdio.h>
#include <stdlib.h>
// Disk queue (cylinders 0-199), head starts at 53
int q[] = {98, 183, 37, 122, 14, 124, 65, 67}, n = 8;
int main(void) {
int head = 53, total = 0;
printf("FCFS:");
for (int i = 0; i < n; i++) { // serve in arrival order
total += abs(q[i] - head); head = q[i];
printf(" %d", head);
}
printf("\ntotal head movement: %d cylinders\n", total);
}
Output:
FCFS: 98 183 37 122 14 124 65 67
total head movement: 640 cylinders
By hand: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640.
SSTF (shortest seek time first)
Always serve the waiting request nearest to the head. A greedy method (it makes the best-looking choice at each step).
#include <stdio.h>
#include <stdlib.h>
int q[] = {98, 183, 37, 122, 14, 124, 65, 67}, n = 8, done[8];
int main(void) {
int head = 53, total = 0;
printf("SSTF:");
for (int k = 0; k < n; k++) { // pick the NEAREST request
int b = -1;
for (int i = 0; i < n; i++)
if (!done[i] && (b < 0 || abs(q[i] - head) < abs(q[b] - head))) b = i;
done[b] = 1; total += abs(q[b] - head); head = q[b];
printf(" %d", head);
}
printf("\ntotal head movement: %d cylinders\n", total);
}
Output:
SSTF: 65 67 37 14 98 122 124 183
total head movement: 236 cylinders
By hand: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236.
Problem: starvation. If new requests keep arriving near the head, a far request (like 183) can wait forever. Starvation means a request waits indefinitely because others are always preferred (we met it in CPU scheduling, episode 22). SSTF is also not optimal: being greedy, it can miss a shorter overall route.
SCAN (the elevator algorithm)
The story: a lift
A lift goes up stopping at every requested floor, reaches the top, then comes down doing the same. SCAN moves the arm in one direction to the end of the disk, serving requests on the way, then reverses. Nobody waits more than about one round trip, so no starvation.
C-SCAN (circular SCAN)
Right after SCAN reverses, the cylinders it just passed are served again soon, while the far end waits longest. C-SCAN serves only in one direction: go up to the end, jump back to cylinder 0 (serving nothing on the way back), and sweep up again. Waiting times are more uniform.
LOOK and C-LOOK
A smart lift turns at the last requested floor, not at the roof. LOOK is SCAN that reverses at the last request in the current direction. C-LOOK is C-SCAN that goes only as far as the last request and jumps back to the lowest pending request (not to 0).
Live: all four sweeps (head at 53, moving up)
#include <stdio.h>
#include <stdlib.h>
// Sorted queue, head at 53 moving UP. Disk: cylinders 0-199
int s[] = {14, 37, 65, 67, 98, 122, 124, 183}, n = 8;
int go(int *h, int to) { int d = abs(to - *h); *h = to; return d; }
int sweep(int toEnd, int circular) {
int h = 53, t = 0, i = 0;
while (s[i] < 53) i++; // first request above the head
for (int j = i; j < n; j++) t += go(&h, s[j]); // serve on the way up
if (toEnd) t += go(&h, 199); // SCAN family: touch the end
if (circular) {
if (toEnd) t += go(&h, 0); // C-SCAN: jump back to 0
for (int j = 0; j < i; j++) t += go(&h, s[j]); // and go up again
} else for (int j = i - 1; j >= 0; j--) t += go(&h, s[j]); // turn around
return t;
}
int main(void) { printf("SCAN %d | C-SCAN %d | LOOK %d | C-LOOK %d\n",
sweep(1, 0), sweep(1, 1), sweep(0, 0), sweep(0, 1)); }
Output:
SCAN 331 | C-SCAN 382 | LOOK 299 | C-LOOK 322
The exam method, by hand
Sort the queue and mark the head: 14 37 | 53 | 65 67 98 122 124 183, moving up, disk 0-199.
| Algorithm | Path | Total |
|---|---|---|
| FCFS | 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67 | 640 |
| SSTF | 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183 | 236 |
| SCAN (up) | 53 → ... → 183 → 199 → 37 → 14 | (199 − 53) + (199 − 14) = 146 + 185 = 331 |
| C-SCAN (up) | 53 → ... → 183 → 199 → jump to 0 → 14 → 37 | 146 + 199 + 37 = 382 |
| LOOK (up) | 53 → ... → 183 → 37 → 14 | (183 − 53) + (183 − 14) = 130 + 169 = 299 |
| C-LOOK (up) | 53 → ... → 183 → jump to 14 → 37 | 130 + 169 + 23 = 322 |
Rules that save marks:
- Sort first, mark the head, note the direction. SCAN and LOOK depend on it; going down first gives different totals (SCAN down = 53 + 183 = 236 here).
- SCAN / C-SCAN touch the end cylinder (0 or the last one); LOOK / C-LOOK don't.
- Read whether the return jump of C-SCAN / C-LOOK is counted. Most textbooks and GATE keys count it (as above); some questions say "ignore the return". State your assumption.
Comparison
| Algorithm | Head movement | Starvation? | Waiting-time fairness | Notes |
|---|---|---|---|---|
| FCFS | high | no | fair but slow | zig-zags |
| SSTF | low | yes | poor | greedy, not optimal |
| SCAN | medium | no | middle cylinders favoured | elevator |
| C-SCAN | medium-high | no | most uniform | jump back to 0 |
| LOOK | lower than SCAN | no | like SCAN | turns at last request |
| C-LOOK | lower than C-SCAN | no | uniform | jump to lowest request |
For a hard disk under load, SCAN/LOOK-style ordering is a good balance of speed and fairness.
4. RAID: surviving a dead disk
The story: the one-notebook problem
Keep all your notes in one notebook, it gets soaked in the rain, and everything is gone: a single point of failure. Disks are machines, and machines die.
In 1988, David Patterson, Garth Gibson and Randy Katz of U.C. Berkeley presented "A Case for Redundant Arrays of Inexpensive Disks (RAID)" at the ACM SIGMOD conference (source: Computer History Museum, "1988: U.C. Berkeley paper catalyses interest in RAID"). RAID originally stood for Redundant Arrays of Inexpensive Disks; it is now usually read as Redundant Array of Independent Disks: many disks working as one, for speed, safety or both.
Three building blocks:
- Striping: split data into chunks (stripe units) and put consecutive chunks on different disks, so several disks work at once. Faster.
- Mirroring: write every block to two disks. Safe, costs double.
- Parity: store an extra block computed from the data blocks (with XOR) so any one lost block can be rebuilt.
XOR (exclusive OR, from episode 3) gives 1 when two bits differ: 0^0=0, 0^1=1, 1^0=1, 1^1=0. Key facts: x ^ x = 0 and x ^ 0 = x. So if P = D0 ^ D1 ^ D2, then D1 = D0 ^ D2 ^ P.
Live: rebuild a dead disk with XOR, and usable space
#include <stdio.h>
// RAID 5 parity: P = D0 ^ D1 ^ D2. Lose any one block, XOR the rest back
int main(void) {
unsigned char d[3] = {0x5A, 0x3C, 0xF0}; // data on disks 0, 1, 2
unsigned char p = d[0] ^ d[1] ^ d[2]; // parity on disk 3
printf("D0=%02X D1=%02X D2=%02X parity=%02X\n", d[0], d[1], d[2], p);
unsigned char lost = d[1]; d[1] = 0; // disk 1 dies
unsigned char rebuilt = d[0] ^ d[2] ^ p; // XOR the survivors
printf("disk 1 died. rebuilt D1=%02X (was %02X): %s\n",
rebuilt, lost, rebuilt == lost ? "recovered" : "LOST");
int disks = 4; double size = 4.0; // four 4 TB disks
printf("usable with %d x %.0f TB disks:\n", disks, size);
printf(" RAID 0 : %4.0f TB (no disk may fail)\n", disks * size);
printf(" RAID 5 : %4.0f TB (any 1 disk may fail)\n", (disks - 1) * size);
printf(" RAID 6 : %4.0f TB (any 2 disks may fail)\n", (disks - 2) * size);
printf(" RAID 10: %4.0f TB (1 per mirror pair)\n", disks * size / 2);
printf(" RAID 1 with just 2 disks: %.0f TB (a full copy)\n", size);
}
Output:
D0=5A D1=3C D2=F0 parity=96
disk 1 died. rebuilt D1=3C (was 3C): recovered
usable with 4 x 4 TB disks:
RAID 0 : 16 TB (no disk may fail)
RAID 5 : 12 TB (any 1 disk may fail)
RAID 6 : 8 TB (any 2 disks may fail)
RAID 10: 8 TB (1 per mirror pair)
RAID 1 with just 2 disks: 4 TB (a full copy)
Check by hand: 5A = 0101 1010, 3C = 0011 1100, F0 = 1111 0000. 5A ^ 3C = 0110 0110 (66); 66 ^ F0 = 1001 0110 = 96. Rebuild: 5A ^ F0 = 1010 1010 (AA); AA ^ 96 = 0011 1100 = 3C.
The RAID levels
| Level | Idea | Usable space (n disks of size s) | Survives | Good for |
|---|---|---|---|---|
| RAID 0 | striping, no redundancy | n·s | 0 failures (one failure loses everything) | speed, scratch data |
| RAID 1 | mirroring | s (with 2 disks); 1/2 of raw | 1 failure (per mirror) | small, safe, fast reads |
| RAID 5 | striping + 1 parity block per stripe, parity rotated across all disks | (n − 1)·s | any 1 | read-heavy storage |
| RAID 6 | striping + 2 independent parity blocks | (n − 2)·s | any 2 | big arrays, long rebuilds |
| RAID 10 (1+0) | mirror pairs, then stripe across the pairs | n·s / 2 | 1 per pair (more if in different pairs) | databases: fast and safe |
- RAID 5 rotates the parity block across disks so no single disk does all parity writes (that was the bottleneck of RAID 4, which uses one dedicated parity disk).
- A small write in RAID 5 costs extra I/O: read old data + old parity, write new data + new parity (the write penalty).
- RAID is not a backup. It protects against a dead disk, not against deleting a file, malware, or a fire: a deletion is mirrored instantly.
5. SSDs: no moving parts
The story: a whiteboard you can only wipe in big panels
An SSD (solid-state drive) stores bits in flash memory chips. No platters, no arm: no seek time and no rotational latency, so random reads are fast. But flash has unusual rules:
| Whiteboard | Flash | Meaning |
|---|---|---|
| Write on any empty line | Write a page | A page (e.g. 4 KB) is the unit of reading and writing. It can be written only if it is empty (erased). |
| Wipe only a whole panel | Erase a block | A block (many pages, e.g. 128-256 pages) is the unit of erasing. To reuse one page, the whole block must be erased, after copying out pages still in use. |
| Each panel wears thin | Limited P/E cycles | Each block survives a limited number of program/erase (P/E) cycles, then wears out. |
So an SSD never overwrites in place: an update is written to a fresh empty page, and the old page is marked invalid.
Live: wear leveling
#include <stdio.h>
// Flash: a block wears out after a limited number of erases (say 3000)
#define BLOCKS 8
int main(void) {
int naive[BLOCKS] = {0}, level[BLOCKS] = {0}, writes = 6000;
for (int w = 0; w < writes; w++) naive[0]++; // same block every time
for (int w = 0; w < writes; w++) { // wear leveling:
int least = 0; // pick the least-worn block
for (int b = 1; b < BLOCKS; b++) if (level[b] < level[least]) least = b;
level[least]++;
}
printf("no wear leveling : block 0 erased %d times -> %s\n",
naive[0], naive[0] > 3000 ? "WORN OUT" : "ok");
printf("wear leveling :");
for (int b = 0; b < BLOCKS; b++) printf(" %d", level[b]);
printf(" -> all ok\n");
}
Output:
no wear leveling : block 0 erased 6000 times -> WORN OUT
wear leveling : 750 750 750 750 750 750 750 750 -> all ok
Wear leveling spreads writes and erases evenly over all blocks so no block wears out early.
Inside the SSD controller
- FTL (flash translation layer): firmware in the SSD that maps the OS's logical block numbers to physical flash pages. The OS still asks for "block 500"; the FTL knows where that data really is right now.
- Garbage collection: in the background, copy the still-valid pages out of a block full of invalid pages, then erase the block.
- Write amplification: because of this copying, the flash may physically write more data than the OS asked for.
- Over-provisioning: spare flash the user can't see, giving garbage collection room to work.
- TRIM: when a file is deleted, only the file system knows its blocks are free. TRIM is the command by which the OS tells the SSD which blocks are no longer in use, so garbage collection can skip them. On Linux,
fstrim"is used on a mounted filesystem to discard (or 'trim') blocks which are not in use by the filesystem", useful for SSDs (source: fstrim(8) manual page).
Does disk scheduling matter on an SSD?
Much less: there is no arm, so ordering by cylinder saves nothing. Linux's multiqueue block layer offers the schedulers bfq, kyber, none and mq-deadline; the Ubuntu kernel documentation calls none "ideal for fast random I/O devices such as NVME" and says to "avoid using the none/noop I/O schedulers for a HDD" (source: Ubuntu wiki, Kernel/Reference/IOSchedulers). NVMe is the fast interface used by modern SSDs that plug into the PCIe bus.
| HDD | SSD | |
|---|---|---|
| Moving parts | yes (spindle, arm) | none |
| Random access | slow (seek + rotation, milliseconds) | fast (no seek) |
| Overwrite in place | yes | no (erase a block first) |
| Wears out by writes | not mainly | yes (P/E cycles) → wear leveling |
| Scheduling | SCAN/LOOK-style helps | little benefit ("none") |
The whole chain
| Problem | Invention |
|---|---|
| Where is the data physically? | platter, surface, track, sector, cylinder, head |
| How long does a read take? | seek + rotational latency + transfer |
| Many requests in arrival order zig-zag | FCFS → SSTF |
| SSTF can starve far requests | SCAN (elevator), C-SCAN |
| SCAN goes to the end for nothing | LOOK, C-LOOK |
| One disk dies, everything is lost | RAID: striping, mirroring, parity |
| Flash blocks wear out | wear leveling, FTL, TRIM |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Average latency = one full rotation | answer twice too big | on average the sector is half a turn away | latency = 0.5 × 60 / RPM |
| Forgetting to convert RPM | latency in minutes | RPM is per minute | 60 / RPM seconds per rotation |
| SCAN stops at the last request | total too small | that's LOOK | SCAN goes to cylinder 0 or the last cylinder |
| C-LOOK jumps to cylinder 0 | total too big | that's C-SCAN | C-LOOK jumps to the lowest pending request |
| Ignoring the direction | wrong order, wrong total | SCAN/LOOK depend on it | note the direction first |
| Not stating if the return jump counts | marks lost on C-SCAN | conventions differ | count it unless told otherwise, and say so |
| "RAID 1 means no backups needed" | a deleted file is gone for good | mirrors copy mistakes | RAID for uptime, backups for mistakes |
| "RAID 0 is safer" | data loss | one failure breaks every file | RAID 0 is only for speed |
printf("%d %d", f(), g()) with side effects |
values in an unexpected order | C doesn't fix the order arguments are evaluated | compute into variables first |
Mini project: a disk scheduling simulator
Write one C program that:
- reads the number of cylinders, the head position, the direction and the queue from input;
- prints the service order and total head movement for FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK (with a flag for whether the return jump counts);
- prints the average seek distance per request and, for a given seek time per cylinder (say 0.1 ms), the total seek time;
- bonus: simulate starvation: keep adding requests near the head every step and show how long the request at the far end waits under SSTF versus LOOK.
Practice
1. Queue 82, 170, 43, 140, 24, 16, 190; head at 50; cylinders 0-199. Total head movement for SSTF and C-LOOK (moving up).
Solution
SSTF: 50 → 43 (7) → 24 (19) → 16 (8) → 82 (66) → 140 (58) → 170 (30) → 190 (20) = 208.
C-LOOK (up): 50 → 82 → 140 → 170 → 190 = 140; jump to 16 = 174; 16 → 24 → 43 = 27. Total 341 (counting the jump).
For practice: FCFS = 642, SCAN up = (199 − 50) + (199 − 16) = 332, LOOK up = (190 − 50) + (190 − 16) = 314, C-SCAN up = 149 + 199 + 43 = 391.
2. Capacity: 16 surfaces, 512 tracks per surface, 64 sectors per track, 1 KB per sector.
Solution
16 × 512 × 64 × 1 KB = 524,288 KB = 512 MB (2⁴ × 2⁹ × 2⁶ × 2¹⁰ = 2²⁹ bytes). Cylinders = 512.
3. Average access time: 12,000 RPM, average seek 3 ms, transfer time negligible.
Solution
One rotation = 60 / 12,000 s = 5 ms. Average latency = 2.5 ms. Access time = 3 + 2.5 = 5.5 ms.
4. Usable space of six 2 TB disks in RAID 5 and in RAID 6.
Solution
RAID 5: (6 − 1) × 2 = 10 TB, survives 1 failure. RAID 6: (6 − 2) × 2 = 8 TB, survives any 2 failures.
5. Data blocks D0 = 1100, D1 = 1010, D2 = 0111. Compute the parity; then D2 is lost: rebuild it.
Solution
P = 1100 ^ 1010 ^ 0111 = 0110 ^ 0111 = 0001. Rebuild D2 = D0 ^ D1 ^ P = 1100 ^ 1010 ^ 0001 = 0110 ^ 0001 = 0111. ✓
6. Why does SSTF give the least head movement on the classic queue, yet SCAN is usually preferred on a busy hard disk?
Solution
SSTF greedily picks the nearest request, which keeps movement low, but under a steady stream of nearby requests a far request may starve. SCAN bounds every request's wait to about one sweep, giving predictable response times for only slightly more movement.
Quick quiz
rotation speed = 6000 RPM
average seek time = 5 ms
transfer time = negligible
// average access time?
A. 10 ms B. 15 ms C. 5 ms D. 7.5 ms
Answer
A. One rotation = 60 / 6000 s = 10 ms, so the average rotational latency = 5 ms. Access time = 5 + 5 = 10 ms.
Interview questions
- What are tracks, sectors and cylinders? A track is a ring on a surface, a sector a slice of a track (the smallest read/write unit), a cylinder the same track number on all surfaces.
- What makes up disk access time? Seek time + rotational latency + transfer time; seek and latency dominate.
- Why is average rotational latency half a rotation? The needed sector is equally likely to be anywhere on the track, so on average it is half a turn away.
- Compare FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK. See the comparison table: FCFS fair but slow; SSTF low movement but starvation; SCAN family sweeps with no starvation; C- versions give uniform waits; LOOK versions stop at the last request.
- Why can SSTF starve requests? It always serves the nearest; a stream of nearby requests keeps a far one waiting forever.
- What is the elevator algorithm? SCAN: sweep to the end serving requests, then reverse.
- What is RAID? Name the common levels. Redundant Array of Independent (originally Inexpensive) Disks; 0 striping, 1 mirroring, 5 striping + rotating parity, 6 double parity, 10 mirrored stripes.
- How does RAID 5 rebuild a failed disk? XOR of the remaining data blocks and parity in each stripe gives the missing block.
- Is RAID a backup? No. It survives disk failure, not deletion, corruption or disasters.
- Why can't an SSD overwrite a page in place? Flash must be erased before writing, and erasing works only on whole blocks.
- What are wear leveling, the FTL and TRIM? Spreading erases evenly; the firmware layer mapping logical blocks to physical pages; the OS telling the SSD which blocks are unused.
- Which Linux I/O scheduler suits an NVMe SSD? Often
none, since there's no seek to optimise (Ubuntu kernel docs).
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| HDD (hard disk drive) | Storage with spinning magnetic platters and a moving arm | a 7200 RPM laptop disk |
| Platter | A spinning disc coated with magnetic material | 4 platters |
| Surface | One side of a platter; both sides store data | 8 surfaces |
| Read/write head | Reads and writes bits on one surface | one per surface |
| Actuator arm | Holds all the heads; they move together | the "tone arm" |
| Track | One ring on a surface | track 50 |
| Sector | A slice of a track; smallest unit read or written | 512 bytes |
| Cylinder | The same track number on every surface | cylinder 50 |
| Capacity | surfaces × tracks × sectors × bytes per sector | 409.6 GB |
| RPM | Rotations per minute | 7200 RPM → 8.33 ms per turn |
| Seek time | Time to move the arm to the right track | 9 ms average |
| Rotational latency | Time for the sector to come under the head; average half a turn | 4.17 ms at 7200 RPM |
| Transfer time | Time for the data to pass under the head | 0.0083 ms per sector |
| Access time | seek + rotational latency + transfer | 13.18 ms |
| Disk queue | Requests waiting for the disk, as cylinder numbers | 98, 183, 37, ... |
| Disk scheduling | Choosing the order to serve the disk queue | SCAN |
| Total head movement | Total cylinders the arm travels | FCFS 640 |
| Throughput | Requests served per second | higher with less seeking |
| FCFS | Serve in arrival order | 640 |
| SSTF | Serve the nearest request next | 236 |
| Greedy algorithm | Takes the best-looking choice at each step | SSTF |
| Starvation | A request waits forever because others are always preferred | 183 under SSTF |
| SCAN (elevator) | Sweep to the end serving requests, then reverse | 331 |
| C-SCAN | Serve one way to the end, jump back to 0 | 382 |
| LOOK | SCAN that reverses at the last request | 299 |
| C-LOOK | C-SCAN that stops at the last request and jumps to the lowest | 322 |
| RAID | Redundant Array of Independent (Inexpensive) Disks | RAID 5 |
| Striping | Spreading consecutive chunks over several disks | RAID 0 |
| Mirroring | Writing every block to two disks | RAID 1 |
| Parity | An extra block, the XOR of the data blocks, to rebuild one loss | 96 |
| XOR | Bit is 1 when the inputs differ; x ^ x = 0 | 5A ^ 3C = 66 |
| RAID 0 / 1 / 5 / 6 / 10 | Striping / mirroring / single parity / double parity / striped mirrors | see table |
| Write penalty | Extra reads/writes to update parity on a small write | RAID 5 |
| Single point of failure | One part whose failure stops everything | one disk |
| Backup | A separate copy kept to recover from mistakes or disasters | nightly copy |
| SSD (solid-state drive) | Storage in flash chips, no moving parts | NVMe SSD |
| Flash memory | Chips that keep data without power; erase before write | NAND flash |
| Page (flash) | Unit of reading/writing in flash | 4 KB |
| Block (flash) | Unit of erasing; many pages | 128 pages |
| P/E cycle | One program (write) + erase of a block; limited | "say 3000" |
| Wear leveling | Spreading erases evenly over all blocks | 750 each |
| FTL (flash translation layer) | SSD firmware mapping logical blocks to flash pages | block 500 → page 9312 |
| Garbage collection (SSD) | Copy valid pages out, erase old blocks | background |
| Write amplification | Flash writes more than the OS asked for | GC copies |
| Over-provisioning | Hidden spare flash for GC | spare space |
| TRIM | OS tells the SSD which blocks are unused | fstrim |
| NVMe | Fast SSD interface on the PCIe bus | M.2 SSD |
| I/O scheduler | Kernel code ordering block requests | mq-deadline, bfq, kyber, none |
Summary
- A hard disk has platters with two surfaces, each split into tracks and sectors; one head per surface on one arm; the same track on all surfaces is a cylinder (live: 409.6 GB capacity).
- Access time = seek + rotational latency (half a rotation) + transfer (live: 9 + 4.17 + 0.0083 ≈ 13.18 ms at 7200 RPM). Seek and rotation dominate.
- Disk scheduling on the queue 98 183 37 122 14 124 65 67, head 53 (live): FCFS 640, SSTF 236 (can starve), SCAN 331, C-SCAN 382, LOOK 299, C-LOOK 322.
- RAID (Patterson, Gibson, Katz, 1988): 0 striping, 1 mirroring, 5 single rotating parity (n − 1 disks usable), 6 double parity (n − 2), 10 striped mirrors (n / 2). Parity rebuild is XOR (live: 3C recovered). RAID is not a backup.
- SSDs: write pages, erase blocks, never overwrite in place; the FTL, garbage collection, wear leveling (live: 750 erases each instead of 6000 on one block) and TRIM (
fstrim). On NVMe, Linux'snonescheduler is often ideal.
Next episode: I/O systems and virtualization: device controllers and drivers, polling, interrupts and DMA, buffering, caching and spooling, hypervisors, virtual machines and containers.