File Allocation Methods
File allocation methods are used to place the files on hard disk and accessed from the disk as required.
As we know the hard disk is divided into number of physical sectors. That’s why; file is also divided into number of logical blocks. The block size of file is always equal to size of sector in Hard disk. So that, blocks of file could load into the hard-disk sectors.
Blocks of file which are allocated to sectors of hard disk are also known as disk blocks. Following diagram will explain more about file blocks and disk sectors.
Note: The same concept we already discussed in memory management, where the page size was equal to frame size.
For loading the file into hard disk, some allocation methods are used as shown in the following diagram
The main goals of file allocation methods are
- Higher the Performance because access is faster
- Higher the efficiency due to batter disk utilization.
In the next lecture will be cover all File allocation methods in detail.
1. Contiguous Allocation
If all the logical blocks of the file are present in contiguous (sequential) manner into the hard disk then it is a contiguous allocation. Contagious allocation of blocks into the hard disk may start from any location but consecutive. As if the file has five blocks then these 5-block may present at any locations of hard disk i.e. 0-4, 1-5, 2-6, 5-9 or any other locations but should be consecutive.
Let explain with explain
Suppose there are two files. In the file directory, File 1 size is 5 blocks and other file size is 2 blocks. Other file attributes are also given in the file directory table. Then file allocation into the hard disk is shown into the following diagram
Start attribute in directory table tells about the starting position of file in hard desk. And length attribute tells about the number of required block for the file.
i. Easy to implement: As the file came, it is allocated to the hard disk In sequence.
ii. Batter the read performance: As in compiler, there is a need to execute the instructions in sequence. And if all the instructions are placed in hard disk in a contagious manner then it will be very easy for compiler to read the instructions. It is the same case with audio, video and text files etc.
i. External fragmentation may occur: If any file is deleted from hard disk then create a free space which may leads toward external fragmentation.
ii. It is very tough to increase the file size: As if File-1 allocated blocks are 0-4 in the hard disk and File-2 allocated blocks are 5-8. And if the File-1 size is increased then it will be difficult to assign the 5th block to File-1 because it is already allocated to File-2. For this purpose OS moves the sectors to manage some space.
2. Linked List Allocation
External fragmentation and increasing the file size problems are resolved through linked list allocation.
According to Linked List allocation, file does not need to be contiguous on the disk because any block of file may exist on any available location of hard disk. But each disk block at hard disk contains data and pointer. Pointer points to the next block of file on hard disk in the same file.
File-1 with 5 blocks and File-2 with 2 block allocation is given in the following diagram.
The above diagram illustration in simple words, is explain in the following diagram
Last block of each file points to -1. It means there is no more block is available of current file in the hard disk. So, we can also say that -1 represent the end of that particular file.
i. No external fragmentation. ii. Easy to increase the file size. iii. Directory contains only the starting block address. iv. Any block of file can exist in any available location of disk.
i. Random Access is not provided because it is need to traverse each block to get the desired block. ii. Pointers require additional space in the disk. iii. If the chain of pointers is broken then the later blocks could not accessed.
Linked List allocations has two types
- 2.1. Indexed Allocation
- 2.2. Linked Index Allocation
2.1 Indexed Allocation
As the data could not access randomly in linked list allocation but this issue has been resolved through index allocation scheme.
According to index allocation scheme, Directory contains an index block address for each file. This Indexed block does not contain the file data, but it just contains the pointers to all blocks allocated to that particular file in the hard disk.
i. direct access is possible ii. Every pointer is independent.
i. If the index block is fail, then it will cause the loss of entire file. ii. Size of a file depends upon the number of pointers, an index block can hold. iii. Using the index block for a small file is wastage of time and space. iv. More pointers are required which creates overhead.
2.2 Linked Index Allocation
If the file size is too large then its entries into index block is also increased due to which size of index block is increased. And if the index block size is even greater than disk block size then multilevel indexing comes to picture. In such cases we have to link several index blocks together.
Linked index allocations has two types
- 2.2.1 Single level index allocations
- 2.2.2 Multilevel index allocations
2.2.1 Single level linked Index Allocation
Index block of Single level linked index allocation contains
- Attributes: It includes file name, type etc.
- disk pointers : it points to other block for same file
- Pointer for another index block: The last entry of index block will be a pointer which will points to another index block of the same file.
A case, when a file having 5 blocks. One index block size is capable of representing the 3 disk block. Then we require two index block to represent 5 blocks of file in hard disk.
Advantage: No limit with file size.
Disadvantage: Complexity may increase for random access.
2.2.2 Multilevel Index Allocation
In Multilevel index allocation, the index block contains
- Outer level index blocks: It contains the pointers to the inner level index blocks
- Inner level index blocks: It contains the pointers to the file data.
Let explain with Example
Inner level index block: A case, when a file having 16 blocks. One index block size is capable of representing the four disk block. Then we require 4-index blocks to represent 16 blocks of file in hard disk. These 4-index blocks are inner level index blocks.
Outer level index block: If these 4-index blocks do not fit into single disk block, then we have to take multiple blocks of hard disk to accommodate these 4-index blocks.
Suppose 2-index blocks are fit into single disk-block. So, 2 more disk-block are required to accommodate 4-inner level index blocks. These 2-blocks are known as outer level index blocks.
More understanding about the above diagram is
Advantage: No limit with file size.
Disadvantage: Access time for a file may be increase.
Example of Multilevel index block in Unix OS is Inode.