Skills101

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

A 16-block disk strip shown three times: contiguous allocation uses blocks 3 to 6; linked allocation uses blocks 1, 7, 10 and 14 joined by arrows; indexed allocation keeps the list 2, 5, 11, 13 in index block 9

MethodDirectory storesReach block i of the fileMain problem
Contiguousstart block, lengthstart + i → 1 readexternal fragmentation; hard to grow a file
Linkedfirst block (and last)follow i pointers → i + 1 readsslow random access; one bad pointer loses the rest
Indexedindex block numberread index block, then the data → 2 readsthe 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.

An inode with 12 direct pointers going straight to data blocks, a single indirect pointer to one block of pointers, a double indirect pointer to a block of pointer blocks, and a triple indirect pointer three levels deep; with 4 KB blocks each pointer block holds 1024 pointers

  • 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:

PartData blocksBytes
12 direct1248 KB
single indirect10244 MB
double indirect1024² = 1,048,5764 GB
triple indirect1024³ = 1,073,741,8244 TB
total1,074,791,436about 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)?

  1. Logical block number = 5,000,000 ÷ 4096 = 1220 (integer division).
  2. Blocks 0–11 are direct. Blocks 12 to 12 + 1023 = 1035 use the single indirect pointer.
  3. 1220 > 1035, so it is in the double indirect range, at position 1220 − 1036 = 184 inside it.
  4. 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?

  1. Number of blocks = 20 GB / 4 KB = 20 × 2³⁰ / 2¹² = 5,242,880.
  2. 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.

MethodIdeaStrength
Bitmapone bit per blocksmall; easy to find runs of free blocks
Free listfree blocks linked togetherno extra space; slow to find many blocks
Grouping / countingstore "start block + count" runscompact 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.

Practice what you learned

📝 Quiz: File Allocation and Inode Numericals5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →