File Allocation Methods in Operating System

There are many numbers of files that are stored on the same disk, the problem is how to allocate these files so that disk space is utilized effectively and files can be accessed quickly. The File Allocation Methods helps the operating system to efficiently store and access the files in the memory.

There are three major methods for file allocation (or disk space allocation) that are widely by operating system:

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

Other methods include FAT(File Allocation Table) and Inode. Each File Allocation method has its advantages and disadvantages. Let’s take a quick look at the infographic.

File Allocation Methods in Operating System

 

Purpose of the File Allocation Methods in Operating System

The purpose of file allocation in operating systems is first of all the efficient use of the disk space or efficient disk utilization. Say for example you have a hard drive and it does not follow a good file allocation method. What are the problems that will be faced by the hard drive –

First, it can suffer from fragmentation. Fragmentation is the small spaces that are left from filling one sector with a determined amount of files and another is the early following of the sectors.

Second, slower memory access if the allocation methods of the memory blocks are not optimum. Today we are storing a huge amount of data in our memory and the method to search and access the memory makes the response time better on the operating system.

Both of the above problems are dealt with file allocation methods in the operating system which provides the file system with the techniques to store and access the file efficiently.

 

Types of File Allocation Methods in Operating System

There are three major ways the operating system applies file allocation: Contiguous indexed and linked file allocation. Every file allocation method has its advantages and disadvantages. The Operating System can support all types of file allocation methods in the operating system but the Operating System mainly uses one type of file allocation method which suits its need.

Types of file allocation methods in Operating System:

1. Contiguous File allocation
2. Linked File Allocation
3. Indexed File Allocation
4. File Allocation Table (FAT)
5. Inode

Contiguous File Allocation Method in Operating System

Mechanism of Contiguous Allocation

The contiguous allocation in Operating systems requires the files that have to be stored in the memory (such as a hard disk) to be first divided logically into smaller chunks.

Then these small chunks are then physically placed into the memory blocks (these blocks have pre-decided small memory spaces, and our main memory is split into many such simpler memory blocks).

Difference between Contiguous and Non Contiguous allocation

The difference between Contiguous memory allocation and non-contiguous memory allocation is that when the file is divided into smaller chunks to be stored into memory blocks then if they are placed sequentially they are known as contiguously allocated and if they are placed randomly they are known as non contiguously allocated.

When the files are placed sequentially in the memory blocks of the main memory then the access of the file becomes easy and this speeds up the search of files in the memory.

Example of Contiguous allocation

For example, A file(F1) is three chunks (F1-A, F2-B, F2-C) and then stored into contiguous memory blocks such as block number 0100,0101, and 0102.

Also, there is a magnetic head that points to the file on a magnetic disk in our hard drive.

The head when searching for information in our file (F1) has to only search sequentially in the three memory blocks(0100,0101,0102) and that’s it you will find the information.

And that is not the same case with non-contiguous, the magnetic has to cover ten or twenty times more distance before finding the required blocks in which the file is stored.

Properties & Advantages of Contiguous File Allocation

Directory Mechanism of Contiguous Allocation

Also, in contiguous file allocation, when the files are stored into the memory blocks there exists a directory that maintains the record of the starting address of every file’s memory block.

As the file is divided and stored into contiguous memory blocks, therefore, the directory maintains the first memory block address of each file, so if you have to search the file you can refer to the directory and which will point you to the starting block address of that file.

Contiguous Allocation Supports both sequential and direct file access methods

The File Access in the contiguous memory allocation is much simpler than other methods and therefore it can support both the sequential and direct access methods.

For sequential access, the file system remembers the address of the last block that was referenced earlier, and from there it can continue to read the next blocks if required.

For direct access to block 110 of a file that starts at block 100, we can immediately access block 100 + 10. Thus, direct access allows the program to read and write blocks rapidly, in no particular order.

If you want to learn more about how operating system access Files in Memory then you can visit – File Access Methods in OS. 

Disadvantages of Contiguous File Allocation

Contiguous Allocation suffers from both Internal and External Fragmentation

The major disadvantage of the contiguous file allocation method is that the storage memory will suffer from both internal and external fragmentation.

This is because we are allocating the file sequentially in predefined memory blocks.

This also becomes a reason for wastage of memory spaces which is taken care of by the non-contiguous allocation method.

Internal Fragmentation in Contiguous allocation

The internal fragmentation happens when the storage memory is split into mounted size blocks (or memory blocks).

When there is a request to store some file into the memory, then these mounted sized blocks are allocated.

And if in case the file is bigger than these mounted sized blocks then it has to skip some memory blocks and when it finds the appropriately sized block then it stores the files.

The skipped memory blocks are left empty and this causes internal fragmentation, as the next file has to be stored sequentially after the previous file and this will lead to empty space.

External Fragmentation in Contiguous allocation

External Fragmentation happens when there is a sufficient amount of empty space in the memory to store new files but is unable to store because these empty spaces are broken pieces of empty spaces that are scattered all over the memory rather than being a large cumulated memory chunk.

