Directory Implementation in Operating System – Using Linear List & Hash Table

There are many ways to implement a directory in the operating system. Implementation of a directory structure involves a selection of efficient and reliable directory allocation and management algorithm from the available algorithms that enhances the performance of the system. There are mainly two algorithms for implementing directory, by using Linear List and Hash table.

Linear List :

This is the simplest of all directory implementation methods. It is easy to implement, but it takes a lot of time to execute. It simply maintains a sequential list of file names pointing to their corresponding data blocks.

Directory Implementation in Operating System

This kind of implementation requires a filename to be searched before creating a file with that name. Similarly, a delete operation also requires a linear search for the directory and then deallocating the space occupied by the directory. Finally, the corresponding entry is removed from the list.

Instead of deleting the entry we can name the entry as unused with the help of a used-unused bit, or include it into the list of available directory entries. Another method could be to decrement the directory length and transfer the directory entry contents to any free spaces on the disk.

Though this algorithm is simple to implement it has a few disadvantages as well. This method requires a linear search for finding a file before performing any operation. This makes it slow and users would experience this property very frequently. Even if a binary search technique is used instead of linear search, though it improves average search time, it still needs a sorted list of directory entries to search.

Hash Table :

In this technique, a hash table is used with the linear list for storing directory entries. The hash table makes use of a hash function that takes an input value based on the filename and produces an output as a reference to the corresponding directory entry in the linear list.

Therefore, all file operations consume very less time to execute. However necessary arrangements should be made to handle collisions. A collision is a situation where more than one filename is hashed to the same location.

Directory Implementation in Operating System

Disadvantages of this technique are that a hash table is usually of fixed size and the performance of the hash functions is also dependent on the size of the hash table. Therefore, whenever a new file is to be added after all the available free entries have been used. The hash table should be expanded to accommodate the addition of new files and the existing directory entries should be organized in such a way that the new hash function also maps input values to their corresponding directory entries.

A solution to the above problem could be to use a chained-overflow hash table. A chained-overflow hash table consists of a linked list that stores all hashed entries. Now, if more than one filename hashes to the same entry it can be added as another node to the linked list.

Though this algorithm eliminates all the disadvantages of linear list directory implementation, searching directory names can consume some time since it involves traversing the linked list. However, this technique is considered to be more efficient than the linear list directory implementation method.

Leave a Comment