Directory Structure in Operating System
What is a Directory
A Directory is the collection of the correlated files on the disk. In simple words, a directory is like a container which contains file and folder. In a directory, we can store the complete file attributes or some attributes of the file. A directory can be comprised of various files. With the help of the directory, we can maintain the information related to the files.
To take the advantages of various file systems on the different operating systems, we can divide the hard disk into multiple partitions, which are of different sizes. Partitions are known as minidisks or volumes.
There should be at least one directory that must be present in each partition. Through it, we can list all the files of the partition. In the directory for each file, there is a directory entry, which is maintained, and in that directory entry, all the information related to the file is stored.
There are various types of information which are stored in a directory:
- Name: - Name is the name of the directory, which is visible to the user.
- Type: - Type of a directory means what type of directory is present such as single-level directory, two-level directory, tree-structured directory, and Acyclic graph directory.
- Location: - Location is the location of the device where the header of a file is located.
- Size: - Size means number of words/blocks/bytes in the file.
- Position: - Position means the position of the next-read pointer and the next-write pointer.
- Protection: - Protection means access control on the read/write/delete/execute.
- Usage: - Usage means the time of creation, modification, and access, etc.
- Mounting: - Mounting means if the root of a file system is grafted into the existing tree of other file systems.
Operations on Directory
The various types of operations on the directory are:
- List a directory
- Creating: - In this operation, a directory is created. The name of the directory should be unique.
- Deleting: - If there is a file that we don’t need, then we can delete that file from the directory. We can also remove the whole directory if the directory is not required. An empty directory can also be deleted. An empty directory is a directory that only consists of dot and dot-dot.
- Searching: - Searching operation means, for a specific file or another directory, we can search a directory.
- List a directory: - In this operation, we can retrieve all the files list in the directory. And we can also retrieve the content of the directory entry for every file present in the list.
If in the directory, we want to read the list of all files, then first, it should be opened, and afterwards we read the directory, it is a must to close the directory so that the internal tablespace can be free up.
Types of Directory Structure
There are various types of directory structure:
- Single-Level Directory
- Two-Level Directory
- Tree-Structured Directory
- Acyclic Graph Directory
- General-Graph Directory
- Single-Level Directory: - Single-Level Directory is the easiest directory structure. There is only one directory in a single-level directory, and that directory is called a root directory. In a single-level directory, all the files are present in one directory that makes it easy to understand. In this, under the root directory, the user cannot create the subdirectories.
Advantages of Single-Level Directory
The advantages of the single-level directory are:
- The implementation of a single-level directory is so easy.
- In a single-level directory, if all the files have a small size, then due to this, the searching of the files will be easy.
- In a single-Level directory, the operations such as searching, creation, deletion, and updating can be performed.
Disadvantages of Single-Level Directory
The disadvantages of Single-Level Directory are:
- If the size of the directory is large in Single-Level Directory, then the searching will be tough.
- In a single-level directory, we cannot group the similar type of files.
- Another disadvantage of a single-level directory is that there is a possibility of collision because the two files cannot have the same name.
- The task of choosing the unique file name is a little bit complex.
- Two-Level Directory
Two-Level Directory is another type of directory structure. In this, it is possible to create an individual directory for each of the users. There is one master node in the two-level directory that include an individual directory for every user. At the second level of the directory, there is a different directory present for each of the users. Without permission, no user can enter into the other user’s directory.
Characteristics of Two-Level Directory
The characteristics of the two-level directory are:
- In a two-level directory, there may be same file name of different users.
- There is a pathname of each file such as /User-name/directory-name/
- In a two-level directory, we cannot group the files which are having the same name into a single directory for a specific user.
- In a two-level directory, searching is more effective because there is only one user’s list, which is required to be traversed.
Advantages of Two-Level Directory
The advantages of the two-level directory are:
- In the two-level directory, various users have the same file name and also directory name.
- Because of using the user-grouping and pathname, searching of files are quite easy.
Disadvantages of Two-Level Directory
The disadvantages of the two-level directory are:
- In a two-level directory, one user cannot share the file with another user.
- Another disadvantage with the two-level directory is it is not scalable.
- Tree-Structured Directory
A Tree-structured directory is another type of directory structure in which the directory entry may be a sub-directory or a file. The tree-structured directory reduces the limitations of the two-level directory. We can group the same type of files into one directory.
In a tree-structured directory, there is an own directory of each user, and any user is not allowed to enter into the directory of another user. Although the user can read the data of root, the user cannot modify or write it. The system administrator only has full access to the root directory. In this, searching is quite effective and we use the current working concept. We can access the file by using two kinds of paths, either absolute or relative.
Advantages of tree-structured directory
The advantages of the tree-structured directory are:
- The tree-structured directory is very scalable.
- In the tree-structures directory, the chances of collision are less.
- In the tree-structure directory, the searching is quite easy because, in this, we can use both types of paths, which are the absolute path and relative path.
Disadvantages of Tree-Structure Directory
The disadvantages of tree-structure directory are:
- In the tree-structure directory, the files cannot be shared.
- Tree-structure directory is not efficient because, in this, if we want to access a file, then it may go under multiple directories.
- Another disadvantage of the tree-structure directory is that each file does not fit into the hierarchal model. We have to save the files into various directories.
- Acyclic-Graph Directory
In the tree-structure directory, the same files cannot exist in the multiple directories, so sharing the files is the main problem in the tree-structure directory. With the help of the acyclic-graph directory, we can provide the sharing of files. In the acyclic-graph directory, more than one directory can point to a similar file or subdirectory. We can share those files among the two directory entries.
With the help of aliases, and links, we can create this type of directory graph. We may also have a different path for the same file. Links may be of two kinds, which are hard link (physical) and symbolic (logical).
If we delete the files in acyclic graph structures, then
- In the hard link (physical) case, we can remove the actual files only if all the references to the file are deleted.
- In the symbolic link (logical) case, we just delete the file, and there is only a dangling point that is left.
Advantages of Acyclic-Graph Directory
The advantages of the acyclic-graph directory are:
- In the acyclic-graph directory, the sharing of files is possible.
- In the acyclic-graph directory, because of different-different paths, searching is easy.
Disadvantages of Acyclic-Graph Directory
The disadvantages of acyclic-graph directory are:
- If the files are shared through linking, there may be a problem in the case of deleting.
- If we are using softlink, then in this case, if the file is deleted then there is only a dangling pointer which is left.
- If we are using hardlink, in this case, when we delete a file, then we also have to remove all the reference connected with it.
- General-Graph Directory
The General-Graph directory is another vital type of directory structure. In this type of directory, within a directory we can create cycle of the directory where we can derive the various directory with the help of more than one parent directory.
The main issue in the general-graph directory is to calculate the total space or size, taken by the directories and the files.
Advantages of General-Graph directory
The advantages of general-graph directory are:
- The General-Graph directory is more flexible than the other directory structure.
- Cycles are allowed in the general-graph directory.
Disadvantages of General-Graph Directory
The disadvantages of general-graph directory are:
- In general-graph directory, garbage collection is required.
- General-graph directory is more costly, among other directory structures.
There are various types of algorithm which we use for directory implementation. The selection of a suitable algorithm for directory implementation is an essential task because it directly affects system performance.
We can classify the directory implementation algorithm based on the data structure.
Mostly, we use two types of algorithms:
- Linear List
- Hash Table
- Linear List: - The linear list is the most straightforward algorithm which is used for directory implementation. In this algorithm, we keep all the files in a directory like a singly linked list. Every file comprises of a pointer to the data blocks that are allocated to it and the next file in the directory.
Characteristics of Linear List
The characteristics of the linear list are:
2. Hash Table: - There are some disadvantages in singly linked implementation of directories. So, to remove this drawback, we use another method that is called a hash table. In this method, the hash table is used with the linked list.
In a directory, for every file, there is a key-value pair that is generated, and when the key-value pair is generated, then we store it into the hash table. With the help of the hash function on the file name, we can determine the key and key points to the respective file that are stored in a directory.
In a linear list, the task of searching is difficult because, in a linear list, we have to search the entire list, but in hash table approach, there is no requirement of searching the entire list. So, in hash table searching is quite efficient. With the help of the key, we only have to check the entries of the hash table, and when we get the entry, then by using the value, we will fetch the corresponding file.