File Systems & Disk I/O

File Allocation — How to Store a File on Disk?

Analogy: You need to store 5 boxes of items. Where do you put them? - Contiguous: boxes 1-5 in a row (fast to find, hard to add box 6 later) - Linked: box 1 has note "box 2 is at shelf 7"; box 2 has note "box 3 is at shelf 12"... (flexible, slow to find box 4 directly) - Indexed: a card at the front lists where ALL boxes are (fast to find any, wastes one card)

---

Three Allocation Methods

Contiguous Allocation

File stored in consecutive disk blocks.
Directory entry: (start_block, length)

Example: "report.pdf" starts at block 10, length 5
  [10][11][12][13][14] ← 5 consecutive blocks

Pros:
  ✓ Fast sequential read (blocks are adjacent)
  ✓ Direct access: block k = start_block + k (O(1))
Cons:
  ✗ External fragmentation (holes between files)
  ✗ Hard to extend file (no space after end?)

Linked Allocation

Each block has a pointer to the next block.
Directory entry: (start_block)

Block chain: 10 → 15 → 3 → 22 → null

Pros:
  ✓ No external fragmentation
  ✓ Easy to extend (append a new block)
Cons:
  ✗ No direct access (must traverse chain for block k)
  ✗ Pointer in each block wastes space
  ✗ Pointer corruption = lose rest of file

FAT (File Allocation Table): linked allocation but pointers stored in a table in memory
  → enables random access by traversing the FAT table (faster)

Indexed Allocation

One index block holds ALL block pointers for the file.
Directory entry: (index_block)

Index block: [10, 15, 3, 22, 7, ...]  ← all pointers here

Pros:
  ✓ Direct access: block k = IndexBlock[k]
  ✓ No external fragmentation
Cons:
  ✗ Wasted space for small files (whole index block for tiny file)
  ✗ Max file size limited by index block size

---

Unix i-node — Multi-level Indexed Allocation

i-node structure:
  Metadata (owner, permissions, size, timestamps)
  12 Direct block pointers  → access first 12 blocks directly
  1 Single indirect pointer  → block of N pointers → N more blocks
  1 Double indirect pointer  → block → N blocks → N² more blocks
  1 Triple indirect pointer  → block → block → N blocks → N³ more blocks

Where N = pointers per block = block_size / pointer_size

Max file size calculation:

Block size = 4KB = 4096 bytes
Pointer size = 4 bytes
N = 4096/4 = 1024 pointers per block

Direct:          12 blocks
Single indirect: 1024 blocks
Double indirect: 1024 × 1024 = 1,048,576 blocks
Triple indirect: 1024³ blocks

Max file = (12 + 1024 + 1024² + 1024³) × 4KB ≈ 4 TB

---

Disk Scheduling — Minimise Seek Time

Analogy: A record player (or CD) — the head must physically move to the right track. Minimising head movement saves time.

Disk head current position: cylinder 50 Requests queue (cylinder numbers): 65, 37, 14, 98, 122, 124, 65, 67

FCFS

Serve in arrival order.
50 → 65 → 37 → 14 → 98 → 122 → 124 → 65 → 67
Total movement: 15+28+23+84+24+2+59+2 = 237 cylinders
Simple but high movement.

SSTF (Shortest Seek Time First)

Always go to the nearest request.
50 → 65 → 67 → 65 → 98 → 122 → 124 → 37 → 14
Less movement, but can STARVE distant requests.

SCAN (Elevator Algorithm)

Move in one direction, serve all requests, reverse at end.
50 → 65 → 67 → 98 → 122 → 124 → 37 → 14
No starvation (everyone gets served as head passes).

C-SCAN (Circular SCAN)

Move in one direction, serve all, jump back to start without serving.
More uniform wait times than SCAN (no preference for middle).

LOOK / C-LOOK

Like SCAN/C-SCAN but only travel to last request (not end of disk).
More efficient than SCAN.
LOOK is recommended for most use cases.

---

Disk Access Time

Access time = Seek time + Rotational latency + Transfer time

Seek time:         move head to correct track (5-15ms typical)
Rotational latency: wait for correct sector to come under head
                    Average = half rotation = 0.5 × (60,000/RPM) ms
Transfer time:      time to read/write the data

Example: 7200 RPM disk
Avg rotational latency = 0.5 × (60,000/7200) = 0.5 × 8.33 = 4.17ms

---

RAID — Redundant Array of Independent Disks

RAID 0 (Striping):    Data split across disks. Fast! No redundancy. ONE disk fails → data lost.
RAID 1 (Mirroring):   Exact copy on 2 disks. Can lose 1 disk. 100% storage overhead.
RAID 4:               Stripe + dedicated parity disk. Can recover 1 disk failure.
RAID 5:               Stripe + DISTRIBUTED parity (no parity disk bottleneck). Needs ≥3 disks.
RAID 6:               Stripe + two parity blocks. Survive 2 simultaneous disk failures. Needs ≥4 disks.
RAID 10 (1+0):        Mirror first, then stripe. Fast + redundant. Needs ≥4 disks.

RAID	Min Disks	Tolerates	Storage Efficiency
0	2	0 failures	100%
1	2	1 failure	50%
5	3	1 failure	(N-1)/N
6	4	2 failures	(N-2)/N

---

Quick Check

Q1. Block size = 512 bytes, pointer = 4 bytes. How many blocks accessible via single indirect pointer?

N = 512/4 = 128 pointers per block → 128 additional blocks

Q2. Disk has 7200 RPM. Average rotational latency?

Rotational latency = 0.5 × (60,000ms/7200) = 0.5 × 8.33 = 4.17ms

Q3. SSTF vs SCAN — which one can cause starvation? Answer: SSTF can starve requests far from current head position (always serves nearest, so far-away requests keep getting skipped). SCAN visits all cylinders systematically — no starvation.