AdvancedOperating Systems · Lesson 15 of 17 · Updated ·
File Allocation and Inode Numericals — Max File Size, Disk Accesses, FAT and Bitmap Size
Lesson 8 described the three ways to place a file on disk and introduced inodes. Exams turn this into arithmetic: "What is the largest file this inode can describe?", "How many disk reads to get block 50?", "How big is the FAT?" Every one of these needs only two numbers — the block size and the pointer (disk address) size — and a clear picture.
1. The three allocation methods in one picture
| Method | Directory stores | Reach block i of the file | Main problem |
|---|---|---|---|
| Contiguous | start block, length | start + i → 1 read | external fragmentation; hard to grow a file |
| Linked | first block (and last) | follow i pointers → i + 1 reads | slow random access; one bad pointer loses the rest |
| Indexed | index block number | read index block, then the data → 2 reads | the index block itself uses space |
Counting convention: block numbers start at 0, and the directory entry is already in memory. If a question numbers blocks from 1 or says the index block is cached, adjust the count.
Example. To read block 9 (the tenth block) of a file: contiguous = 1 read, linked = 10 reads (blocks 0 to 9 one after another), indexed = 2 reads.
FAT (File Allocation Table, used by FAT32 on pen drives) is linked allocation with all the "next" pointers moved into one table. If the table is held in RAM, following the chain costs no disk reads — reaching any block takes 1 disk read.
2. How an inode points to data
A Unix-style inode stores the file's details (owner, size, permissions, times) and a list of block pointers. A common layout is 12 direct pointers plus one single, one double and one triple indirect pointer.
- A direct pointer points to a data block.
- A single indirect pointer points to a block full of pointers to data blocks.
- Double indirect: a block of pointers to blocks of pointers to data. Triple: one more level.
The key number is pointers per block = block size / pointer size. With 4 KB blocks and 4-byte pointers: 4096 / 4 = 1024.
3. Maximum file size
Count the data blocks each pointer can reach, add them, multiply by the block size:
Max size = (direct + p + p² + p³) × block size, where p = pointers per block.
With 4 KB blocks, 4-byte pointers, 12 direct:
| Part | Data blocks | Bytes |
|---|---|---|
| 12 direct | 12 | 48 KB |
| single indirect | 1024 | 4 MB |
| double indirect | 1024² = 1,048,576 | 4 GB |
| triple indirect | 1024³ = 1,073,741,824 | 4 TB |
| total | 1,074,791,436 | about 4 TB |
The triple indirect part is so large that it decides the answer; the others add only a few GB.
KB, MB, GB, TB = 2**10, 2**20, 2**30, 2**40
def max_file_size(block, ptr, direct, single=1, double=1, triple=1):
p = block // ptr # pointers that fit in one block
blocks = direct + single * p + double * p**2 + triple * p**3
return p, blocks, blocks * block
def show(n):
for unit, name in ((TB, "TB"), (GB, "GB"), (MB, "MB"), (KB, "KB")):
if n >= unit:
return f"{n / unit:.2f} {name}"
return f"{n} B"
for block, ptr, direct, d, t in [(4 * KB, 4, 12, 1, 1), (1 * KB, 4, 10, 1, 0)]:
p, blocks, size = max_file_size(block, ptr, direct, double=d, triple=t)
print(f"block {block // KB} KB, {ptr}-byte pointers: {p} per block, {blocks} data blocks, max file {show(size)}")
block 4 KB, 4-byte pointers: 1024 per block, 1074791436 data blocks, max file 4.00 TB
block 1 KB, 4-byte pointers: 256 per block, 65802 data blocks, max file 64.26 MB
The second line is a typical exam variant: 1 KB blocks, 10 direct, one single and one double indirect pointer, no triple. p = 256, so the maximum is (10 + 256 + 65,536) × 1 KB = 65,802 KB ≈ 64.26 MB.
4. Which pointer reaches a given byte?
4 KB blocks, 4-byte pointers, 12 direct. Which pointer is used to read byte 5,000,000 of a file, and how many disk reads are needed (inode already in memory)?
- Logical block number = 5,000,000 ÷ 4096 = 1220 (integer division).
- Blocks 0–11 are direct. Blocks 12 to 12 + 1023 = 1035 use the single indirect pointer.
- 1220 > 1035, so it is in the double indirect range, at position 1220 − 1036 = 184 inside it.
- Reads: the double indirect block → a second-level pointer block → the data block = 3 disk reads.
General rule: direct = 1 read, single = 2, double = 3, triple = 4 (each level adds one pointer block).
This is why small files are fast on Unix-style systems: most files fit in the direct pointers, so one read after the inode gets the data.
5. Size of a FAT
A 20 GB disk has 4 KB blocks. Each FAT entry is 4 bytes. How big is the FAT?
- Number of blocks = 20 GB / 4 KB = 20 × 2³⁰ / 2¹² = 5,242,880.
- FAT size = 5,242,880 × 4 bytes = 20 MB.
Keeping a 20 MB table in RAM is the price of FAT's fast random access. For terabyte disks the table becomes very large, which is one reason modern systems use inodes or extents instead.
6. Free-space management: bitmap size
The OS must also remember which blocks are free. A bitmap uses one bit per block (1 = free, 0 = used, or the other way round).
For the same 20 GB disk: 5,242,880 bits ÷ 8 = 655,360 bytes = 640 KB.
| Method | Idea | Strength |
|---|---|---|
| Bitmap | one bit per block | small; easy to find runs of free blocks |
| Free list | free blocks linked together | no extra space; slow to find many blocks |
| Grouping / counting | store "start block + count" runs | compact when free space is in big chunks |
7. Extents (what modern systems do)
File systems such as ext4 and NTFS describe a file as a few extents: "start at block 1000, length 300". It is contiguous allocation in pieces — fast like contiguous, but able to grow like indexed. You may see this as a one-line interview question: "How does ext4 store a large file efficiently?"
Common mistakes
- Using the number of bits in a pointer as its size in bytes (a 32-bit pointer is 4 bytes).
- Forgetting the direct pointers when finding which range a block falls into.
- Counting the inode read when the question says the inode is already in memory (or the other way round).
- Mixing powers of 2 and 10: in these questions 1 KB = 1024 bytes and 1 GB = 2³⁰ bytes.
- For linked allocation, saying "1 read" — you must follow the chain.
Quick recap
- Pointers per block p = block size / pointer size.
- Max file = (direct + p + p² + p³) × block size; with 4 KB blocks and 4-byte pointers it is about 4 TB.
- Reads to a data block: direct 1, single 2, double 3, triple 4 (inode in memory).
- Block i: contiguous 1 read, linked i + 1, indexed 2.
- FAT size = blocks × entry size; bitmap size = blocks / 8 bytes.