The contiguous memory allocation always seeks to find a large empty memory chunk which is either more than or equal to file size and then store it.

This causes smaller empty pieces of memory to be leftover in contiguous file allocation and causing external fragmentation. This problem is silver by the Non-Contiguous File Allocation.

Also check, how free space management in OS happens. 

File Size Initialization restricts file growth in Contiguous Allocation

The other disadvantage of the contiguous file allocation is when a file is created initially by the user then he has to allocate the file size to be stored into the memory blocks, the starting address of the first block, and the number of blocks allocated is then stored into the directory.

So, when more data is to be added then it becomes a problem because we have already allocated the number of blocks to store the file sequentially, therefore this restricts the growth of the file, and the solution to this problem is given by the non-contiguous file allocation.

Contiguous File Allocation Program 

If you want some hands-on practice on contiguous file allocation methods then you can visit – Sequential File Allocation Program in C and C++.

You will find a complete explanation of the program with the algorithm along with the output at the end of the program.

 

Non-Contiguous File Allocation Methods in Operating System

We have already seen how contiguous memory allocation works and what are its advantages and disadvantages. Now, we will see what is a non-contiguous allocation.

The difference between these allocation methods follows space and time tradeoff.

The contiguous memory allocation will take more space but at the same time will reduce the time to store and search the blocks of the file.

Whereas in non-contiguous allocation you will gain more space to store by avoiding the fragmentation, but time to find the block of the file will increase.

Non-Contiguous File Allocation are of two types:

1. Linked File Allocation
2. Indexed File Allocation

Linked File Allocation Method 

Linked File Allocation in operating systems solves the problem that was faced by the contiguous memory allocation and that is it solves fragmentation problem (inefficient use of storage memory).

In contiguous we use to store the blocks of files one after another in a sequence in the memory, but in the linked file allocation the blocks of files are scattered in the memory and these blocks are linked to each other with the help of a pointer.

Linked File Allocation Example

For example, a file (F1) is divided into five file-subparts (F1-A, F1-B, F1-C, F1-D, F1-E) and then they are stored in the memory blocks randomly(the main memory is split into various memory blocks which have pre-allocated size).

Say first file-subpart(F1-A) is stored at a memory block 16, second file-subpart(F1-B) is stored at memory block 9, third file-subpart(F1-C) is stored at memory block 40, fourth file-subpart(F1-D) is stored at memory block 40, and fifth subfile(F1-E) is stored at memory block 1.

Conclusion of Example

Pointer

We can see these files subparts are stored randomly in the memory blocks of our memory. So, there must be a way that we had mapped these file subparts to each other and this way is called the pointer.

Each memory block contains the pointer that points to the next memory block. Pointers are variables that are capable of containing the address of other variables (and in our case, it’s the memory blocks).

Pointer’s Visibility

But these pointers are not made visible to the user and only the file allocation system can see the pointers.

Therefore if each memory block is of the size of 500 bytes, and the disk address (the pointer) requires 4 bytes then the user sees the size of the memory block as 496 bytes.

Properties & Advantages of Linked File Allocation

Directory Mechanism of Linked File Allocation

The linked file allocation also has the directory as we saw in contiguous memory allocation. Each directory entry has a pointer to the first memory block of the file.

Empty File Blocks in Linked Allocation

The pointers can be initialized with a nil value to signify an empty file and also the data field is set to 0.

So whenever any new block has to be stored, these empty blocks are searched by the file allocation system and then written with a new data field and then linked at the end of the file with the help of a pointer.

Linked Allocation solves External Fragmentation

The main advantage that comes with using this file allocation system is that there is no external fragmentation.

There is an efficient use of the memory blocks and it does not suffer from external fragmentation as the contiguous memory allocation does.

When there’s an empty block in the memory then it is stored in a directory as a free-space in the memory list and when a new file has to be allocated a block then we simply look in our free-space list and store the file in the blocks from the list.

Disadvantages of Linked File Allocation

Linked Allocation does not Support Direct Access

The disadvantage which occurs with the linked file allocation is that it can support sequential access but it cannot support direct access to the memory blocks, instead it has to travel from block to block to find the right block.

This direct access was possible in contiguous memory allocation as the files were stored sequentially so to search a particular block you have to just know where you are and then you can jump directly to the required block by some calculations.

But this is not possible with the linked file allocation where pointers lead from one block to another block.

The direct access capability is provided in the indexed allocation and therefore indexed allocation helps in faster access of the memory blocks than the linked list allocation.

Linked Allocation has Excess Pointer Overheads

The other disadvantage that is faced in the linked file allocation method is the memory required to store the pointers.

If a pointer requires 4 bytes out of a 500-byte block, then 0.80 percent of the disk is being used for pointers, rather than for information.

Therefore each file block requires more size to store pointers at the end than it would have if only data is stored.

Linked Allocation is Less Reliable

The files in the linked file allocation method are connected through pointers that are scattered all over the disk. So if any failure in hardware or bug in the operating system happens then it may result in damage of pointers or may create errors such as linking to other files. This problem can be resolved by the double linked list or maintaining the file name in relative block number but this leads to creating more overheads for every file.

