The File Allocation Methods in OS [Operating System] helps the file system to efficiently store and access the files in the main memory. The work of the file system in the operating system is to divide a file into various logical parts or partition it and then store the file in the sectors of the hard drive. The allocation method in the file system is arranging the logically divided file into the physical sector in our hard drive and the way it is used to allocate the file in the sector is the method of file allocation.
There are two types of file allocation methods in OS:
1. Contiguous File allocation
2. Non-contiguous File allocation
The Non-contiguous file allocation also has two types:
a. Linked File Allocation
b. Indexed File Allocation
In real life, say for example some new students were admitted by the school and the students are allotted their class sections. After the students are allotted their class section, his sitting place in each section can be in a continuous manner such as according to roll number where students are sitting one behind another or in a non-continuous manner such as students are allowed to sit in any random place they want. The same goes for the operating system also.
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.
File Allocation Methods in OS [ 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 three types of file allocation methods in the operating system but the OS mainly uses one type of file allocation method which suits its need.
Let’s discuss in detail all the types of file allocation methods in OS
Contiguous File Allocation Method
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 and 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).
Contiguous Allocation in Operating system | Advantages & Disadvantages
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.
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 of Contiguous File Allocation Method in OS
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.
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.
The major disadvantage of the contiguous file allocation method is that the storage memory will suffer from both internal and external fragmentation, and it 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.
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 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.
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.
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 Allocation Methods
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.
Linked File Allocation Method
Linked File Allocation in operating systems solves the problem that was faced by the contiguous memory allocation and that is the 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 List allocation in file allocation with example | Operating system
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.
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). 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 of Linked File Allocation Method in OS
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.
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.
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.
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.
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.
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.
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.
Indexed File Allocation in Operating System
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 their block which will contain only the pointer (or address) of the stored data.
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 of Indexed File Allocation Method in OS
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.
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.
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.
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, 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.
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.