Understanding File Allocation Methods

Aug 2, 2024

File Allocation Methods

Introduction

  • Files are stored in secondary storage devices (e.g., hard disks).
  • File allocation methods help in utilizing the hard disk space effectively and access files quickly.

Goals of File Allocation Methods

  1. Efficient utilization of hard disk space.
  2. Faster file access.

Types of File Allocation Methods

  1. Contiguous Allocation
  2. Linked Allocation
  3. Indexed Allocation

1. Contiguous Allocation

  • Allocates a set of contiguous blocks for a file.
  • Example:
    • File Size: 20 KB
    • Block Size: 2 KB
    • Total Blocks Needed: 10 (20 KB / 2 KB per block)

File Allocation Table (FAT)

  • Contains information about files stored in secondary storage.
  • Columns in FAT:
    • File Name
    • Starting Block Number
    • Length of File in Blocks

Advantages

  • Simple to implement (only requires contiguous blocks).
  • Best suited for sequential file access (accessing records one by one).

Disadvantages

  • Difficult to find large contiguous blocks as file size increases.
  • Suffer from external fragmentation:
    • Enough free blocks are available, but are non-contiguous.
    • Compaction can solve fragmentation but is costly.

2. Linked Allocation

  • Based on linked list structure where each block contains a pointer to the next block.
  • Example:
    • Disk blocks range from 0 to 11.
    • Each block points to the address of the next block.

Advantages

  • Eliminates external fragmentation since any free block can be used.
  • Suitable for sequential file access.

Disadvantages

  • Requires extra memory for pointers in each block.
  • Accessing the last block requires traversing from the first block, which can be time-consuming.

3. Indexed Allocation

  • Based on an index block that contains addresses of all the blocks allocated for a file.
  • Example:
    • Index block maps addresses of allocated blocks (e.g., 0, 1, 3, 4, etc.).

Advantages

  • Supports both sequential and random file access (can access any block directly).
  • No external fragmentation as blocks do not need to be contiguous.
  • Easy to add new blocks as a file grows (just update the index).

Conclusion

  • Understanding file allocation methods is critical for optimizing disk space and file access efficiency.
  • Each method has its own advantages and disadvantages, making them suitable for different use cases.

Full transcript