Unit V — I/O & File Management

FILE
//ALLOC
METHODS

How an OS maps files to physical disk sectors determines everything — access speed, fragmentation behavior, and storage efficiency. Explore all three allocation strategies and the buffering pipeline that feeds the CPU.

3 Alloc Methods

4 Buffer Types

64 Block Simulator

Phase 01

The Disk as a Block Array

A disk is divided into fixed-size blocks (also called clusters), numbered sequentially from 0 to N−1. Every file must be stored across some subset of these blocks. The allocation strategy decides which blocks a file gets.

Seek Time

Time for disk arm to reach the right track. Scattered blocks = more seeks = slower access.

Fragmentation

External: free space in non-contiguous holes. Internal: unused space within allocated blocks.

Access Pattern

Sequential reads benefit from contiguous blocks. Random access needs direct block pointers.

Phase 02

Three Allocation Strategies

Contiguous Allocation

Files occupy consecutive disk blocks in a single run

LINEAR

Disk State (64 blocks shown, 32 per row)

Row 0–7

Row 8–15

After Del

Red dashed = external fragmentation hole after File A deleted

Directory Entry

file_a.txt

kernel.bin

FORMULA

Block(i) = Start + i

O(1) random access — just arithmetic

REAL-WORLD USE

CD-ROM, DVD filesystems (ISO 9660). Files are write-once, so no fragmentation occurs.

Linked Allocation

Each block holds data + pointer to the next block

CHAINED

Block Chain — File "notes.txt"

→8

→

→15

→

→21

→

→EOF

File Allocation Table (FAT)

Block#	Next Block	File
2	8	notes.txt
3	-1	data.csv
8	15	notes.txt
10	14	data.csv
15	21	notes.txt
21	EOF	notes.txt

Directory Entry (only needs start block)

notes.txt

ACCESS BLOCK i

Follow i pointers from start

Time complexity: O(i) — expensive for large files

FAT VARIANT

MS-DOS FAT12/16/32 stores the entire FAT in RAM — turning linked access into O(1) table lookup.

Indexed Allocation

One index block stores all data block addresses for a file

INDEXED

Disk View — Index block (gold border) holds pointers

Blocks

2★

★ Index Block #2 — inode for "img.png"

[0]→ blk 4

[1]→ blk 6

[2]→ blk 8

[3]→ blk 11

Directory Entry

img.png

ACCESS BLOCK i

Read index_block[i] → seek there

Two disk reads total for any block

UNIX INODE

ext2/ext4 use 12 direct + 1 indirect + 1 double-indirect + 1 triple-indirect pointers, supporting files up to 16 TiB.

Phase 03

I/O Buffering Strategies

CPUs operate at GHz speeds. Disks operate at millisecond speeds. Buffering bridges this gap — intermediate memory staging areas that decouple the producer and consumer so neither waits unnecessarily.

① No Buffer

CPU blocks on every I/O operation

I/O CPU IDLE

CPU blocks entirely on every I/O — utilization as low as 10–15% on disk-heavy tasks.

② Single Buffer

OS provides one intermediate buffer slot

BUF

I/O CPU

I/O and CPU alternate on one slot — idle time remains whenever one side finishes before the other.

③ Double Buffer

Two buffers let I/O and CPU run simultaneously

BUF A

BUF B

I/O CPU

While CPU drains Buffer A, I/O fills Buffer B — near-zero CPU idle for sequential workloads.

④ Circular Buffer

Ring of N buffers for sustained high-throughput I/O

W▼

R▲

I/O CPU

Head/tail pointers advance around a ring — maximum throughput for burst I/O; used in audio drivers, network stacks, and video streaming.

Phase 03.5

Method Comparison

Criterion	Contiguous	Linked	Indexed
Sequential Access	Excellent	Good	Good
Random Access	O(1) — Direct	O(n) — Traverse	O(1) — Via index
External Fragmentation	High over time	None	None
File Growth	Difficult	Easy — append block	Limited by index
Overhead	Minimal (start+len)	Pointer per block	Full index block
Directory Entry	Start + Length	Start block only	Index block #
Real-World Usage	CD-ROM, ISO	FAT12/16/32	ext2, ext4, UNIX

FILE //ALLOC METHODS

The Disk as a Block Array

Seek Time

Fragmentation

Access Pattern

Three Allocation Strategies

I/O Buffering Strategies

Method Comparison

Build Your Own Filesystem

FILE
//ALLOC
METHODS