File Storage

Contiguous Allocation

File data is stored on disk. Like programs in memory, it can occupy contiguous or noncontiguous space. Storage methods differ in efficiency and read/write performance.

Contiguous storage places file data in consecutive physical disk locations. Data is tightly packed, making sequential reading efficient by reducing disk seeks.

Contiguous storage requires knowing the file size in advance so the file system can allocate a sufficiently large consecutive region. The file header therefore records the starting block and length, which describe the file's contiguous disk space.

Although efficient to read and write, contiguous storage suffers from fragmentation and difficulty extending a file. For example, files A, B and C occupy these disk blocks:

If B is deleted, the largest contiguous free region contains six blocks. A new file needing at most six blocks can be stored, but a larger file cannot be stored contiguously on this disk.

Linked Allocation

Linked storage uses scattered blocks, eliminating external fragmentation and improving space utilization while allowing files to grow dynamically. It can be implemented with implicit or explicit links.

Implicit links use a file header containing the first and last block locations. Each data block reserves space for a pointer to the next block, so all blocks can be found by following pointers from the head, without requiring contiguous storage.

Implicit linked storage cannot directly access a data block: pointers must be followed sequentially, and they consume storage space. It is vulnerable to pointer loss or corruption caused by software or hardware errors, which can make file data inaccessible.

Moving pointers out of data blocks into an in-memory table reduces pointer overhead inside data blocks and avoids reading each data block merely to follow its pointer. Explicit links store the next-block pointers in one table for the disk. This table is called the File Allocation Table (FAT).

Indexed Allocation

Linked storage addresses external fragmentation and dynamic growth but does not efficiently support direct access. Indexed storage solves this by creating an index block for each file, containing a list of pointers to data blocks, like a book's contents page. The file header points to the index block, whose entries locate the data blocks.

Indexed storage has these advantages:

1. Files are easy to create, grow and shrink
2. It avoids external fragmentation
3. It supports sequential and random reading and writing

If a file is too large for one index block to hold its index entries, linked and indexed storage can be combined into chained index blocks. Each index block reserves a pointer to the next index block; once its entries are exhausted, that pointer locates the next index block's information.