TOPIC: File allocation methods
22BCE2216
COLIN PAUL EBBY
Operating System (theory)
Disk Space
Allocation Methods
Disk space allocation is a crucial aspect of file system design,
determining how files are stored on disk. The main challenge is efficiently
utilizing disk space while enabling quick file access. This overview
examines three major allocation methods: contiguous, linked, and
indexed allocation. Each approach has distinct advantages and trade-offs
in terms of performance, space utilization, and flexibility.
by Colin Paul Ebby
Contiguous Allocation
Contiguous allocation requires each file to occupy a set of contiguous
blocks on the disk. This method minimizes disk seeks, as accessing
adjacent blocks typically requires no head movement. The file's location
is defined by the disk address of the first block and its length. While
simple and efficient for sequential and direct access, contiguous
allocation faces challenges in finding space for new files and dealing with
external fragmentation as files are created and deleted.
1 Advantages
Minimal disk seeks and efficient access
2 Challenges
Finding contiguous space for new files
3 Issue
External fragmentation over time
Contiguous Allocation:
Fragmentation and
Compaction
External fragmentation becomes a significant issue in contiguous
allocation as free disk space gets broken into small, unusable chunks. To
address this, some systems employ compaction - copying the entire file
system to create one large contiguous free space, then reallocating files
back. While effective, compaction can be time-consuming, especially for
large disks, and may require system downtime. Modern systems often
perform online defragmentation, but at a performance cost.
Fragmentation Occurs
1 Free space breaks into small chunks
Compaction Initiated
2 File system copied to create contiguous space
Files Reallocated
3 Data moved back to defragmented space
Linked Allocation
Linked allocation solves the contiguous allocation problems by storing
files as linked lists of disk blocks scattered across the disk. The directory
contains pointers to the first and last blocks of each file. This method
eliminates external fragmentation and allows files to grow dynamically.
However, it's primarily suitable for sequential access, as direct access
requires following the chain of pointers from the beginning. Linked
allocation also introduces overhead for storing pointers in each block.
1 Advantages
No external fragmentation, dynamic file growth
2 Disadvantages
Inefficient for direct access, pointer overhead
3 Reliability Concerns
Potential issues with lost or damaged pointers
File Allocation Table (FAT)
The File Allocation Table (FAT) is a variation of linked allocation used in
MS-DOS. It stores the linked list structure in a table at the beginning of
each volume, with one entry per disk block. The directory entry contains
the first block number, and the table entries chain to subsequent blocks.
This method improves random access compared to standard linked
allocation, as the FAT can be cached. However, it may still result in
significant disk head movement if not cached effectively.
Block Number FAT Entry
217 618
618 339
339 EOF
Indexed Allocation
Indexed allocation addresses the direct access limitations of linked allocation by using an index block for each file.
This block contains an array of disk block addresses for the file. The directory entry points to the index block,
allowing efficient direct access to any file block. While this method supports direct access and avoids external
fragmentation, it can waste space for small files that require an entire index block. Various schemes exist to handle
large files that exceed a single index block's capacity.
Linked Scheme Multilevel Index Combined Scheme
Links multiple index blocks for Uses multiple levels of index Stores some pointers directly in
large files blocks the inode
UNIX Inode Structure
The UNIX file system uses a combined scheme for indexed allocation,
implemented through the inode structure. An inode stores the first 12
pointers directly, allowing small files to be accessed without an additional
index block. For larger files, it uses single, double, and triple indirect
blocks. This approach balances efficiency for small files with the ability to
support very large files. Modern implementations often use 64-bit or
even 128-bit file pointers to support extremely large file sizes.
Direct Blocks
First 12 pointers for small files
Indirect Blocks
Single, double, and triple indirect
Scalability
Supports files up to exbibytes in size
Performance Considerations
Each allocation method has performance implications. Contiguous allocation offers the best performance for
sequential and direct access but suffers from fragmentation. Linked allocation, including FAT, can result in
scattered file blocks, potentially causing numerous disk seeks. Indexed allocation improves direct access but may
still lead to scattered data blocks. Caching strategies, such as caching the FAT or index blocks, can significantly
improve performance. The choice of allocation method involves trade-offs between access speed, space
efficiency, and implementation complexity.
Contiguous Linked
Best for sequential access, fragmentation issues Flexible growth, poor random access
Indexed Caching
Good direct access, potential block scattering Critical for improving overall performance
