Implementing Files (see Fig. 2)

• The file system must keep track of
  • which blocks belong to which files.
  • in what order the blocks form the file
  • which blocks are free for allocation
• Given a logical region of a file, the file system must identify the corresponding block(s) on disk.
  • Stored in file allocation table (FAT) (see Fig. 2), directory, Inode
• Creating and writing files allocates blocks on disk

  Figure 2: Left: A possible file system layout. Right: File Allocation Table.
• Allocation Strategies
  • Preallocation
    • Need the maximum size for the file at the time of creation
    • Difficult to reliably estimate the maximum potential size of the file
    • Tend to overestimated file size so as not to run out of space
  • Dynamic Allocation; Allocated in portions as needed
• Portion Size
  • Extremes
    • Portion size = length of file (remember or contiguous)
    • Portion size = block size
  • Tradeoffs
    • Contiguity increases performance for sequential operations
    • Many small portion increase the size of the file allocation table
    • Fixed-sized portions simplify reallocation of space
    • Variable-sized portions minimize internal fragmentation losses
• Methods of File Allocation
  • The file system allocates disk space, when a file is created. With many files residing on the same disk, the main problem is how to allocate space for them. File allocation scheme has impact on the efficient use of disk space and file access time.
  • Common file allocation techniques are:
    • Contiguous
    • Chained (linked)
    • Indexed
  • All these techniques allocate disk space on a per block (smallest addressable disk unit) basis.
• Methods of File Allocation; Contiguous allocation (see Fig. 3a, b)
  • Allocate disk space like paged, segmented memory. Keep a free list of unused disk space.
  • Single set of blocks is allocated to a file at the time of creation
  • Advantages;
    • Only a single entry in the directory entry; Starting block and length of the file
    • easy access, both sequential and random
    • Simple, only starting location (block #) and length (number of blocks) to find all contents
    • few seeks
  • Disadvantages;
    • External fragmentation will occur
    • May not know the file size in advance
    • Eventually, we will need compaction to reclaim unusable disk space.
    • Files can't grow
• Methods of File Allocation; Chained (or linked list) allocation (see Fig. 3c,d,e,f)
  • Space allocation is similar to page frame allocation. Mark allocated blocks as in-use
  • Each block contains a pointer to the next block in the chain
  • Only single entry in a directory entry; Starting block and length of file
  • No external fragmentation; Free-space manageable, no wasted space
  • Files can grow easily
  • Simple; need only starting address
  • Best for sequential files; Poor for random access
  • No accommodation of the principle of locality; Blocks end up scattered across the disk
  • To improve performance, we can run a defragmentation utility to consolidate files.
  • Storing a file as a linked list of disk blocks (see Fig. 3e)
  • Linked allocation with file allocation table (FAT) in RAM (see Fig. 3f)
    • Avoids disk accesses when searching for a block
    • Entire block is available for data
    • Table gets too large for large file systems; Can cache parts of it, but still can consume significant RAM or generate disk traffic
    • Used in MSDOS, OS/2

  Figure 3: (a) Contiguous allocation (b) Contiguous allocation with compaction (c) Storing a file as a linked list of disk blocks (d) Storing a file as a linked list of disk blocks with defragmentation (e) Alternative representation of chained allocation (f) Linked list allocation using a file allocation table in main memory.
• Methods of File Allocation; Indexed allocation (see Fig. 4)
  • Allocate an array of pointers during file creation. Fill the array as new disk blocks are assigned
  • File allocation table contains a separate one level index for each file
  • The index has one entry for each portion allocated to the file
  • The file allocation table contains block number for the index
  • Supports both sequential and direct (easy) access to the file
  • Small internal fragmentation
  • Lots of seeks if the file is big
  • Maximum file size is limited to the size of a block
  • Portions
    • Block sized; Eliminates external fragmentation
    • Variable sized; Improves contiguity, Reduces index size
  • Most popular of the three forms of file allocation
  • Example: UNIX file system

  Figure 4: (a) Indexed allocation with block partitions (b) Indexed allocation with variable-length partitions (c) An example of i-node.