File Allocation Methods
There are different kinds of methods that are used to allocate disk space. We must select the best method for the file allocation because it will directly affect the system performance and system efficiency. With the help of the allocation method, we can utilize the disk, and also files can be accessed.
There are various types of file allocations method:
- Contiguous allocation
- Linked allocation
- Indexed allocation
- Linked Indexed allocation
- Multilevel Indexed allocation
There are different types of file allocation methods, but we mainly use three types of file allocation methods:
- Contiguous allocation
- Linked list allocation
- Indexed allocation
These methods provide quick access to the file blocks and also the utilization of disk space in an efficient manner.
Contiguous Allocation: - Contiguous allocation is one of the most used methods for allocation. Contiguous allocation means we allocate the block in such a manner, so that in the hard disk, all the blocks get the contiguous physical block.
We can see in the below figure that in the directory, we have three files. In the table, we have mentioned the starting block and the length of all the files. We can see in the table that for each file, we allocate a contiguous block.
Example of contiguous allocation
We can see in the given diagram, that there is a file. The name of the file is ‘mail.’ The file starts from the 19th block and the length of the file is 6. So, the file occupies 6 blocks in a contiguous manner. Thus, it will hold blocks 19, 20, 21, 22, 23, 24.
Advantages of Contiguous Allocation
The advantages of contiguous allocation are:
- The contiguous allocation method gives excellent read performance.
- Contiguous allocation is easy to implement.
- The contiguous allocation method supports both types of file access methods that are sequential access and direct access.
- The Contiguous allocation method is fast because, in this method number of seeks is less due to the contiguous allocation of file blocks.
Disadvantages of Contiguous allocation
The disadvantages of contiguous allocation method are:
- In the contiguous allocation method, sometimes disk can be fragmented.
- In this method, it is difficult to increase the size of the file due to the availability of the contiguous memory block.
Linked List Allocation
The linked list allocation method overcomes the drawbacks of the contiguous allocation method. In this file allocation method, each file is treated as a linked list of disks blocks. In the linked list allocation method, it is not required that disk blocks assigned to a specific file are in the contiguous order on the disk. The directory entry comprises of a pointer for starting file block and also for the ending file block. Each disk block that is allocated or assigned to a file consists of a pointer, and that pointer point the next block of the disk, which is allocated to the same file.
Example of linked list allocation
We can see in the below figure that we have a file named ‘jeep.’ The value of the start is 9. So, we have to start the allocation from the 9th block, and blocks are allocated in a random manner. The value of the end is 25. It means the allocation is finished on the 25th block. We can see in the below figure that the block (25) comprised of -1, which means a null pointer, and it will not point to another block.
Advantages of Linked list allocation
There are various advantages of linked list allocation:
- In liked list allocation, there is no external fragmentation. Due to this, we can utilize the memory better.
- In linked list allocation, a directory entry only comprises of the starting block address.
- The linked allocation method is flexible because we can quickly increase the size of the file because, in this to allocate a file, we do not require a chunk of memory in a contiguous form.
Disadvantages of Linked list Allocation
There are various disadvantages of linked list allocation:
- Linked list allocation does not support direct access or random access.
- In linked list allocation, we need to traverse each block.
- If the pointer in the linked list break in linked list allocation, then the file gets corrupted.
- In the disk block for the pointer, it needs some extra space.
The Indexed allocation method is another method that is used for file allocation. In the index allocation method, we have an additional block, and that block is known as the index block. For each file, there is an individual index block. In the index block, the ith entry holds the disk address of the ith file block. We can see in the below figure that the directory entry comprises of the address of the index block.
Advantages of Index Allocation
The advantages of index allocation are:
- The index allocation method solves the problem of external fragmentation.
- Index allocation provides direct access.
Disadvantages of Index Allocation
The disadvantages of index allocation are:
- In index allocation, pointer overhead is more.
- We can lose the entire file if an index block is not correct.
- It is totally a wastage to create an index for a small file.
A single index block cannot hold all the pointer for files with large sizes.
To resolve this problem, there are various mechanism which we can use:
- Linked scheme
- Multilevel Index
- Combined Scheme
- Linked Scheme: - In the linked scheme, to hold the pointer, two or more than two index blocks are linked together. Each block contains the address of the next index block or a pointer.
- Multilevel Index: - In the multilevel index, to point the second-level index block, we use a first-level index block that in turn points to the blocks of the disk, occupied by the file. We can extend this up to 3 or more than 3 levels depending on the maximum size of the file.
- Combined Scheme: - In a combined scheme, there is a special block which is called an information node (Inode). The inode comprises of all the information related to the file like authority, name, size, etc. To store the disk block addresses that contain the actual file, the remaining space of inode is used. In inode, the starting pointer is used to point the direct blocks. This means the pointer comprises of the addresses of the disk blocks, which consist of the file data. To indicate the indirect blocks, the next few pointers are used. The indirect blocks are of three types, which are single indirect, double indirect, and triple indirect.
In the UNIX operating system, every file is indexed with the help of Inode. An Inode is a block that is created at the time when the file system is designed.
There are various types of information included in Inode:
- Attributes of the file, such as timestamp, permissions, details, ownership, etc.
- The total number of direct blocks that comprise of the pointer to the starting blocks.
- In Inode, there is a single indirect pointer. It is used to point an index block. If using direct blocks, entire file cannot be indexed, then, in that case, we use a single indirect pointer.
- Inode also contains a double indirect pointer. This pointer is used to point a disk block.
- In Inode there is another pointer, which is a triple index pointer. This pointer is also used to point a disk block.