1. Why Tree Structure is Not Enough

The Tree-Structured Directory solved many of the problems present in Single-Level and Two-Level Directory Structures. It introduced:

• Hierarchical organization

• Subdirectories

• Better scalability

• Efficient searching

However, it still suffers from one major limitation:

A File Can Exist in Only One Location

Consider the following tree structure:

/home/UserA/project.txt

Suppose UserB also needs access to the same file.

Option 1: Copy the File

/home/UserA/project.txt

/home/UserB/project.txt

Although this appears simple, it introduces serious issues.

Problem 1: Data Duplication

The same file is stored twice.

project.txt
     ↓
Copy 1

project.txt
     ↓
Copy 2

Result:

• Extra disk space consumed

• Increased storage requirements

Problem 2: Inconsistency

Suppose UserA modifies the original file.

UserA version → Updated

UserB version → Old

Now two different versions exist.

Problem 3: Maintenance Overhead

Whenever the file changes:

• All copies must be updated

• Synchronization becomes difficult

Requirement

Modern systems need:

• File sharing

• Storage efficiency

• Consistency

without creating duplicate copies.

Solution

Allow multiple directory entries to refer to the same file.

This leads to the Acyclic Graph Directory Structure.

Key Insight

Instead of copying data, share references to the same file.

2. What is an Acyclic Graph Directory?

An Acyclic Graph Directory is a directory structure that allows files and directories to be shared by multiple users through links while ensuring that no cycles are formed.

Definition

An Acyclic Graph Directory is a directory organization scheme in which files or directories may have multiple parent directories, creating a graph structure that does not contain any cycles.

Key Idea

Multiple Paths
        ↓
Same File

Unlike a tree:

One Parent
     ↓
One Child

an acyclic graph allows:

Multiple Parents
        ↓
     Same Child

Example

UserA
   │
   └── project.txt

UserB
   │
   └── project.txt

Both directory entries refer to:

Same Physical File

Core Insight

The file exists only once on disk but can be accessed through multiple directory paths.

3. Structure of an Acyclic Graph

Tree Structure

In a tree:

Root
│
├── A
│
└── B

Every node has exactly one parent.

Graph Structure

In an acyclic graph:

      Root
      /  \
     /    \
    A      B
     \    /
      \  /
   project.txt

Here:

project.txt

has two parents:

• A

• B

Important Observation

The file is stored only once.

Both paths lead to the same file.

Example

/home/UserA/project.txt

/home/UserB/project.txt

Both names point to identical underlying data.

Key Insight

Logical duplication exists.

Physical duplication does not.

4. Visualization of Acyclic Graph Directory

Tree Structure

Root
│
├── UserA
│   └── project.txt
│
└── UserB

UserB cannot directly access the file.

Acyclic Graph Structure

Root
│
├── UserA
│   │
│   └─────┐
│         │
│         ▼
│     project.txt
│         ▲
│         │
└── UserB┘

Another Representation

UserA
   │
   ├── Notes
   │
   └── Shared_Project
             ▲
             │
             ▼
UserB
   │
   └── Shared_Project

Both users access the same object.

Key Insight

One physical file can appear in multiple locations.

5. How Sharing is Implemented

This is the most important concept in acyclic graph directories.

The operating system uses links.

What is a Link?

A link is a directory entry that refers to an existing file.

Instead of creating another copy:

Directory Entry
        ↓
      File

The OS creates another reference.

5.1 Hard Links

A Hard Link creates another directory entry pointing to the same inode.

Example

file1.txt → inode 100

file2.txt → inode 100

Both names refer to:

inode 100

Visual Representation

file1.txt
      \
       \
        ▼
      inode 100
        ▲
       /
      /
file2.txt

What Happens Internally?

Directory Entry 1:

file1.txt → inode 100

Directory Entry 2:

file2.txt → inode 100

The inode contains:

• Metadata

• Block pointers

• File size

• Permissions

Important Observation

Only directory entries increase.

Data is not copied.

Advantages

No Additional Storage

One file
One inode
One set of blocks

Immediate Consistency

Editing through one name:

file1.txt

automatically affects:

file2.txt

because both reference the same file.

Key Insight

Hard links share the actual file.

5.2 Symbolic Links (Soft Links)

A Soft Link stores a pathname rather than directly referencing an inode.

Example

link.txt
      ↓
