Course contentsShow
← Computer Science
Lesson 1420 of 2,87232. File SystemsFree lesson

General Graph Directories and Cycle Issues

Understanding how unrestricted linking creates cycles and the garbage collection challenges they introduce.

General Graph Directories and Cycle Issues

What you'll learn: How unrestricted linking in file systems can create cycles and why they pose serious garbage collection challenges.

Why Cycles Are a Problem

In the acyclic graph directories you just learned about, we carefully avoided cycles—paths that loop back to themselves. But what if we allow any link anywhere? We get a general graph directory structure where directories can form cycles.

Imagine this: Directory A contains a link to Directory B, which contains a link to Directory C, which contains a link back to Directory A. You've created a loop. Now try traversing from A to find all files—you could walk forever: A → B → C → A → B → C...

The Real Danger: Garbage Collection

The bigger issue isn't infinite traversal (we can mark visited directories). It's garbage collection—reclaiming space from deleted files and directories.

Analogy: Think of a chain of people holding hands in a circle. If everyone lets go except for two people still holding each other's hands, they form an isolated island. From the outside, you can't reach them, but they still occupy space. In file systems, this is a self-contained cycle with no external references.

Normal reference counting fails here. If you delete the last external pointer to our A-B-C cycle, all three directories still have non-zero reference counts (they reference each other), so they won't be freed—even though they're unreachable garbage.

Solutions

File systems typically handle this by:

  • Prohibiting cycles entirely (stay acyclic)
  • Using garbage collection algorithms that detect unreachable cycles (expensive)
  • Allowing only symbolic links to create potential cycles (they don't affect reference counts)

Key Takeaway: General graph directories with unrestricted hard links can create cycles that break simple reference counting, requiring expensive cycle-detection algorithms or design restrictions to prevent orphaned, unreachable storage.