File Allocation Methods

File allocation methods are used to place the files on the hard disk and access them from the disk as required. 

As we know, the hard disk is divided into several physical sectors. That’s why the file is also divided into several logical blocks. The file’s block size is always equal to the size of the industry in the Hard disk. So that blocks of files could be loaded into the hard disk sectors. 

Blocks of files allocated to the hard disk sectors are also known as disk blocks. The following diagram will explain more about file blocks and disk sectors.

file allocation at Hard Disk

Note: The same concept we already discussed in memory management, where the page size was equal to frame size.

Some allocation methods are used for loading the file into a hard disk, as shown in the following diagram.

File allocation Methods

The main goals of file allocation methods are

  • Higher Performance because access is faster.
  • Higher efficiency due to batter disk utilization.

The following lecture will cover all File allocation methods in detail.

1. Contiguous Allocation

If all the logical blocks of the file are present in a contiguous (sequential) manner on the hard disk, then it is a contiguous allocation. Contagious allocation of blocks into the hard disk may start from any location but are consecutive. If the file has five blocks, then this 5-block may present at any location of the hard disk, i.e., 0-4, 1-5, 2-6, 5-9, or any other locations but should be consecutive.

Let me explain with an example.
Suppose there are two files. In the file directory, Fil1’s’s size is five blocks, and the other file’s size is two blocks. Other file attributes are also given in the file directory table. Then, file allocation into the hard disk is shown in the following diagram.

disk-Contiguous-Allocation-example

 The start attribute in the directory table tells us the starting position of the file on the hard desk. The length attribute tells about the number of required blocks for the file.

Advantages

i. Easy to implement: As the file comes, it is allocated to the hard disk In sequence.

ii. Batter the read performance: As in the compiler, there is a need to execute the instructions in sequence. If all the instructions are placed on a hard disk in a contagious manner, it will be effortless for the compiler to read them. It is the same case with audio, video, and text files, etc.

Disadvantages

i. External fragmentation may occur: Any file deleted from the hard disk creates a free space, which may lead to external fragmentation.

ii. It is very tough to increase the file size: File-1 allocated blocks are 0-4 in the hard disk, and File-2 allocated blocks are 5-8. And if the File-1 size is increased, then it will be difficult to assign the 5th block to File-1 because it is already allocated to File-2. For this purpose, OS moves the sectors to manage some space.

2. Linked List Allocation

External fragmentation and increasing file size problems are resolved through linked list allocation.

According to Linked List allocation, a file does not need to be contiguous on the disk because any file block may exist on any available hard disk location. But each disk block on the hard disk contains data and a pointer. The pointer points to the next file block hard disk in the same file.

File-1 with five blocks and File-2 with two block allocations are given in the following diagram.

Linked List Allocation in file system

The above diagram illustration, in simple words, is explained in the following. diagram

Linked List Allocation example in file system

The last block of each file points to -1. It indicates that no more blocks are available for the current function on the hard disk. So, we can also say that -1 represents the end of that particular file.

Advantages

i. No external fragmentation.
ii. Easy to increase the file size.
iii. Directory contains only the starting block address.
iv. Any block of file can exist in any available location of disk.

Disadvantages

i. Random Access is not provided because it is need to traverse each block to
   get the desired block.
ii. Pointers require additional space in the disk.
iii. If the chain of pointers is broken then the later blocks could not accessed.

Linked List allocations have two types

  • 2.1. Indexed Allocation
  • 2.2. Linked Index Allocation

2.1 Indexed AllocaThes The data could not be accessed randomly in linked list allocation, but this issue has been resolved through the index allocation scheme.

According to the index allocation scheme, the Directory contains an index block address for each file. This Indexed block does not have the file data, but it just includes the pointers to all blocks allocated to that particular file in the hard disk.

Index Allocation in file system

Advantages

i. direct access is possible
ii. Every pointer is independent.

Disadvantages

i. If the index block is fail, then it will cause the loss of entire file.
ii. Size of a file depends upon the number of pointers, an index block can hold.
iii. Using the index block for a small file is wastage of time and space.
iv. More pointers are required which creates overhead.

2.2 Linked Index Allocation

If the file size is too large, then its entries into the index block are also increased, increasing the index block’s size. If the index block size is even more significant than the disk block size, then multilevel indexing comes into the picture. In such cases, we have to link several index blocks together.

Linked index allocations have two types

  • 2.2.1 Single-level index allocations
  • 2.2.2 Multilevel index allocations

2.2.1 Single level linked Index Allocation

Index block of Single level linked index allocation contains

  • Attributes: It includes file name, type, etc.
  • disk pointers: it points to another block for the same file
  • Pointer for another index block: The last entry of the index block points to another index block.

Single level linked Index Allocation

A case when a file has 5 blocks. One index block size can represent the 3 disk blocks. Then, we require two index blocks to represent 5 blocks of a file on the hard disk.

Single level linked Index Allocation Example In File System

Advantage: No limit with file size.

Disadvantage: Complexity may increase for random access.

2.2.2 Multilevel Index Allocation

In Multilevel index allocation, the index block contains

  • Outer-level index blocks: These include the pointers to the inner-level indInternalocks
  • Inner-level index blocks: These include the pointers to the file data. Let’s explain with an Example

Inner level index block: A case when a file has 16 blocks. One index block size is capable of representing the four disk blocks. Then, we require 4-index blocks to represent 16 file blocks on the hard disk. These 4-index blocks are iinner-levelindex blocks.

Outer level index block: If these 4-index blocks do not fit into a single disk block, we have to take multiple disk blocks disk to accommodate these 4-index blocks.

Suppose 2-index blocks fit into a single block disk and are required to accommodate 4-inner level index blocks. These 2-blocks are known as outer level index blocks.

Multilevel Index Allocation in File System

More understanding of the above diagram is

Multilevel Index Allocation Example in file system

Advantage: No limit with file size.

Disadvantage: Access time for a file may be increased. An example of a Multilevel index block in Unix OS is Inode.