Last Updated on July 20, 2023 by Mayank Dham
File Allocation Methods are an important feature of file systems that aid in efficient storage and management. These File Allocation Methods in the OS determine how files are stored on the disk drive, which has an effect on file access time in the computer. Their primary goal is to maximize the use of available space and minimize fragmentation, which can impede file access and reduce overall system performance. There are several commonly used file allocation methods, each with its own set of advantages and disadvantages.
What are File Allocation Methods?
Before we learn about File Allocation methods, let’s recap where these File Allocation methods are being used. On an empty hard disk, there are numerous memory blocks where the files are stored and to store the files efficiently, file allocation methods are used.
Certain File Allocation Methods in OS can be used for the task of successful utilization of space on the hard disk. These methods effectively help us in accessing files faster. File Allocation Methods are given as follows:-
- Contiguous File Allocation
- Linked File Allocation
- Index-based FIle Allocation
- File Allocation Table
- Inode
Now that we know the basic understanding of file allocation methods in os, we proceed further to know how each of the allocation methods fare among each other.
Contiguous File Allocation Method
It is a file allocation method where files are stored in contiguous blocks that can be assumed as neighbouring or adjacent, the multiple blocks holding the file. Example of it can be assumed that when we have the current block at position t, the following blocks will be placed at the position t+1,t+2 and goes until t+n-1.
Now let’s take an example along with illustrating the memory blocks in our disk to understand this better.
The distribution of memory blocks for files using a contiguous file allocation method can be described by the table that displays the characteristics of three files named sample.txt, study.pdf, and one.jpeg.
| Name of File | Initial Position | Length | Allocated Memory |
|---|---|---|---|
| sample.txt | 3 | 2 | 3,4 |
| study.pdf | 5 | 4 | 5,6,7,8 |
| one.jpeg | 0 | 2 | 0,1 |
The allocation of the length of blocks is performed contiguously as derived from the above table. The first file consumes two blocks from 2 to 4, the second takes 4 from 5 to 8 and the third takes the first two positions.
Advantages of Contiguous Allocation
Below are some advantages of contiguous allocation:
- It has a simplistic implementation
- It supports direct access as well as sequential access can be performed.
- Accessing the memory is faster with less seek time.
- Disk head moves the minimum if this method is sought after.
Disadvantages of Contiguous Allocation
Below are some disadvantages of continuous allocation:
- The size must be pre-determined and it cannot be altered once allotted.
- Internal or External Fragmentation of the disk is possible.
Linked File Allocation Method
In this file allocation method, instead of contiguous placing of memory blocks together, they are linked to each other at various memory blocks present empty in the disk. The memory blocks are scattered at different positions, pointers are used to refer to the next position in this file allocation method.
Looking at the below illustration and understanding it better.
The distribution of memory blocks for files using a linked file allocation method can be described by the table that displays the characteristics of two files named a and b.
| Name | Start | End |
|---|---|---|
| a | 0 | 2 |
| b | 6 | 5 |
In we study both the disk illustration and table together, we find out that a, starts at 0, points next block at 7 and ends at 2. Similarly, b, start and 6, with the next reference at 5 and ending at 4. Here a and b are respective files with allocated memory blocks.
Advantages of Linked Allocation
Below are the advantages of Linked allocation:
- External Fragmentation does not exist
- It offers easiness as no contiguous spaces are required.
- Only the start entry is needed to access.
Disadvantages of Linked Allocation
Below are the Disadvantages of Linked allocation:
- Traversal to memory blocks must be done to reach a block with no direct access.
- Pointers take up extra space in the block as a reference to the next block.
- Any error or loss to the pointer can put the disk blocks to risk.
Indexed File Allocation Method
Indexed File Allocations is one of the file allocation methods in os that is somewhat similar to linked file allocation with slight modifications as linked blocks have a location to the next block in linked but in indexed, all the memory block locations are put into a single block called the index block. Thereby, instead of moving block to block for retrieval, we can extract all the blocks from pointers stored in the index file.
The below illustration can help you understand in a better manner.
From the above figure, we can conclude that index block 1 consists of all the pointers of the file with -1 set as an unused part of the index block.
Advantages of Indexed Allocation
Below are the advantages of Indexed allocation:
- It reduces the chances of External Fragmentation.
- Direct accessibility is provided pointers to all the memory blocks stored
- Better than sequential access.
Disadvantages of Indexed Allocation
Below are the Disadvantages of Indexed allocation:
- Memory is wasted on small files.
- Losing access to the Index block can result in a loss of file.
- Single index block cannot store enormous pointers for large files.
Resolving Large Files on Single Indexed Block Issue
To solve this problem, we can resort to the below three techniques,
- Linked Schemes:- In case the file size is too high, two or more indexed blocks are joined together to hold the pointers with each block containing the address to the next indexed block.
- Multilevel Scheme:- In this, there can be multiple layers of the indexed block where the topmost will point to the bottommost, beneath which there will be disk blocks where the file has been stored.
- Combined Scheme:- When a special block contains all the essential information such as name, size and authority while the half portion also contains the address of the memory blocks the file is stored in. It also goes by the name inode or Information node.
File Allocation Table
File Allocation Table was introduced as an improved follow-up to the Linked Allocation Method as no random access is allowed in the linked allocation of files but in File Allocation System, shortened to FAT, all the disk block links are maintained and cached.
The working depends on storing the entry block and reading the entry block in the file allocation table to access. It reduces the seek time by caching the disk blocks to avoid accessing all the blocks.
Below is a depiction of FAT that can help us understand it in a better manner.
Inode
Another one of the many file allocation methods in OS where all the data such as name, attribute and size etc. are stored in one part of it while the other part stores the pointers to the memory block holding the file.
There are pointers that are direct as well as a few that are indirect. With indirect pointers being of three types, the single indirect block contains only the address of the block containing the data of the file. while the double indirect block contains the points to the pointers that point to somewhere else.
Here is an illustration that can help us understand the information node in a better manner.
Conclusion
File allocation methods are an essential component of computer operating systems because they govern how files are stored and accessed on disk or other storage media. These methods are intended to ensure the efficient storage of files and data, which is required for computer systems to function properly. The number and size of files that must be stored, the specifications of the operating system and applications, and the speed and capacity of the storage media all influence the choice of a file allocation method. The chosen file allocation method should be capable of meeting storage requirements while preventing data fragmentation.
Frequently Asked Questions
1. What is a file allocation method in an operating system?
A file allocation method is a way of storing files on a disk. It determines how files are assigned to physical storage locations on the disk and how space is managed as files are added, deleted, or modified.
2. What are some file allocation methods in OS?
File allocation methods are Contiguous allocation, Linked Allocation, Indexed Allocation, FAT and inode.
3. What is the difference between sequential and random access file allocation methods?
In sequential file allocation, files are stored one after another on the disk, with no gaps between them. In random access file allocation, files are assigned to any available space on the disk, and there may be gaps between them.
4. How does a file allocation method affect disk performance?
The choice of file allocation method can have a significant impact on disk performance. Sequential file allocation can be faster for reading and writing large files but may result in wasted space and fragmentation. Random access file allocation can be slower for reading and writing large files but can make more efficient use of disk space.