Directory Structures :

Directory Structures :

Information in a Device Directory

Name

Type

Address

Current length

Maximum length

Date last accessed (for archival)

Date last updated (for dump)

Owner ID (who pays)

Protection information (discuss later)

Operations Performed on Directory

Search for a file

Create a file

Delete a file

List a directory

Rename a file

Traverse the file system

Organize the Directory (Logically) to Obtain

Efficiency – locating a file quickly.

Naming – convenient to users.

  1. Two users can have same name for different files.

  2. The same file can have several different names.

Grouping – logical grouping of files by properties, (e.g., all Java programs, all games, …)

Single-Level Directory

       

A single directory for all users.

Naming problem

Grouping problem

Two-Level Directory

Separate directory for each user.

           

•Path name

•Can have the same file name for different user

•Efficient searching

•No grouping capability

Tree-Structured Directories

           

Efficient searching

Grouping Capability

Current directory (working directory)

 1.cd /spell/mail / prog

 2. type list

 3. Absolute or relative path name

 4. Creating a new file is done in current directory.

 5. Delete a file

rm <file-name>

Creating a new subdirectory is done in current directory.

mkdir <dir-name>

Acyclic-Graph Directories

Have shared subdirectories and files.

          

  

Two different names (aliasing)

If dict deletes list _ dangling pointer.

Solutions:

•  Back pointers, so we can delete all pointers.   

Variable size records a problem.

      1. Back pointers using a daisy chain organization.

      2. Entry-hold-count solution.

General Graph Directory

          

How do we guarantee no cycles?

 1. Allow only links to file not subdirectories.

 2. Garbage collection.

 3. Every time a new link is added use a cycle detection algorithm to determine whether it is  

     OK.