File Allocation Methods

What the OS has to remember

A disk is divided into fixed-size blocks. When you save a file, the operating system chooses blocks for it and must later find them again. The three classic strategies make different trade-offs.

Contiguous allocation

The file occupies consecutive blocks. The directory stores only the start block and the length.

• Fast: reading block k is start + k, a single access, and sequential reads need little disk-head movement.
• Problem: as files are created and deleted, free space breaks into small holes: external fragmentation. Files also cannot easily grow. This is the same issue as in memory allocation.

Linked allocation

Each block stores a pointer to the next block, so a file can be scattered anywhere.

• No external fragmentation, and files can grow easily.
• Slow random access: to reach block k you must follow k pointers, k disk reads. A single lost pointer breaks the rest of the file. FAT keeps all pointers in one table to speed this up.

It is a linked list stored on disk.

Indexed allocation

Each file has an index block holding the addresses of all its data blocks.

• Direct access in two reads: the index block, then the data block.
• No external fragmentation.
• Overhead: one extra block per file. Large files use several index blocks, in a multi-level scheme like the Unix inode.

The scenario in the visualization

16 blocks. Create A (3), B (4), C (3), delete B, then create D (7 blocks).

Comparison

Code

def read_block(method, file, k):
    if method == "contiguous":
        return 1, file.start + k                 # 1 disk access
    if method == "linked":
        block = file.first
        for _ in range(k):                       # k pointer hops
            block = disk[block].next
        return k + 1, block
    if method == "indexed":
        return 2, disk[file.index_block].entries[k]

Common mistakes

• Saying linked allocation has no overhead. Every block gives up some space for the pointer.
• Mixing up internal fragmentation (unused space inside the last block of a file) with external fragmentation (holes between files).
• Forgetting that indexed allocation needs the index block read first, so it takes 2 accesses, not 1.