Introduction
File allocation: core operating system function to map logical files to physical disk space. Objective: optimize disk utilization, minimize access time, avoid fragmentation. Allocation impacts file system reliability, speed, and scalability. Methods evolved to balance speed, space, and complexity.
"The choice of file allocation method fundamentally affects system performance and robustness." -- Abraham Silberschatz
File Allocation Methods
Overview
Three primary methods: contiguous, linked, indexed. Each differs in data structure, access efficiency, and fragmentation handling. Trade-offs exist between simplicity, speed, and flexibility.
Contiguous Allocation
Allocates consecutive disk blocks for entire file. Simple mapping: base address + offset. Fast direct access. Prone to external fragmentation.
Linked Allocation
Files stored as linked list of blocks scattered on disk. Each block contains pointer to next. Eliminates external fragmentation. Sequential access efficient; random access costly.
Indexed Allocation
Uses index block containing pointers to file blocks. Supports direct access. Avoids external fragmentation. Overhead due to index block(s).
Contiguous Allocation
Mechanism
Allocate continuous block range at file creation. Address translation: logical block i → physical address = base + i.
Advantages
Fast sequential and random access. Simple implementation. Minimal overhead.
Disadvantages
External fragmentation: free space split into small chunks. File size must be known in advance or requires costly resizing.
Management Techniques
Compaction: move files to consolidate free space. Preallocation: reserve extra space for file growth.
Use Cases
Systems prioritizing speed and simplicity. Boot files, system binaries.
Linked Allocation
Mechanism
File as linked list of blocks. Each block contains pointer to next physical block. Directory stores pointer to first block.
Advantages
Eliminates external fragmentation. Easier file size growth. No need for contiguous space.
Disadvantages
Random access inefficient: must traverse pointers sequentially. Pointer overhead per block reduces usable space. Reliability risk if pointer corrupted.
Variants
File Allocation Table (FAT): centralized table storing all pointers. Reduces pointer overhead in blocks.
Applications
Floppy disks, FAT-based file systems.
Indexed Allocation
Mechanism
Single index block stores pointers to all file blocks. Logical block number maps directly to index block entry.
Advantages
Direct access to any block. No external fragmentation. Flexible file size.
Disadvantages
Index block overhead. Large files require multi-level or combined indexing. Index block failure impacts entire file.
Multi-Level Indexing
Index block points to other index blocks. Improves scalability for large files.
Combined Indexing
Mix of direct, single indirect, double indirect pointers. Example: Unix inode structure.
Allocation Table Structures
File Allocation Table (FAT)
Centralized table storing next block pointers for all files. Simplifies linked allocation. Table cached in memory for speed.
Inode Structure
Unix-style metadata block stores pointers to data blocks. Contains direct and indirect pointers. Supports complex indexing.
Bitmap Allocation
Bitmap tracks free/used blocks. Efficient space management. Used in conjunction with allocation methods.
Directory Entries
Store file metadata and starting pointers. Indexing points to allocation structures.
Fragmentation Issues
External Fragmentation
Free space divided into small chunks preventing large contiguous allocation. Common in contiguous allocation.
Internal Fragmentation
Unused space within allocated blocks due to fixed block size. Affects all methods to some extent.
Fragmentation Impact
Slower access, increased seek time, wasted disk space.
Mitigation
Compaction, preallocation, variable block sizes, defragmentation utilities.
File Access and Performance
Sequential Access
Contiguous and linked allocation efficient. Indexed allocation slightly slower due to index lookup.
Random Access
Indexed allocation fastest. Contiguous also fast. Linked allocation slow due to pointer traversal.
Metadata Overhead
Indexed and linked methods have pointer storage overhead. Contiguous minimal metadata.
Disk Seek Time
Contiguous minimizes seek time. Fragmentation increases seek for linked and indexed methods.
Allocation Algorithms
First-Fit
Allocate first sufficiently large free space. Fast but leads to fragmentation.
Best-Fit
Allocate smallest adequate space. Reduces fragmentation but slower search.
Worst-Fit
Allocate largest available space. Attempts to leave large free chunks.
Next-Fit
Continue search from last allocation point. Simple, reduces search time.
Algorithm First-Fit:for each free block in free list: if block.size >= request_size: allocate block breakComparison of Allocation Methods
| Feature | Contiguous | Linked | Indexed |
|---|---|---|---|
| Access Type | Sequential/Random | Sequential | Sequential/Random |
| External Fragmentation | High | None | None |
| Internal Fragmentation | Low | Pointer overhead | Index block overhead |
| File Size Flexibility | Poor | Good | Excellent |
| Implementation Complexity | Simple | Moderate | Complex |
Real-World Implementations
FAT File System
Uses linked allocation with centralized FAT table. Widely used in removable media and embedded systems.
Unix File System (UFS)
Indexed allocation via inode structure. Multi-level indirect pointers for large files.
NTFS
Uses Master File Table (MFT) with indexed allocation. Supports complex metadata and security features.
Ext4
Extents-based allocation: contiguous block ranges with extent trees. Reduces fragmentation and metadata overhead.
Future Trends in File Allocation
Extent-Based Allocation
Group contiguous blocks into extents. Improves allocation efficiency and reduces fragmentation.
Copy-on-Write (CoW)
Allocate new blocks on write. Facilitates snapshots and versioning.
Flash-Aware Allocation
Optimizes wear leveling and garbage collection for SSDs.
Distributed File Allocation
Allocation across networked storage nodes. Requires metadata synchronization and fault tolerance.
References
- Silberschatz, A., Galvin, P. B., & Gagne, G. "Operating System Concepts," 9th ed., Wiley, 2013, pp. 234-258.
- Tanenbaum, A. S., & Bos, H. "Modern Operating Systems," 4th ed., Pearson, 2015, pp. 180-210.
- Stallings, W. "Operating Systems: Internals and Design Principles," 9th ed., Pearson, 2017, pp. 312-345.
- McKusick, M. K., & Neville-Neil, G. V. "The Design and Implementation of the FreeBSD Operating System," 2nd ed., Addison-Wesley, 2014, pp. 95-130.
- Card, R., Ts'o, T., & Tweedie, S. "Design and Implementation of the Second Extended Filesystem," Proceedings of the First Dutch International Symposium on Linux, 1994, pp. 33-46.