Do you think IIT Guwahati certified course can help you in your career?
Introduction
The operating system stores data in memory blocks using a variety of file allocation mechanisms. In the Operating System, there are five different types of file allocation methods: Contiguous file allocation, Linked File Allocation, Indexed File Allocation, File Allocation Table (FAT) and Inode.
In this article, you will read in detail about file allocation in OS, its types, advantages, and disadvantages. Let's drive in.
What is File Allocation in OS?
When a hard drive is formatted, a system has numerous tiny spaces to store files called blocks. The operating system stores data in memory blocks using various file allocation methods, which enables the hard disk to be used efficiently and the file to be accessed.
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.
1. Contiguous File Allocation
In the contiguous allocation methods, the files are allocated the disk blocks in a contiguous manner, meaning that if a file's starting disk block address is x, then it will be allocated the blocks with address x+1, x+2, x+3,……., provided the blocks are not already occupied.
Suppose a file abcd.doc has a starting disk block address of 2, and it requires four such blocks; hence in the contiguous allocation method, the file will be allocated the disk blocks with the address as 2, 3, 4, and 5.
The operating system also maintains a directory table that includes the file name along with the starting address and the length of the blocks allocated. The length represents the number of disk blocks required by the file.
In the above figure, it can be seen that the file "os.pdf" requires four disk blocks and its starting disk block address is 1. Therefore the blocks allocated to the file are 1, 2, 3, and 4.
Similarly, for “dbms.doc” the blocks allocated are 7, 8, and 9 since its starting address is 7 and length is 3.
Advantages of contiguous file allocation
Since the blocks are allocated in sequential order, therefore it can be accessed in a sequential manner since the starting address and the length is already available in the directory table.
The block allocation is similar to the array. Given the starting address, we can "jump" to any block address by simply adding the block size to the starting address, just as we do while accessing any block in an array. Hence the contiguous allocation also allows random access to the blocks.
The seek time is less because of the contiguous allocation of blocks. This makes it very fast.
Disadvantages of contiguous file allocation
It suffers from internal fragmentation. Suppose the size of a block is 2KB, but the file that has to be stored is just 1KB. In that case, an extra 1KB remains unutilized and the memory is wasted.
It suffers from external fragmentation. If there are sufficient blocks available to store a file, but if they are not contiguous, the file cannot be stored.
The size of the file can be increased only if free contiguous disk blocks are available.
Although it allows fast access, memory management is poor.
2. Linked File Allocation
The linked allocation works just like the linked list. The problem with contiguous allocation was that memory remained unutilized due to external fragmentation. The solution to the problem was to allocate the disk block in the form of a linked list where every block was a node.
The blocks are allocated in such a way that every block contains a pointer to the next block that is allocated to the file.
The above image shows how the linked allocation works. The file "os.pdf" has to be allocated some blocks. The first block allocated is 4. Block 4 will have a pointer to the next block 8, block 8 will have a pointer to block 10, block 10 will have a pointer to block 11, block 11 will have a pointer to block 2, and finally, block 2 will point to 3. In this manner, a total of six blocks are allocated to the file in a non-contiguous manner. The ending block ( block 3) will not point to any other block.
By allocating memory through linked allocation, the memory is utilized in a much better manner. Since the blocks are not allocated in a contiguous manner, it is not necessary that files can be allocated only if contiguous free blocks are available. Every block contains a pointer to the next block, which is part of the memory for that particular file.
The directory table will contain the file name along with the starting disk block address. It does not contain length in this case but the address of the ending block.
Advantages of linked file allocation
There is no external fragmentation because blocks can be allocated in random order with the help of pointers. Contiguous allocation is not required.
File size can be increased, even if the contiguous blocks are not available, provided there are enough blocks to store the file.
Judicious use of memory.
Disadvantages of linked file allocation
Random access is not allowed since the memory allocation is not contiguous. Therefore with the help of the starting block address, we cannot directly jump to some other block, just as we cannot jump to any node in the linked list with just the head pointer.
It is relatively slow because of more seek time.
Every block needs to contain extra information about the pointer to the next block.
3. Indexed File Allocation
Although linked allocation used the memory in an efficient way, it was slower than contiguous allocation. There was a need for an allocation method such that the disk blocks are used properly and also the access time is less. This is where indexed allocation comes to the rescue. It can be thought of as a mixture of linked and contiguous allocation that is more efficient in terms of space and time.
There are index blocks that contain pointers to the blocks occupied by the file. Thus every file has its own index block, which is a disk block, but instead of storing the file itself, it contains the pointers to other blocks that store the file. This helps in randomly accessing the files and also avoiding external fragmentation.
From the above image, we can see that block number 8 does not store the file but contains the pointers to various other blocks, which store the file. The directory table contains only the file name and the index block for the respective files.
Below is the pictorial representation of index block 8, which contains the pointers that determine the address of the blocks that store the "os.pdf" file.
Since the size of every block is limited, there will be problems if the numbers of pointers to other blocks are very large in number such that a block is not sufficient to store it.
The following are the ways to solve such a problem:
Linked scheme: In case the number of pointers is too large to fit in a single block, the first block, along with the pointers to other blocks, also holds a pointer to another index block which stores the rest of the pointers.
Multilevel Index: This is very similar to multilevel paging. Here the first-level index block will point to various second-level index blocks, which will then hold pointers to various blocks that are occupied by the file. The second-level index blocks can again point to several third-level index blocks depending on the file size.
Inode: Inode is created by the file system. It contains various attributes of the files. The rest of the Inode is used to contain disk block addresses. It also holds pointers to single, double, triple, etc., and indirect blocks. The single indirect block holds pointers to various disk blocks. The double indirect block holds pointers to some other index blocks, which in turn holds addresses of various blocks that are occupied by the file.
Advantages of Indexed allocation
No external fragmentation.
Allows random access to disk blocks.
Allows direct access, reducing complexity.
Disadvantages of Indexed allocation
It is very complex.
Extra memory for index blocks.
Large pointer overhead.
For files that are very large, single index block may not be able to hold all the pointers.
But it can be resolved by the following approaches:-
Linked Scheme
Linked Scheme uses links or pointers to connect data in a database. This is commonly used in linked lists or tree data structures to establish relationships between data elements.
Multilevel Index
A multilevel index is an indexing technique that uses multiple levels of index structures to improve search efficiency. It breaks down an extensive index into smaller, reduces search time, and improves performance.
Combined Scheme
The combined scheme uses a combination of different indexing techniques to optimize database performance. This aims to provide faster access and retrieval of data, By leveraging the strengths of various indexing methods.
4. File Allocation Table (FAT)
The File Allocation Table (FAT) is a file system format commonly used in older computer systems and removable storage devices. It organizes data storage by maintaining a table that tracks the allocation status of individual file clusters on a storage medium. While less common today, FAT was instrumental in early computing, providing a straightforward way to manage files and directories.
Advantages of File Allocation Table (FAT)
FAT is widely supported across different operating systems and devices, making it easy to share data between various platforms without compatibility issues.
FAT's straightforward structure makes it relatively easy to implement and understand, which was particularly advantageous in the early days of computing.
The minimalistic design of FAT requires less storage space and processing power compared to more modern file systems, making it suitable for systems with limited resources.
Due to its simplicity, FAT file systems are often recoverable using basic data recovery tools, allowing for potential retrieval of lost or deleted data.
Disadvantages of File Allocation Table (FAT)
FAT lacks advanced metadata capabilities, such as support for extended file attributes, which limits the types of information that can be associated with files.
As files are created, modified, and deleted, the FAT file system can suffer from fragmentation, leading to slower file access times and inefficient use of storage space.
FAT does not offer robust security features or fine-grained access controls, leaving files more vulnerable to unauthorized access and modifications.
FAT file systems have limitations on file sizes and partition sizes, which can be restrictive when dealing with large files or storage devices.
5. Inode
An inode, short for "index node," is a data structure in Unix-like file systems that stores metadata about a file, such as its permissions, ownership, size, and location of data blocks on the storage device. Inodes play a crucial role in efficient file management and data retrieval, as they enable the operating system to quickly locate and access files. Each file or directory on the file system corresponds to an inode, allowing for organized and optimized storage allocation.
Advantages of Inode
Inodes enable rapid access to file metadata and data blocks, making file operations like opening, reading, and writing faster and more efficient.
Inodes allow sparse files—files with unallocated gaps—to be managed effectively, as they only allocate space for actual data blocks, optimizing storage usage.
Inodes facilitate the creation of hard links, which are multiple directory entries pointing to the same inode.
Inodes enhance file system stability by maintaining data consistency and reducing the risk of data corruption.
Disadvantages of Inode
Inodes consume a fixed amount of storage space regardless of file size.
File systems have a finite number of inodes available.
As directories grow in size, the number of inodes used to represent directory entries can increase.
Inode allocation and management can contribute to storage fragmentation.
Frequently Asked Questions
What is an index allocation method?
The index allocation method is like having a guidebook for file storage in a file system. It creates a separate index structure that works as a map. It helps to organize and manage files effectively. This index keeps track of where each file block or data unit is located, making it easier to access and manage files efficiently.
Which file allocation method is best and why?
The indexed allocation method is often considered the best file allocation because it solves the challenges associated with a contiguous and linked allocation.
What is the difference between linked allocation and indexed allocation?
File random access is not supported by linked allocation because each block can only be found from the previous. While indexed allocation combines all the pointers into one index block.
What is the purpose of file allocation methods?
File allocation methods determine how files are stored on a storage medium. They optimize space utilization, access speed, and file organization. Different methods, like contiguous, linked, or indexed allocation, balance trade-offs to efficiently manage data storage and retrieval on a file system.
Conclusion
File allocation methods are required to use the disk block efficiently and allow quick access to the blocks.
There are Five types of allocation methods: Contiguous, Linked, Indexed, File Allocation Table (FAT), and Inode.
External fragmentation is observed in contiguous allocation but not in other allocation methods.
Linked allocation does not allow random access to the disk blocks.
Indexed allocation is the most appropriate method of file allocation.
84+ registered