1. Definition
A file system organizes and manages how data is stored, retrieved, and updated on storage devices. It provides abstraction of storage as named files.
2. File Allocation Methods (Very Important)
Contiguous Allocation
- File occupies consecutive blocks on disk
- Fast sequential and random access: block i at (start + i)
- Problems: external fragmentation, file size must be known at creation
- Used in: CD-ROMs
Linked Allocation
- Each block contains pointer to next block; directory holds start block
- No external fragmentation, file can grow dynamically
- Problems: no random access (must traverse), pointer overhead, reliability (one bad pointer loses rest)
- FAT (File Allocation Table): linked allocation with pointers stored in table in memory - enables random access
Indexed Allocation
- Index block holds all pointers to file's data blocks
- Supports random access, no external fragmentation
- Problem: index block overhead for small files; large files need multi-level index
Multi-level Indexing (Unix inode):
- Direct blocks (12): small files - no extra overhead
- Single indirect: one index block → up to 256 blocks (for 1KB blocks, 4B pointers)
- Double indirect: index block → index blocks → data blocks
- Triple indirect: three levels of indirection
3. File Size Calculation (Very Important)
For block size B bytes, pointer size p bytes:
- Pointers per block = B/p
- Max file size = direct + (B/p) + (B/p)² + (B/p)³ blocks
Example (1KB block, 4B pointer, 12 direct):
- Direct: 12 × 1KB = 12KB
- Single indirect: 256 × 1KB = 256KB
- Double indirect: 256² × 1KB = 64MB
- Triple indirect: 256³ × 1KB = 16GB
4. Directory Structure
- Single-level: One directory for all files - naming conflicts
- Two-level: Separate directory per user - no sharing
- Tree-structured: Hierarchical - absolute and relative paths
- Acyclic graph: Allows shared files/directories (hard links, symbolic links)
- General graph: Allows cycles - needs garbage collection
5. Free Space Management
- Bit vector: 1 bit per block (0=free, 1=allocated). Simple but needs memory
- Linked list: Free blocks linked together - poor random access
- Grouping: First free block stores n free block addresses + address of next group block
- Counting: Store (start, count) pairs for consecutive free blocks
6. GATE Trick
Multi-level indexing calculation is very common - know the formula for each level. File access time for linked allocation = O(n) for nth block. FAT overcomes linked allocation's random access limitation. Contiguous allocation suffers external fragmentation; linked and indexed do not.