File Allocation Methods in OS

What is File Allocation in OS?

Whenever a hard disk is formatted, a system has many small areas called blocks or sectors that are used to store any kind of file. File allocation methods are different ways by which the operating system stores information in memory blocks, thus allowing the hard drive to be utilized effectively and the file to be accessed. Below are the types of file allocation methods in the Operating System.

Types of File Allocation Methods in Operating System.

• Contiguous File allocation
• Linked File Allocation
• Indexed File Allocation
• File Allocation Table (FAT)
• Inode

Let's have an in-detail explanation about each of them,

Contiguous File Allocation.

First, let's understand the meaning of contiguous, here contiguous means adjacent or touching. Now let's understand what is contiguous file allocation.

What is Contiguous File allocation?

In contiguous file allocation, the block is allocated in such a manner that all the allocated blocks in the hard disk are adjacent.

Assuming a file needs 'n' number of blocks in the disk and the file begins with a block at position'x', the next blocks to be assigned to it will be x+1,x+2,x+3,...,x+n-1 so that they are in a contiguous manner.

Let's understand this diagrammatically.

Example

We have three different types of files that are stored in a contiguous manner on the hard disk.

In the above image on the left side, we have a memory diagram where we can see the blocks of memory. At first, we have a text file named file1.txt which is allocated using contiguous memory allocation, it starts with the memory block 0 and has a length of 4 so it takes the 4 contiguous blocks 0,1,2,3. Similarly, we have an image file and video file named sun.jpg and mov.mp4 respectively, which you can see in the directory that they are stored in the contiguous blocks. 5,6,7 and 9,10,11 respectively.

Here the directory has the entry of each file where it stores the address of the starting block and the required space in terms of the block of memory.

Advantages and Disadvantages

Advantages

• It is very easy to implement.
• There is a minimum amount of seek time.
• The disk head movement is minimum.
• Memory access is faster.
• It supports sequential as well as direct access.

Disadvantages

• At the time of creation, the file size must be initialized.
• As it is pre-initialized, the size cannot increase. As
• Due to its constrained allocation, it is possible that the disk would fragment internally or externally.

Linked File Allocation.

What is Linked File Allocation?

The Linked file allocation overcomes the drawback of contiguous file allocation. Here the file which we store on the hard disk is stored in a scattered manner according to the space available on the hard disk. Now, you must be thinking about how the OS remembers that all the scattered blocks belong to the same file. So as the name linked File Allocation suggests, the pointers are used to point to the next block of the same file, therefore along with the entry of each file each block also stores the pointer to the next block.

Let's understand this better diagrammatically by taking an example.

Example

Here we have one file which is stored using Linked File Allocation.

In the above image on the right, we have a memory diagram where we can see memory blocks. On the left side, we have a directory where we have the information like the address of the first memory block and the last memory block.

In this allocation, the starting block given is 0 and the ending block is 15, therefore the OS searches the empty blocks between 0 and 15 and stores the files in available blocks, but along with that it also stores the pointer to the next block in the present block. Hence it requires some extra space to store that link.

Advantages and Disadvantages

Advantages

• There is no external fragmentation.
• The directory entry just needs the address of starting block.
• The memory is not needed in contiguous form, it is more flexible than contiguous file allocation.

Disadvantages

• It does not support random access or direct access.
• If pointers are affected so the disk blocks are also affected.
• Extra space is required for pointers in the block.

Indexed File Allocation.

What is Indexed File Allocation?

The indexed file allocation is somewhat similar to linked file allocation as indexed file allocation also uses pointers but the difference is here all the pointers are put together into one location which is called index block. That means we will get all the locations of blocks in one index file. The blocks and pointers were spread over the memory in the Linked Allocation method, where retrieval was accomplished by visiting each block sequentially. But here in indexed allocation, it becomes easier with the index block to retrieve.

Let's take an example to explain this better.

Example

As shown in the diagram below block 19 is the index block which contains all the addresses of the file named text1. In order, the first storage block is 9, followed by 16, 1, then 10, and 25. The negative number -1 here denotes the empty index block list as the file text1 is still too small to fill more blocks.

Advantages and Disadvantages

Advantages

• It reduces the possibilities of external fragmentation.
• Rather than accessing sequentially it has direct access to the block.

Disadvantages

• Here more pointer overhead is there.
• If we lose the index block we cannot access the complete file.
• It becomes heavy for the small files.
• It is possible that a single index block cannot keep all the pointers for some large files.

To resolve this issue, we can use the following approaches:

1. Linked scheme
2. Multilevel Index
3. Combined Scheme

1. Linked Scheme

If the file is big then more blocks are required so one index block is insufficient to store all the pointers, therefore to store the pointers two or more index blocks are used where these index boxes are connected using linked file allocation that is each index block stores the pointer to the next index block.

2. Multilevel Index

In this method, the multiple indexes blocks along with the levels of these blocks. Here, the level 1 block is used for pointing to the level 2 block which points to the blocks occupied by the file. These index blocks can be extended to three or more levels according to the size of the file.

3. Combined Scheme

In Combined Scheme, a special block is used to store all the information related to the file like name, authority, size, etc. The special block is called inode(information-node). Some space of this special block is used to store the information related to the field as mentioned above and the remaining space is used to store the addresses of blocks that contain the actual file. The inode is explained further in detail.

File Allocation Table (FAT).

The File Allocation Table (FAT) overcomes the drawback of Linked File allocation. The random access of a particular block is not possible in the linked file allocation. To access a particular block it is necessary to access all its previous blocks. Let's see how File Allocation Table works.

Explanation

In the file allocation table, all disk block links are collected and maintained. Here the number of head seeks is reduced by caching the file allocation table so that the head does not need to go through all the disk blocks to access one particular block.

The whole process of randomly accessing any block using FAT is completed by reading the desired entry of a block from the file allocation table and accessing that particular block.

The diagrammatic representation of FAT is given below -

Advantages and Disadvantages

Advantages

• Random Access to the block is possible in FAT.
• One bad/corrupted disk block cannot corrupt all the other blocks.
• It uses all the disk blocks for data as in linked file allocation it needs extra space for pointers.

Disadvantages

• If entries increase so the FAT size also increases.
• Each entry requires the FAT entry.
• If Entries increase the FAT size increases which increases the size of a block so there are chances of internal fragmentation.

Inode.

In Operating systems based on UNIX, every file is indexed using Inode(information-node). The inode is the special disk block that is created with the creation of the file system. This special block is used to store all the information related to the file like name, authority, size, etc along with the pointers to the other blocks where the file is stored.

Explanation

In this special block, some of its space is used to store the information related to the field as mentioned above and the remaining space is used to store the addresses of blocks that contain the actual file.

The first few pointers in Inode point to direct blocks, i.e they contain the addresses of the disk blocks containing the file data. A few pointers in inode point to the indirect blocks. There are three types of indirect blocks: single indirect, double indirect, and triple indirect.

A single indirect block contains nothing but the address of the block containing the file data, not the file itself as shown in the figure below. Furthermore, the double indirect block points to the pointers which again point to the pointers which point to the data blocks. Further, it goes in a similar way for triple indirect block.

The diagrammatic representation of Inode is given below -

Advantages and Disadvantages

Advantages

• Accessibility of file becomes easy as all the information like metadata and block address is stored inside inode.
• Read-write and creation timestamps are stored inside the inode.
• Filenames do not affect inodes. In other words, a single file can be copied and renamed without losing its address.

Disadvantages

• All new files and folders will be rejected as soon as a file system runs out of inodes.
• Upon 100% utilization of the inodes system will start to notice OS restarting, data loss, applications crashing, and more OS-related issues.