operating-systems file-management
Definition
File Allocation
File allocation is the method by which the operating system maps logical file blocks to physical addresses on the disk. The goal is to balance performance, storage efficiency, and the ability to grow files.
Allocation Methods
Contiguous Allocation
Each file occupies a set of adjacent blocks on the disk.
- Pros: Excellent performance for sequential and random access (minimal head movement).
- Cons: Causes external fragmentation and makes it difficult to expand files after they are created.
- Usage: Standard for read-only media like CD-ROMs and DVDs.
Chained (Linked) Allocation
Each block contains a pointer to the next block in the file.
- Pros: No external fragmentation; files can grow easily.
- Cons: Very slow for random access (must read every preceding block). Reduced data capacity per block due to pointer overhead. Reliability is poor (one corrupted pointer breaks the file).
Indexed Allocation
All pointers for a file are stored in a central table in memory, known as the File Allocation Table (FAT).
- Pros: Good for both sequential and direct access. Blocks are used entirely for data.
- Cons: The FAT can become very large and must be kept in RAM for efficiency.
i-nodes (Index Nodes)
A per-file data structure that stores the file’s attributes and an array of pointers to its data blocks.
- Structure:
- Direct Pointers: Points directly to the first few data blocks.
- Indirect Pointers: Points to a block that contains pointers to more data blocks.
- Double/Triple Indirect: For extremely large files.
- Efficiency: The i-node only needs to be resident in memory while the file is open.