CS 134

Key Points: Filesystem Organization

Filesystem Layers

  1. High-Level Filesystem:
    • Handles files, directories, and permissions
    • Provides arbitrary-length files and byte-level access
    • Built on top of low-level filesystem
  2. Low-Level Filesystem:
    • Works with numeric file IDs
    • Reads and writes logical blocks
    • Manages block allocation and free space
  3. Block Device Layer:
    • Provides block-level read/write operations
    • Handles buffering and caching
    • May include features like trim for SSDs

Filesystem Organization Schemes

  1. Fixed Partitioning:
    • Divides disk into equal-sized partitions
    • Simple but inflexible
    • Wastes space with internal fragmentation
  2. Dynamic Partitioning:
    • Allocates space as needed
    • Blocks of a file must be contiguous
    • Limited by inability to grow existing files
  3. File Allocation Table (FAT):
    • Uses a table to track chains of blocks
    • Allows noncontiguous files
    • Clusters reduce fragmentation and overhead, but introduce internal fragmentation
  4. Indexed Allocation:
    • Uses index nodes (“inodes”) to track blocks
    • Supports multiple levels of indirection
    • Allows sparse files
  5. Extents:
    • Tracks ranges of contiguous blocks
    • Balances flexibility and efficiency
    • Used in more modern filesystems like HFS+

Free-Space Management

  1. Basic Approaches:
    • Free space lists
    • Bitmaps
    • Zoned allocation
  2. Key Concepts:
    • Internal fragmentation
    • External fragmentation
    • Block coalescing
    • Space reservation
  3. Management Strategies:
    • Ordered free lists for contiguous allocation
    • Bitmap-based allocation for quick status checks
    • Zoned allocation for reduced fragmentation

Remember

  • Filesystem design involves balancing simplicity, efficiency, and flexibility
  • Modern filesystems use sophisticated schemes to manage space effectively
  • Different schemes have different trade-offs for various workloads
  • Metadata management is crucial for filesystem reliability
  • The characteristics of different storage media can't be ignored
  • Free-space management affects both performance and space efficiency

(When logged in, completion status appears here.)