Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 66 ยท Files and Storage

File Allocation Methods

Understand how a file system places a file's blocks on disk: contiguous, linked, FAT and indexed allocation, with fragmentation, access cost and Python simulations.

A disk is a long array of fixed-size blocks (often 4 KB). A file that is 10 KB long needs three of them. The question this lesson answers is: which three, and how does the file system remember them? The answer is the file's allocation method, and it shapes speed, wasted space and how easily files can grow.

Three goals compete: fast access (especially for sequential and random reads), efficient use of space (little waste), and easy growth (files rarely stay the same size). No method wins everywhere, which is why real systems mix ideas.

Contiguous allocation

Each file occupies a run of consecutive blocks. The directory stores two numbers: the start block and the length. A file starting at block 14 with length 3 uses blocks 14, 15, 16.

  • Pros: Excellent speed. Sequential reads need almost no head movement, and direct access to logical block i is just start + i.
  • Cons: The file system must find a hole big enough (first fit, best fit or worst fit, as with memory allocation). Over time free space breaks into small holes, which is external fragmentation. Growing a file may need to move it. You must also guess the size when the file is created.

Contiguous allocation survives where files are written once and read many times (CD/DVD file systems, some embedded devices), and extents (see below) bring its advantages back into modern systems.

Linked allocation

Each block holds the data plus a pointer to the next block. The directory stores the first (and maybe last) block. Blocks can be anywhere on the disk, so there is no external fragmentation and a file grows by taking any free block.

  • Pros: No size guessing, no external fragmentation, easy growth.
  • Cons: Direct access is slow. To reach block i you must follow i pointers, each one a separate disk read. Pointers eat a few bytes per block, and one damaged pointer loses the rest of the file.

FAT: linked allocation done right

The File Allocation Table moves all the pointers out of the data blocks into one table at the start of the volume. Entry n holds the number of the block that follows block n, or a special end-of-chain marker. The table can be cached in memory, so following a chain no longer needs a disk read per hop. FAT12, FAT16 and FAT32 (and exFAT) are used on USB sticks and memory cards.

Indexed allocation

Each file gets an index block that lists all of its data block numbers in order. The directory entry points to the index block. Entry i of the index is the location of logical block i, so direct access is one lookup plus one read.

  • Pros: Direct access without external fragmentation, easy growth.
  • Cons: An index block costs space even for tiny files, and a file bigger than one index block needs a scheme to extend it.

Ways to handle large files:

  • Linked index blocks: the last slot of an index block points to the next index block.
  • Multilevel index: an outer index points to inner index blocks, which point to data.
  • Combined scheme (Unix inode): the inode holds about 12 direct pointers, then one single-indirect, one double-indirect and one triple-indirect pointer. Small files, which are the majority, need no extra blocks; large files pay only for the indirection they need. See the Unix file system.
flowchart LR
    I["Inode"] --> D1["direct 0..11<br/>12 data blocks"]
    I --> S["single indirect"]
    I --> DB["double indirect"]
    I --> T["triple indirect"]
    S --> SD["block of pointers<br/>to data"]
    DB --> DB1["blocks of pointers<br/>to pointer blocks"]

A combined index: the first few blocks are reachable immediately, the rest through levels of indirection.

Extents

Modern file systems (ext4, NTFS, XFS, APFS) record a file as a short list of extents, each (start block, length). A mostly contiguous file needs one or two extents, which gives the speed of contiguous allocation, while a fragmented file simply has more extents. They also pre-allocate space (delayed allocation) so files tend to stay in one piece.

Comparing the methods

Method Sequential Random External fragmentation Growth
Contiguous Excellent Excellent Yes Hard
Linked Good Poor (follow chain) No Easy
FAT Good Fair (table in RAM) No Easy
Indexed Good Good No Easy
Extents Excellent Excellent Little Easy

Simulating the three classic methods

This program builds one 16-block disk and stores the same files with each method, then counts how many disk reads it takes to reach a given logical block.

Python Contiguous vs linked vs indexed

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

External fragmentation in action

Free space can total plenty of blocks and still be unusable by contiguous allocation. The next program creates and deletes files, then tries to place a big one.

Python Fragmented free space

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the deletes there are 7 free blocks, but they sit in three holes of sizes 3, 3 and 1, so the six-block file fails. A linked or indexed file system would have used the scattered holes.

Common mistakes

  • Assuming linked allocation is bad for sequential reads. On a hard disk it is fine if blocks are near each other, and poor only when they are scattered.
  • Forgetting that indexed allocation needs the index block itself in the space budget.
  • Mixing up internal fragmentation (the unused tail of a file's last block) with external fragmentation (unusable holes between files).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which allocation method suffers from external fragmentation?

    Contiguous files need an unbroken run of blocks, so scattered free holes can be too small to use.
  2. 2. Why is direct access slow in plain linked allocation?

    Each block stores the address of the next one, so reaching block i takes i pointer hops, each a disk read.
  3. 3. How does FAT improve on linked allocation?

    FAT separates the chain from the data, so following a chain uses the cached table instead of reading each data block.
  4. 4. What does a Unix inode use to support both small and very large files?

    Direct pointers cover small files cheaply, while indirect levels extend the reach for large files.

Summary

  • Allocation methods decide where a file's blocks go and how the OS finds them again.
  • Contiguous is fastest but fragments and resists growth; linked has no fragmentation but slow random access; FAT caches the chain; indexed gives direct access through an index block.
  • Unix inodes combine direct and indirect pointers; modern file systems use extents.
  • Distinguish internal fragmentation (waste inside a block) from external fragmentation (unusable holes).

Next: Free Space Management