Explain the various Disk Allocation methods? – Part 2

In this article we discuss about the non-contiguous disk allocation methods i.e., the linked allocation and the indexed allocation. 

What is a Linked Allocation?

- In linked allocation a single file might be stored all over the disk and these scattered parts are linked to each other just like a linked list. 

- Few bytes in the memory block are used for storing the address of the following linked block.

- This type of allocation has two major advantages mentioned below:

1. Simplicity and
2. Non – requirement of disk compaction

- Since the nature of the allocation method is non-contiguous, it does not lead to any external fragmentation of the disk space.

- And since all the memory blocks have been linked to each other, a memory block available anywhere in the memory can be used for satisfying the requests made by the processes. 

- Declaring the file size for the linked allocation is not required during its creation. 

- There are no issues even if the file continues to grow as long as free blocks are available and since the blocks can always be linked up. 

- As a consequence of all this, the need for disk compaction is eliminated. 

Disadvantages of Linked Allocation

But there are disadvantages of using linked allocation. They are:

Direct access to the disk blocks becomes slow: 

For finding a particular block of the file, the search has to begin at the starting point of the file and the successive pointers have to be followed till the destination block is reached.

Space required by the pointers: 

- Suppose out of 512 words of a memory block, 2 are required for storing the pointers, then we have 39 percent of the total disk being used by the pointers rather than for data. 

- This adds to the space requirement of the file blocks.

Reliability: 

- Because of all the blocks being linked via the pointers, even if one pointer gets damaged or wrong, the successive blocks can become inaccessible. 

- This problem is quite common and thus most of the operating systems avoid this problem by keeping redundant copies of these pointers in a special file. 

- The basic idea here is to keep the list of the pointers in the physical memory of the system. 

- This also allows for the faster access to the disk blocks.

What is Indexed allocation?

- The linked allocation method does not provide support for the direct access and this problem is solved by the indexed allocation method. 

- In this method, all the pointers are placed over an index. 

- Thus, these pointers together form the index block. 

- The address of this address block is then stored in the directory. 

- The pointer at the nth number in the index block points to the nth block of the associated file. 

- The purpose of the index blocks is somewhat similar to that of the page map tables; however both of these are implemented in a different way.
- First level index is used for searching the index of second level and the second one is used for searching the third one and the process may continue till the fourth level. 

- But in most of the cases the indexes of the first two levels are sufficient. 

- With this method, second level index blocks (128 x 128) can be easily addressed and files of size of up to 8mb can be supported. 

- Assuming the same thing, files of size up to 1 gb can be addressed.

Advantages and Disadvantage of Indexed Allocation

- The major advantage of this allocation technique is that it does not give rise to external fragmentation and offers a high level of efficiency in random accessing. 

- Also, using this technique mapping can be done around the disk blocks that are known to be bad. 

-Bit mapping can be used for indexing the free space. 

The biggest disadvantage of this allocation technique is the large number disk accesses required for the retrieval of the address of the destination block in the memory.