Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0
Notifications Mark All Read
- Login
- Get Prime
0
File Allocation Methods in OS
File Allocation Methods in OS
File allocation methods are basically ways in which any file is stored in the memory block of the system. There are three types for file allocation methods –
- Contiguous Allocation
- Linked List Allocation
- Indexed Allocation
The main idea behind these methods is to provide:
- Efficient disk space utilization.
- Fast access to the file blocks.
File Allocation Methods
Contagious Allocation
In this method for any file in the memory block, it occupies a Contagious i.e. continuous set of memory blocks.
For example: for file F1, if the starting address is 1 and the memory blocks required by it is 3. Then it will be stored at b[1], b[2], b[3].
Each file will have a directory entry, that will have the following information –
- Address of starting block
- Space required by file in terms of the memory block
For example: Consider the following structure for four files – file 1, file 2, file 3.
| Contagious Allocation | Size or Memory Blocks Req | Starting Address | Color in Diagram |
|---|---|---|---|
| File 1 | 5 | 1 | Green |
| File 2 | 3 | 11 | Blue |
| File 3 | 3 | 20 | Red |
Every file must occupy contiguous blocks on the storage device. The word contiguous means continuous.
Advantages
- Since items are stored in a contiguous fashion, there is limited or no disk-head movement which reading/writing the blocks.
- Also seek time is less. Consequently, there is a great improvement in the access time of a file.
- We just need to know the starting index and length of the file to access the contiguously stored files in memory.
- For any file the kth block which starts at index i can easily be obtained as (i+k)
Disadvantages
- Memory utilization can be inefficient as such type of file allocation suffers from internal and external fragmentation.
- For large size blocks, allocation may get difficult as contiguous blocks may be scarce in the memory.
- Growing file problem may occur, initial space allocated may be sufficient but the file size may grow over time, example for word file where we are typing. Memory block currently allocated may become insufficient.
- Compaction (which is a solution for fragmentation) can take up a lot of time and may need a system to be down, wherein normal operation will not be permitted.
Linked List Allocation
As the name suggests the use of linked lists is there –
Rather than the memory being continuous, it is scattered on available space at the disk. These are also called chained file allocation methods in OS.
Modification 1
The Directory entry will have the following information –
- First memory block address
- Last memory block
Modification 2
The Directory entry will have the following information –
- First memory block address
- Last memory block
- Total blocks required by file
The total block information is used to cross-check if there is any corruption in the system or not.
Modification 3
- First memory block address
The last memory block will not have any pointer, thus indicating the end of the file.
Advantage
- Doesn’t suffer from external fragmentation as the increasing file size can be handled with adding more scatter linked memory
- File size growth is not a problem and can be handled
Disadvantage
- Extra space for a pointer
- Loss of one pointer may lead to whole file corruption
- A large number of disk seeks operations may be required and may slow down access as file blocks are scattered all over the memory
- Direct access is not supported, example: Starting index i, we can’t access kth block by doing (i+k) since it’s not stored in a contiguous manner
Indexed Allocation
In indexed allocation method, all the pointers (pointing to the next block in the Linked list) are gathered together into one location known as Index Block.
- The file-allocation table contains a multi-level index for each file.
- Indirection blocks are introduced each time the total number of blocks “overflows” the previous index allocation.
You get all block locations in one index file. Blocks are stored in the index file in order of access.
Example –
- In the image below the index block is 14 and contains all block addresses of file jeep
- The first block storage is 0 then 4 then 17 in order.
- A negative number denotes index block list being empty. That is the file has not grown large enough to fill more blocks.
This gets resolved in Index allocation method
Highlights
For Linked Allocation the pointers along with the blocks were scattered across the disk and needed to be retrieved in order by visiting each block to access the file
Advantages
- The kth entry of the index-block is a pointer to the kth block of the file.
- All addresses can be found in one index block file
- Doesn’t suffer from external fragmentation
Disadvantages
- Seek time may still be high as memory is scattered all over the disk
- Corruption in index files may lead to loss of file access locations.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment