Acyclic-Graph Directories

• The acyclic graph is a natural generalization of the tree-structured directory scheme.
• The common subdirectory should be shared. A shared directory or file will exist in the file system in two (or more) places at once.
• A tree structure prohibits the sharing of files or directories. An acyclic graph (a graph with no cycles) allows directories to share subdirectories and files (see Fig. 14).

  Figure 14: Acyclic-graph directory structure.

  
• The same file or subdirectory may be in two different directories.
• It is important to note that a shared file (or directory) is not the same as two copies of the file.
  • With two copies, each programmer can view the copy rather than the original, but if one programmer changes the file, the changes will not appear in the other's copy.
  • With a shared file, only one actual file exists, so any changes made by one person are immediately visible to the other.
• A common way, exemplified by many of the UNIX systems, is to create a new directory entry called a link.
• A link is effectively a pointer to another file or subdirectory.
• When a reference to a file is made, we search the directory. If the directory entry is marked as a link, then the name of the real file is included in the link information.
• We resolve the link by using that path name to locate the real file. Links are easily identified by their format in the directory entry and are effectively named indirect pointers.
• Another common approach to implementing shared files is simply to duplicate all information about them in both sharing directories. Thus, both entries are identical and equal.
• A link is clearly different from the original directory entry; thus, the two are not equal. A major problem with duplicate directory entries is maintaining consistency when a file is modified.
• Several problems must be considered carefully for an acyclic-graph directory structure.
  • A file may now have multiple absolute path names. Consequently, distinct file names may refer to the same file.
  • Another problem involves deletion. When can the space allocated to a shared file be deallocated and reused?
    • One possibility is to remove the file whenever anyone deletes it, but this action may leave dangling pointers to the now nonexistent file.
    • Worse, if the remaining file pointers contain actual disk addresses, and the space is subsequently reused for other files, these dangling pointers may point into the middle of other files.
• In a system where sharing is implemented by symbolic links, this situation is somewhat easier to handle.
  • The deletion of a link need not affect the original file; only the link is removed.
  • If the file entry itself is deleted, the space for the file is deallocated, leaving the links dangling.
• We can leave the links until an attempt is made to use them. At that time, we can determine that the file of the name given by the link does not exist and can fail to resolve the link name; the access is treated just as with any other illegal file name.
• In the case of UNIX, symbolic links are left when a file is deleted, and it is up to the user to realize that the original file is gone or has been replaced. Microsoft Windows (all flavours) uses the same approach.
• Another approach to deletion is to preserve the file until all references to it are deleted. To implement this approach, we must have some mechanism for determining that the last reference to the file has been deleted. The trouble with this approach is the variable and potentially large size of the file-reference list.
• However, we really do not need to keep the entire list -we need to keep only a count of the number of references.
  • Adding a new link or directory entry increments the reference count;
  • Deleting a link or entry decrements the count.
  • When the count is 0, the file can be deleted; there are no remaining references to it.
• The UNIX OS uses this approach for non-symbolic links (or hard links), keeping a reference count in the file information block (or inode).
• Most OSs that support a hierarchical directory system have two special entries in every directory, ``.'' and ``..'', generally pronounced ``dot'' and ``dotdot''. Dot refers to the current directory; dotdot refers to its parent. To see how these are used, consider the UNIX file tree of Fig. 15.

  Figure 15: A UNIX directory tree.