/home/user/file.txt

Visual Representation

link.txt
    │
    ▼
"/home/user/file.txt"
    │
    ▼
Actual File

Important Difference

A symbolic link is essentially a shortcut.

It does not directly point to file data.

Example

Shortcut → Target File

Key Insight

Soft links reference a path.

Hard links reference an inode.

Hard Link vs Soft Link

Example

Original file:

report.txt

Hard Link:

report_copy.txt

If original deleted:

report_copy.txt

still works.

Soft Link:

shortcut.txt

If original deleted:

shortcut.txt

becomes a broken link.

6. Why "Acyclic"?

This is one of the most important theoretical concepts.

What is a Cycle?

A cycle occurs when traversal eventually returns to the starting point.

Example:

A → B → C → A

Visual Representation

A
↓
B
↓
C
↓
A

This creates an infinite loop.

Problems Caused by Cycles

Infinite Traversal

Suppose OS performs:

Recursive Directory Search

Traversal becomes:

A → B → C → A → B → C → ...

and never ends.

Backup Failures

Backup programs may repeatedly copy:

A → B → C → A

forever.

Resource Exhaustion

CPU and memory usage can increase indefinitely.

Solution

Operating systems enforce:

No Cycles Allowed

Thus:

Graph
     ✔

Cyclic Graph
     ✘

Key Insight

The structure is called an Acyclic Graph because cycles are prohibited.

7. Advantages of Acyclic Graph Directory

7.1 File Sharing

Multiple users can access the same file.

Example:

UserA
UserB
UserC

        ↓
 Shared File

Benefit

Collaboration becomes easier.

7.2 No Data Duplication

Only one copy exists.

Benefit

Saves disk space.

7.3 Consistency

Changes are visible everywhere.

Example:

UserA edits file

Immediately:

UserB sees updated version

Benefit

No synchronization problems.

7.4 Efficient Storage

Storage grows slowly even when sharing increases.

Benefit

Better utilization of disk resources.

7.5 Better Collaboration

Useful in:

• Shared projects

• Team environments

• Version control systems

Benefit

Supports cooperative work.

8. Disadvantages

Although powerful, acyclic graphs introduce additional complexity.

8.1 Increased Complexity

The OS must manage:

• Links

• References

• Shared ownership

Result

More complicated implementation.

8.2 Deletion Problem

Suppose:

UserA → file

UserB → file

UserA deletes their entry.

Should the file be deleted?

Problem

UserB still needs it.

Solution

Reference counting.

8.3 Garbage Collection

Broken links may remain.

Example:

shortcut.txt
      ↓
deleted_file.txt

The OS may need cleanup mechanisms.

8.4 More Metadata Management

Tracking multiple references requires additional bookkeeping.

Result

Higher management overhead.

9. Deletion Handling (Very Important)

The most common solution is Reference Counting.

What is Reference Count?

Each file maintains:

Number of Active Links

Example

project.txt

Reference Count = 3

Meaning:

3 directory entries

refer to the same file.

Deleting One Link

Before:

Count = 3

After removing one link:

Count = 2

File remains intact.

Another Deletion

Count = 1

Still exists.

Final Deletion

Count = 0

Now the OS:

• Deletes inode

• Frees disk blocks

• Releases resources

Deletion Flow

Remove Link
      ↓
Decrease Count
      ↓
Count > 0 ?
      ↓
 Yes → Keep File

 No  → Delete File

Key Insight

A shared file exists until all references disappear.

10. Real-World Analogy

Think of a shared document in cloud storage.

Example:

Project_Report.docx

Shared with:

• Alice

• Bob

• Charlie

Each person has a shortcut to the same document.

Alice
   │
   ├──► Document

Bob
   │
   ├──► Document

Charlie
   │
   └──► Document

Important Observation

There is:

One Document

but

Multiple Access Points

Key Insight

This is exactly how an acyclic graph directory works.

11. Comparison with Tree Structure

Final Insight

The Acyclic Graph Directory extends the Tree-Structured Directory by allowing files and directories to be shared through links. Multiple directory entries can reference the same file, eliminating duplication and improving consistency. To avoid infinite traversal and management issues, cycles are prohibited, making the structure an acyclic graph. Modern operating systems implement this concept using hard links, symbolic links, and reference counting mechanisms, enabling efficient file sharing while maintaining file system integrity.