Allocation methods: contiguous, linked (FAT), indexed (inodes); free space

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does a hard link share with the original name? from Lesson 6.1.1
2. What octal number is rw-r--r--? from Lesson 6.1.1
3. What is external fragmentation? from Lesson 5.1.1

1 · The Hook

A disk is a long row of numbered blocks. A file needs some of them. Where do they go, and how do we find block 700 of a file quickly? There are three classic answers, each with a GATE favourite: contiguous (fast but fragments), linked/FAT (count pointer hops, size of the FAT), and indexed/inode (maximum file size with direct and indirect pointers, asked in many papers).

3 · Core Concept

Predict First — the answer

101: blocks 0, 1, …, 100 must each be read to follow the chain.

In plain words

Contiguous: give the file one unbroken run of blocks. Linked: let the blocks be anywhere, each pointing to the next. Indexed: let the blocks be anywhere, and keep a separate list (index) of all of them. UNIX's inode is an index that uses extra levels of index blocks for big files.

1. Contiguous allocation

• Directory stores (start block, length). Block b of the file is disk block start + b.
• Fast sequential and direct access.
• External fragmentation; hard to let a file grow.

2. Linked allocation and the FAT

• Each block holds a pointer to the next; the directory stores the first (and last) block.

• No external fragmentation; files grow easily.

• Direct access is slow: reaching block b needs b + 1 reads. Pointers use space; one bad pointer loses the rest of the file.

• FAT (file-allocation table): move all the "next" pointers into one table at the start of the disk, one entry per disk block. Cached in memory, the chain is followed without disk reads.

  FAT size = number of disk blocks × entry size. 2 GB disk, 4 KB blocks → 2¹⁹ blocks; 4-byte entries → 2 MB.

3. Indexed allocation and the UNIX inode

• Each file has an index block listing its blocks; block b = index[b]. Direct access; no external fragmentation; the index costs space.

• Inode: a few direct pointers plus a single indirect (points to a block full of pointers), a double indirect and a triple indirect pointer.

• With block size B and pointer size P, one block holds k = B / P pointers:

  Max file size = (direct + k + k² + k³) × B (drop the terms for pointers that don't exist). Example: 12 direct, B = 4 KB, P = 4 B → k = 1024 → (12 + 1024 + 2²⁰ + 2³⁰) × 4 KB ≈ 4 TB.

• Disk reads to fetch a data block (inode already in memory): direct 1, single indirect 2, double 3, triple 4.

4. Free-space management

• Bit vector (bitmap): one bit per block (1 = free, or 0 = free, by convention). Size = number of blocks / 8 bytes. 1 TB disk, 4 KB blocks → 2²⁸ bits = 32 MB.
• Linked list of free blocks (no wasted space, slow to find many).
• Grouping: the first free block stores addresses of n free blocks.
• Counting: store (first free block, how many follow).

4 · Visual

UNIX inode (block size B, k = B / P pointers per block)

 inode
 +----------------+
 | direct 0..11   |---> 12 data blocks
 | single indirect|---> [k pointers] ---> k data blocks
 | double indirect|---> [k] -> [k] each ---> k^2 data blocks
 | triple indirect|---> [k] -> [k] -> [k] ---> k^3 data blocks
 +----------------+
 max size = (12 + k + k^2 + k^3) x B

5 · Worked Examples

Example 1 Easy

Contiguous allocation: a file starts at block 300 and is 20 blocks long. Which disk block holds file block 7?

Solution

300 + 7 = 307.

Example 2 Medium

Inode with 10 direct pointers, one single and one double indirect pointer; blocks are 256 bytes; pointers 8 bytes. Maximum file size?

Solution

k = 32. (10 + 32 + 32²) × 256 = 1066 × 256 = 272,896 bytes (266.5 KB).

Example 3 GATE

4 KB blocks, 4-byte pointers, 12 direct pointers. The inode is in memory. How many disk reads are needed to read byte 10,000,000 of the file?

Solution

Block number 10,000,000 / 4096 → block 2441. Direct covers 0–11, single indirect covers 12–1035, so 2441 is in the double indirect range → 2 index blocks + 1 data block = 3 reads.

6 · GATE Traps

• k = block size / pointer size: compute it first.
• Use the pointer counts the inode really has (drop k³ if there is no triple indirect).
• FAT has one entry per disk block, not per file.
• Linked allocation: block b needs b + 1 reads (blocks numbered from 0).

7 · Memory Hook

"Contiguous = start + b. Linked = follow b pointers (FAT keeps them in memory). Inode = (direct + k + k² + k³) × B."

8 · Connect the Dots

Chapter 6.1 is complete. Every block read is a trip to the disk, and disks are slow because a head must move. Chapter 6.2 opens the disk up: its geometry, its access time, and the order in which to serve requests.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Inode size

Inode with 8 direct pointers, 1 single and 1 double indirect pointer; block size 512 bytes; pointer size 4 bytes. Maximum file size in bytes?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — FAT

A 2 GB disk uses 4 KB blocks and a FAT with 4-byte entries. FAT size in MB?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — Bitmap

A 1 TB disk with 4 KB blocks uses a free-space bitmap. Bitmap size in MB?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Disk reads

Inode with 12 direct pointers, 4 KB blocks, 4-byte pointers; inode in memory. How many disk reads to fetch file block 500?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Methods

Which allocation method gives fast direct access but suffers from external fragmentation?

1. (A) FAT
2. (B) Indexed
3. (C) Contiguous
4. (D) Linked

10 · Rule Card

• Contiguous: (start, length), block b = start + b; external fragmentation.
• Linked: next pointers; block b needs b + 1 reads. FAT = one entry per disk block, cached.
• Indexed/inode: k = B/P; max size = (direct + k + k² + k³) × B; reads: direct 1, single 2, double 3, triple 4.
• Free space: bitmap (blocks/8 bytes), linked list, grouping, counting.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

disk blockscontiguous allocationlinked allocationfile-allocation tableindexed allocationindex blockinodedirect, single, double and triple indirect pointersmaximum file sizefree-space bitmapfree listgroupingcounting