Linked File Allocation Program 

If you want some hands-on practice on Linked File allocation methods then you can visit – Linked File Allocation Program in C and C++.

You will find a complete explanation of the program with the algorithm along with the output at the end of the program.

 

File Allocation Table (FAT)

The File Allocation Table (FAT) is a variation by which we can utilize the linked file allocation method. This method was used by MS-DOS and OS/2 operating systems. 

In this method, a section of the disk at the beginning of each volume is set aside to contain the table. The table has one entry for each file block and the directory is maintained to index the block number. 

The FAT works similar to linked lists. The directory of the FAT table points to the first block of the file. The FAT table entry that contains the block number pointed by the directory then points to the next block number of the file, the chain is then followed till it reaches the last block of the file and this contains the end of file value. 

The unused blocks in the FAT table are 0 valued. If a new file has to be added then this 0 value is replaced by the block numbers of the file and the last file block number is denoted by the end of the file.

Increases the seek time unless the table is cached

 

Indexed File Allocation Method 

The Linked File allocation solved the problem of external fragmentation and the size declaration problem that existed with the contiguous memory allocation.

Now, the indexed allocation solves the problem of the direct access method which linked list file allocation did not support.

The Indexed Allocation is therefore faster to search blocks in the memory, as well there is no external fragmentation in this method.

Comparison With Linked File Allocation

In the linked list allocation, the pointers to the block were scattered with the blocks themselves all over the disk.

The pointers were present at the end of each memory block which pointed to the next memory block.

But in the indexed file allocation, it brings all the pointers in one location and that is called the index block.

So, the pointers which were present at the end of each block were brought together, and then they were allocated in one complete file block that will contain only the pointer (or address) of the stored data.

Indexed Allocation Example

For example, a file (F1) is divided into five file-subparts (F1-A, F1-B, F1-C, F1-D, F1-E) and then they are stored in the memory blocks randomly.

Say, first file-subpart(F1-A) is stored at a memory block 16, second file-subpart(F1-B) is stored at memory block 9, third file-subpart(F1-C) is stored at memory block 40, fourth file-subpart(F1-D) is stored at memory block 40 and fifth subfile(F1-E) is stored at memory block 1.

Now, there will be an index block let’s say at block 10.

This index block will contain the pointers (or addresses) of other blocks in a table.

So if you have to search for the file then the directory will tell you the location of the index block and then the index block will point you to the address of the blocks that contain our file.

Properties & Advantages of Indexed File Allocation

Directory Mechanism of Indexed Allocation

Now, as the contiguous, as well as the linked list allocation, have their directory so does the indexed file allocation.

Every file has its index blocks, so the number of index blocks will be the same as the number of the files (not the memory block) that are stored in the memory.

The indexed file allocation directory contains the address of these index blocks.

Indexed Allocation Supports both Sequential and Direct Access

As the indexed File Allocation method uses the pointers and index blocks and therefore it can support both sequential access and direct access.

Since the index blocks contain all the pointers of the memory blocks, therefore, the direct access of any memory block becomes possible as the head can read the index block and by applying some basic logic it can directly jump to the pointer which will have our required memory block.

Disadvantages of Indexed File Allocation

Lots of Memory required by Pointers Overhead

The disadvantage of indexed file allocation is that there are a lot of pointers overhead involved in storing the memory blocks.

This pointer overhead can make up more than 1% of the total memory and hence these pointers consume some space that could have been used in storing the file.

Growth of Index Block

The index block which contains the pointers of the file memory blocks can sometimes get filled up.

The index block now requires more space to store the pointer as the size of the file grows therefore a completely new memory block has to be allocated to the index blocks so now more than one index block is containing the pointer of the file memory blocks.

This problem can also be solved by multilevel indexing.

Multilevel Indexing

In multi-level indexing, the first level index block points to the set of second-level index blocks, and the second level index blocks points to the actual file blocks.

Therefore to access a file block, the operating system has to use the first level index block to find the second-level index block, and then the second level index block will lead the operating system to the required file block.

If the data in the file keeps on increasing then this method can be continued to the third and fourth levels depending on the size of the file.

Indexed File Allocation Program

If you want some hands-on practice on Indexed File allocation methods then you can visit – Indexed File Allocation Program in C and C++.

You will find a complete explanation of the program with the algorithm along with the output at the end of the program.

 

Inode

This method is an improvised version of indexed file allocation method. In this method, the first 15 pointers of the index block are kept in the file’s inode. Among these 15 pointers, 12 pointers are the direct blocks that contain the address that directly points to the location of the file blocks that contain the information of the file.

Therefore for small size files does not require to have index blocks. The next three-pointers in the file’s inode are the indirect blocks that do not point to the file block containing the information about the file. The first indirect block contains the address that points to the disk block (index block) which contains the address of the file blocks. The second indirect block points to the disk block which contains the address of the index blocks and these index blocks have the actual file block address that will point towards the file block containing actual data. Similarly, the last pointer points towards the address of the third indirect block. 

 

Frequently Asked Question (FAQ)