Core CS

Directory Structures

Directory structures in operating systems organize how files are stored, retrieved, and managed on disk.

<h3>1. Single-Level Directory</h3><h2>A Single-Level Directory is the simplest directory design where a single master directory hosts all files created by all users.<ul><li>Key Points:<ul><li>Only one directory exists in the entire file system.</li><li>Every file must have a globally unique name across the system.</li><li>Files sit alongside each other with no subdirectories.</li></ul></li><li>Significance: It was the foundational model used in early single-user operating systems (such as early CP/M or simple microcomputer systems) where storage capacity and file counts were minimal.</li><li>Advantages:<ul><li>Extremely simple to design, implement, and maintain.</li><li>File searching is fast when the total number of files is small.</li><li>Minimal metadata overhead required by the OS.</li></ul></li><li>Disadvantages:<ul><li>Name collisions: Two users cannot create a file with the same name (e.g., <code data-path-to-node="4,3,1,0,0" data-index-in-node="74">test.txt</code>).</li><li>No grouping: Difficult to organize related files by project, type, or user.</li><li>Lack of privacy: Not scalable or suitable for multi-user systems.</li></ul></li></ul></h2><h3>2. Tree-Structured Directory</h3><h2>A Tree-Structured Directory organizes files and folders hierarchically, starting from a single root directory and branching into subdirectories, forming an inverted tree.<ul><li>Key Points:<ul><li>Has a root directory (<code data-path-to-node="8,0,1,0,0" data-index-in-node="22">/</code> or <code data-path-to-node="8,0,1,0,0" data-index-in-node="27">C:\</code>) containing files and subdirectories.</li><li>Each file or directory has exactly one parent directory.</li><li>Files can be referenced via absolute paths (from root) or relative paths (from current working directory).</li></ul></li><li>Significance: It is the standard directory model adopted by modern desktop and server OS file systems (like Linux, Windows, and macOS) to support multi-user isolation and project-based grouping.</li><li>Advantages:<ul><li>No naming collisions: Files in different directories can share the same name (e.g., <code data-path-to-node="8,2,1,0,0" data-index-in-node="84">/user1/doc.txt</code> and <code data-path-to-node="8,2,1,0,0" data-index-in-node="103">/user2/doc.txt</code>).</li><li>Logical organization: Users can nest subdirectories to categorize files systematically.</li><li>Easy access control: Permissions can be applied at directory boundaries and inherited down the tree.</li></ul></li><li>Disadvantages:<ul><li>No direct sharing: A file cannot naturally exist simultaneously in two different folders without duplicating the data.</li><li>Traversal overhead: Accessing deeply nested files requires traversing multiple directory blocks, increasing disk I/O.</li></ul></li></ul></h2><h3>3. Acyclic-Graph Directory</h3><h2>An Acyclic-Graph Directory extends the tree structure by allowing directories or files to be shared among different directories via links (aliases/shortcuts), strictly prohibiting closed loops or cycles.<ul><li>Key Points:<ul><li>A file or folder can have multiple parents (indegree > 1).</li><li>Direct file sharing is supported without copying the underlying data blocks.</li><li>Directed graphs are maintained such that no path leads back to the originating directory.</li></ul></li><li>Significance: It provides a native mechanism for collaboration and joint project work in multi-user systems (e.g., UNIX hard links and symbolic links) while preventing traversal deadlock.</li><li>Advantages:<ul><li>True file sharing: Changes made to a shared file by one user are immediately visible to others.</li><li>Storage efficiency: Saves disk space by referencing the same physical blocks rather than creating redundant copies.</li><li>Flexible workflows: Allows shared libraries or source code to reside in multiple user environments seamlessly.</li></ul></li><li>Disadvantages:<ul><li>Dangling pointers: Deleting a file from one path can leave broken links in other paths unless reference counters are maintained.</li><li>Complex deletion logic: If reference counts are used, the physical file is deleted only when the count reaches zero.</li><li>Cycle prevention overhead: The OS must run cycle-checking algorithms every time a new link is created.</li></ul></li></ul></h2><h3>4. General Graph Directory</h3><h2>A General Graph Directory allows arbitrary links between directories and files, including cycles (a path of links can loop back to an ancestor directory).<ul><li>Key Points:<ul><li>Cycles and loops are permitted in the directory graph.</li><li>A directory can be an ancestor and a descendant of another directory simultaneously.</li><li>Requires explicit cycle detection algorithms during search and traversal.</li></ul></li><li>Significance: Arises when an OS allows soft links/shortcuts to arbitrary directories without restricting cycle formation, prioritizing link flexibility over strict structural rules.</li><li>Advantages:<ul><li>Maximum flexibility: Complete freedom to link files and directories without graph topology restrictions.</li><li>Simple link creation: The file system does not need to validate every new link for cycle creation at link time.</li></ul></li><li>Disadvantages:<ul><li>Infinite loop risk: Search, backup, or disk-usage tools can loop infinitely unless they track visited nodes.</li><li>Garbage collection overhead: Standard reference counting fails when cycles occur (isolated loops have non-zero counts but are unreachable), requiring expensive mark-and-sweep garbage collection.</li><li>Complex file management: Determining true file size, total directory contents, or safe deletion requires complex operating system logic.</li></ul></li></ul></h2>