Logical Structure of a directory – File Management

Logical Structure of a directory

Logical Structure of a directory: The directories can be structured in the following ways:

1. Single level directory
2. Two level directory
3. Tree structure directory
4. Acyclic graph directory
5. General graph directory

1. Single Level directory

It is the simplest form of Logical Structure of a directory having only one level of directories. All the files are contained in the same directory. Therefore these files should have unique name i.e., no two users can have same file name as the files of all the users are stored in same directory. Such a directory appears as the list of files or a sequential file having file name serving as the key. This kind of directory structure is implemented in earlier single user system. It has become outdated and does not support multi-user system.

Advantage of Single Level Directory

1. It is simple, easy to support and understand.

Disadvantages of Single Level Directory

1. It requires unique file names so no two users can have a file with same name..
2. It does not provide a method for organizing the files by its type i.e., files of different types such as graphic file, text file and executable files cannot be organized separately.

 2. Two-Level Directory

This kind of directory structure supports two levels of directories i.e., a master file directory (MFD) and user file directories (UFD) as sub-directories of master directory. In this system, a separate directory is provided to each user and all the user file directories are contained and indexed in master file directory.

All the user file directories (UFD) has similar structure and contains list of files of that user. Thus in two level directory structure different users have different directories containing their own files only. This allows different users to have files with same names. However the file names need to be unique in the user’s own directory as two file names cannot be same in one single directory. In this system, the combination of user name and file name serves as pathname for a file. Thus, when a user refers to a particular file, his own user file directory (UFD) is searched.

Two level structure looks like an inverted tree of height 2. Root of this tree is the master file directory having user directories as its branches. Files as the leaves of these branches. To create or delete a file, operating system searches only user’s directory that initiates the command.

Thus, it cannot accidentally delete another user’s file that has the same name. Operating system uses a special system program or system calls, to create or delete a user directory entry from the master directory. One user can access a file of another user by specifying the complete path name of file of another user. For example, if user A wants to access file named “hello” of user B, then user A must specify the path as /userb/hello.

Advantages of two-level directory

1. The files of different users are separated from each other as each user has its own directory.
2. It solves the problem of name-collision as observed in single level directory. Two users can have a file with same name in their own directories.
3. Search operation for files is efficient as compared to single level directory structure. In this scheme, if a user wants to search a particular file, his own directory is searched.

Disadvantages of two-level directory

1. As files of different users are separated, this scheme restricts cooperation among different users. Some systems do not allow local user files to be accessed by other users.
2. This structure also does not provide any help in grouping files of different types.
3. It is not possible to create subdirectories within directories.

3. Tree Structure Directory; Logical Structure of a directory

It is the most common, powerful and flexible structure implemented in almost every operating system. It is just the extension of two level directory structure. Here, the tree is of arbitrary height instead of 2. It uses the same concept of two level directory structure of master file directory having user file directories as subdirectories. The major difference here is that each user file directory can in turn have subdirectories. Thus each user directory can have files or further subdirectories as branches and leaves.

The various users can create their own subdirectories to organize the files different types , such as a separate subdirectory for graphics files, text files etc. Special system calls are used to create or delete directories. Internal format, i.e., the internal structure (in which the details of directory are stored) of each directory has an entry that stores a special bit representing a subdirectory or a file i.e., 0 bit represents a file and 1 bit represent a directory. User always works on the file in the current directory.

Current directory holds all the files, which a user currently requires. Whenever a reference made to a particular file, the operating system searches the current directory. If the required file is not present in current directory, then the user must either specify a path name or change the current directory to be the directory holding that file. In order to change the directory, a system call can be used that takes a directory name as a parameter. In tree structure, files can be referred in two ways : 

(a) absolute pathname

(b) relative pathname

Absolute path name starts from the root directory and ends at the required file following a path of directories and subdirectories. For example, the path c://windows/programs/arkay.exe represents the absolute path. It means that root directory contains subdirectory ‘windows‘ which further contains a subdirectory programs’, that contains an executable file ‘arkay. exe’. Relative Pathname starts from the current directory or the working directory to the file For example, if a current working directory is ‘/user/curr‘ then the file whose absolute path is ‘/user/curr/Arkay can be referred simply as ‘Arkay’. User can access another user’s file by giving its path name.

In tree structure directory path name to a file can be longer than in two level directory. This increases the search time for a file that resides in other user directory.

Advantages of tree structure directory

1. The files of different users separated from each other. Thus allowing different users to have files with same name.
2. It provides efficient searching capabilities by specifying either absolute path or relative path.
3. It enables the users to group similar kind of files in one subdirectory. Thus providing grouping of files of similar kind.

Disadvantage of tree structure directory

1. The files or directories of different users cannot be shared.

4. Acyclic Graph Directory

In this Logical Structure of directory it allows different user directories to organize within master file directory just like tree structure. The additional feature provided by acyclic group is that the subdirectories or files of different users can share. A shared directory or file will exist in the file system in two or more places simultaneously. In such a case, shared file or directory does not mean that two copies of that file or directory exist.

With shared file, only one actual file exits, so a change made by one user immediately visible to other. In case of shared sub directories, a new file created by one user automatically appear n all the shared subdirectories. In acyclic graph directory, because of sharing, a file may have multiple absolute path names. As a result distinct file names may refer to the same file.

Advantage of acyclic graph directory

1. It is simple and easy to traverse the graph in order to find a particular file.

Disadvantage of acyclic graph directory

1. As there are no cycles, shared sections (files & directories) are traversed twice. This leads to the wastage of time.

5. General Graph Directory; Logical Structure of a directory

This Logical Structure of a directory is formed by adding links into an existing tree structure. The general graph directory overcomes the problem of acyclic graph by allowing the cycles in a directory. Thus it helps in avoiding the searching of a component twice in a subdirectory. As a result performance of a system improved. If we use a poor algorithm, then it leads in an infinite loop, which continuously searches through the cycle and this loop never comes to an end.

In order to solve this problem, we have to limit the number of directories that can be accessed during searching. If we want to know when a file can be deleted, then the same problem of looping comes into existence. In acyclic directories we can find when the file can be deleted. In these directories there is a 0 value of reference count which indicates that the file can be deleted.

But in case of general graph, as cycles exists, the value of reference count may not be 0. In this case, we need to use a scheme called garbage collection. It helps us in determining when the last reference has deleted and that space can be used for reallocation.

Garbage collection involves traversing the entire file system marking everything that accessed. Then, a second pass collects everything that is not marked into a list of space. However, garbage collection is time consuming for a disk based file and is rarely used.