Directory

Definition:

• Requirements:
  • Efficiency – locating a file quickly
  • Naming – convenient to users
    • Two users can have same name for different files
    • The same file can have several different names
  • Grouping – logical grouping of files by properties, (e.g., Java programs, games, …)

Directory structure

• Single-level directory: A single directory for all users
  • Problems:
    • Privacy
    • Cant share file
    • unorganized
• Two-level directory: separate directory for each user, each directory has multiple directories
  • Problems:
    • Privacy
    • Cant share file
• Tree-structured directory (hierarchical directory): directories can contain both files and other directories
  • Problems:
    • Privacy
    • Long path to file/dir
    • Difficult to share files across different directories
• Acyclic-Graph Directory: more flexible than in tree, a folder can link to another file/folder which is in another location
  • Problems:
    • two linked files having the same name
    • Dangling pointer: A file/folder links to a deleted file/folder
    • Cant link backward
  • Solution:
    • Backpointer: when linked file/folder is deleted, it looks back to the org pointing file/folder to remove pointer
    • Symbolic Link, soft link
• General graph directory: allow arbitrary (link backward)
  • How to have no cycles?
    • allow links to files that are not subdir
    • Garbage collection
    • Run cycle detection algorithm when new link is added

Directory implementation

• How to know which Files are in a directory
• Linear list: store list of names with pointer to the data blocks
  • simple
  • takes long time to search
• Hash table: hash the file to where it belong
  • 2 different files have same hash → both appear in eachother dir
  • Only good if entries are fixed size, or use chained-overflow method