File Allocation Methods in Operating System

This is a summary of my notes on operating systems file allocation methods. In the context of operating systems file allocation refers to managing files on disk such that disk space is effectively utilized and files are accessed quickly.

File Allocation Methods in Operating System

Contiguous Allocation

  1. All blocks of the file are consecutive on disk
  2. Deleting files leaves gaps
  3. Compacting disk can be very slow
  4. Simple and efficient indexing
  5. Random access well supported
  6. Difficult to grow: need to preallocate which wastes space
  7. Easy to map from logical to physical address
  8. Let us assume we are going to read some position (pos) in a file. Assuming a block size of (1024) here is how to map from logical to physical address:

    Block number on disk = file start block number + (pos/1024)
    Offset in block = pos%1024
    

Linked Allocation

  1. Linked list of file blocks
  2. Blocks can be scattered on disk
  3. No limit on file size
  4. File can grow easily
  5. Random access well supported
  6. Random access is not easy
  7. Using the same assumptions as before here is how to map from logical to physical address:

    block = start
    for (j = 0; j < pos/1024; j++)
    {
       block = block->next
    }
    Offset in block = pos%1024
    

Linked Allocation Table in RAM

Same as the previous file allocation method but the table resides in memory. It is faster but need to copy the table to disk at some point and keep both copies consistent.

Index Block Allocation

  1. File block addresses are stored in an array which is stored in a disk block
  2. Directory has a pointer to index block
  3. Both random and sequential access are easy
  4. File size limitation depends on array size for example if we have (256) pointers in the index block then the maximum file size will be 256KB assuming 1KB data blocks
  5. Space utilization is good
  6. Files can grow or shrink easily
  7. Using the same assumptions as before here is how to map from logical to physical address:

    block = index[pos/1024]
    offset = pos%1024
    

Linked Index Block Allocation

  1. Similar to linked file blocks but using index blocks instead of data blocks
  2. Good for large files
  3. Both random and sequential access are easy
  4. Random access is slow for large files
  5. Using the same assumptions as before and assuming an index block size of 256 here is how to map from logical to physical address:

    index = start
    block num = pos/1024
    for (j = 0; j < block num/255; j++)
    {
       index = index->next
    }
    block = index[block num%255]
    offset = pos%1024
    

Two Level Index Block Allocation

  1. Allow larger files by creating an index of index blocks
  2. Overhead is now at least two blocks per file
  3. Using the same assumptions as before here is how to map from logical to physical address:

    block num = pos/1024
    index = start[block num/256]
    block = index[block num%256]
    offset = pos%1024
    

Block Allocation with Extents

  1. Reduce space consumed by index pointers because often consecutive blocks in file are sequential on disk
  2. Store block and count instead of block and index
  3. Faster read and write but complex look up

Was it a useful article ? if so, please use the comments section below for questions, corrections or feedback. Thanks for reading.

Search Terms...

Leave a Reply

%d bloggers like this: