A Fast File System for Unix

Old File System

  • A file system is described by its superblock

    • number of data blocks in the FS
    • a count of the maximum number of files
    • a pointer to the free list
    • a linked list of all the free blocks in the FS

  • Main problem: although the free list was initially ordered for optimal access, it quickly became scrambled as files were created and removed.

    • Random free list -> force a seek before every block access

Problems & Solutions

Problem Solutions
Random data block placement in aging file system allocate data in same file close together (Cylinder groups)
inodes allocated far from data blocks inodes and data close together
low bandwidth utilization larger block size
small max file size larger block size
waste from large block size fragments (different sizes)
recovery replicated superblocks (superblocks not placed in same track to minimize effect of platter fatures)
Device oblivious parameterize file systems to device characteristics

FFS Organization

  • each disk has one or more FS.
  • a FS is described by its superblock
  • superblock located at the beginning of the FS's diskpartition.

Cylinder groups

  • Divide a disk partition into one or more cylinder groups
  • bookkeeping information (Associated with each cylinder group) has
    • a redundant copy of the superblock
    • space for inodes
    • a bit map (replaces free list)
    • summary information
  • bookkeeping info begins at a varying offset from the beginning of the cylinder group.
    • In this way, any single track, cylinder, or platter can be lost without losing al copies of the superblock.

Storage utilization

  • Bigger block brings disk consumption waste for small files. To solve this, a single FS block is divided into one or more fragments. The block map associated with each cylinder group records the space available at the fragment level.

Layout Policies

  • global policy: use file system wide summary info to make placement of inode and data blocks
  • local allocation routine: use locally optimal scheme to lay out data blocks
    • try to place all the inode in a directory in the same cylinder group
    • try to place data blocks in the same cylinder group

Functional enhancements

  • long file names
  • file locking
  • symbolic links
  • rename
  • quotas: restrict the amount of file system resources that a user can obtain.

  • writes are async!
  • UFS: write faster -> seek time in reading
  • FFS: write more overhead -> need to organize data

results matching ""

    No results matching ""