File Allocation Methods in OS

File Allocation Methods in OS

File allocation methods are basically ways in which any file is stored in the memory block of the system. There are three types for file allocation methods –

  • Contiguous Allocation
  • Linked List Allocation
  • Indexed Allocation

The main idea behind these methods is to provide:

  • Efficient disk space utilization.
  • Fast access to the file blocks.
files

Contagious Allocation

In this method for any file in the memory block, it occupies a Contagious i.e. continuous set of memory blocks.

For example for file F1, if the starting address is 1 and the memory blocks required by it is 3. Then it will be stored at b[1], b[2], b[3].

Each file will have a directory entry, that will have the following information –

  1. Address of starting block
  2. Space required by file in terms of the memory block

For example consider the following structure for four files – file 1, file 2, file 3.

Contagious AllocationSize or Memory Blocks ReqStarting AddressColor in Diagram
File 151Green
File 2311Blue
File 3320Red

Every file must occupy contiguous blocks on the storage device. The word contiguous means continuous.

Advantages

  • Since items are stored in a contiguous fashion, there is limited or no disk-head movement which reading/writing the blocks.
  • Also seek time is less. Consequently, there is a great improvement in the access time of a file.
  • We just need to know the starting index and length of the file to access the contiguously stored files in memory.
  • For any file the kth block which starts at index i can easily be obtained as (i+k)

Disadvantages

  • Memory utilization can be inefficient as such type of file allocation suffers from internal and external fragmentation.
  • For large size blocks, allocation may get difficult as contiguous blocks may be scarce in the memory.
  • Growing file problem may occur, initial space allocated may be sufficient but the file size may grow over time, example for word file where we are typing. Memory block currently allocated may become insufficient
  • Compaction (which is a solution for fragmentation) can take up a lot of time and may need a system to be down, wherein normal operation will not be permitted
File Allocation Method Linked List Allocation

Indexed Allocation

In indexed allocation method, all the pointers (pointing to the next block in the Linked list) are gathered together into one location known as Index Block.

  • The file-allocation table contains a multi-level index for each file.
  • Indirection blocks are introduced each time the total number of blocks “overflows” the previous index allocation.

You get all block locations in one index file. Blocks are stored in the index file in order of access.

Example – 

  • In the image below/right the index block is 19 and contains all block addresses of file jeep
  • The first block storage is 9 then 16 then 1 and then 10 and 25 in order
  • A negative number denotes index block list being empty. That is the file has not grown large enough to fill more blocks
File allocation methods index allocation
Indexed Allocation

Highlights

For Linked Allocation the pointers along with the blocks were scattered across the disk and needed to be retrieved in order by visiting each block to access the file

Advantages

  • The kth entry of the index-block is a pointer to the kth block of the file.
  • All addresses can be found in one index block file
  • Doesn’t suffer from external fragmentation

Disadvantages

  • Seek time may still be high as memory is scattered all over the disk
  • Corruption in index files may lead to loss of file access locations.