Examine how operating systems structure, search, and protect the file system namespace: single-level directories, two-level Master/User architectures, recursive tree hierarchies, structural self/parent links, path resolution, and hard versus symbolic links.
1. Single-Level Directory Systems
To track files stored on secondary storage media, the operating system maintains a mapping between human-readable file names and physical storage locations. The simplest design is a single-level directory system (a flat directory structure).
Architectural Characteristics
Unified Global Namespace: A single directory contains every file present on the entire storage volume. There are no subdirectories or partitions by user account.
Global Name Uniqueness: Every file must have a globally unique identifier. If Alice creates assignment.c, Bob cannot create assignment.c on that disk volume.
Direct Linear Mapping: The directory entry directly pairs each file name with its file attributes and disk allocation addresses (or a pointer to a metadata block).
Practical Applications & Limitations
Single-level directory systems appeared in early mainframe operating systems and first-generation personal microcomputers, such as early CP/M and original MS-DOS 1.0 on 160 KB / 360 KB 5.25-inch diskettes. With only dozens of files per disk, flat tables were computationally inexpensive.
Name Collisions: In multi-user systems, coordinate naming breaks down, forcing artificial prefixes like alice_prog.c and bob_prog.c.
Project Segmentation Failure: Even for a single user, storing thousands of source modules, binaries, and data records in a single flat list makes cataloging difficult.
Linear Search Bottlenecks: Directory lookup requires scanning an increasingly large linear table ($\mathcal{O}(N)$), driving up disk access latency.
Figure 4-1: Single-Level Flat Directory Layout
2. Two-Level Directory Systems
The shift to multi-user time-sharing architectures (such as MIT's CTSS and DEC TOPS-10) demanded isolated namespaces. Operating systems introduced a fixed two-tier hierarchy:
Master File Directory (MFD): The root-level administrative table containing one entry per user account or project group. It contains account metadata and pointers to individual user directory tables.
User File Directory (UFD): An isolated directory table created for each user, mapping their private file names to inode/FCB metadata. Alice and Bob can each create main.c without conflict.
Figure 4-2A: Two-Level Directory Structural Topology (MFD to UFD)
The System Utility & Fallback Search Dilemma
While account segregation prevents conflicts, duplicating common executables (cc, ed, as) across every user's UFD exhausts storage. Systems introduced a dedicated system directory and a Two-Stage Fallback Search Rule:
Two-Stage Search Rule:
$$ \text{SearchTarget} = \begin{cases}
\text{Step 1:} & \text{Search Active Caller UFD} \\
\text{Step 2:} & \text{If not found } \longrightarrow \text{Search SYSTEM UFD} \\
\text{Step 3:} & \text{If not found } \longrightarrow \text{Return Error (ENOENT)}
\end{cases} $$
3. Hierarchical (Tree-Structured) Directory Systems
Pioneered by Multics and UNIX, the generalization from two tiers to arbitrary depth is straightforward: allow directory entries to point to other directories as well as regular files.
Directories as Specialized Files
Readable Like Data Files: Directories are linear arrays of entry records. In POSIX, access is wrapped via standard functions (opendir(), readdir(), closedir()) to decouple applications from on-disk data structures (e.g., ext4 directory hashes, B-trees).
Kernel-Guarded Writes: User processes are strictly prohibited from writing directly to directories via write(). Only the kernel may modify directory bytes during system calls (creat, mkdir, link, unlink).
Self and Parent Links: . and ..
Every directory created in a hierarchical file system is initialized with two structural entries:
. (Current Directory / Self): Points directly to the directory's own metadata node (inode / FCB).
.. (Parent Directory): Points directly to the metadata node of the parent directory.
Traversing above the root cycles back to the root, preventing file system traversal escapes.
Path Name Classification
Path Class
Starting Anchor
Syntax Signature
Example
Resolution Mechanics
Absolute Path
Root directory (/ or C:\)
Leading slash or drive specifier
/home/alice/src/main.c
MMU/VFS begins traversal unconditionally at the root inode.
Relative Path
Current Working Directory (CWD)
No leading slash
src/main.c or ../bob/notes.txt
Traversal begins from the CWD inode recorded in the process PCB.
Hierarchical Tree & Path Resolution SandboxTanenbaum §4.2.3
On-Disk Table for: /
Name
Type
i-node
Notes
$ session started. Active working directory set to /
/ $
Quick Jumps:
4. Directory System Calls & Link Mechanics
mkdir() & rmdir():mkdir allocates an inode and automatically populates . and ... rmdir enforces an emptiness invariant: deletion is denied with ENOTEMPTY unless the directory contains exclusively . and ...
Hard Links (link): Creates an additional directory entry pointing to an existing inode. The target inode's nlink reference count increments. Both names have identical status.
Symbolic Links: Creates a separate file with type S_IFLNK containing a target path string. If the target is deleted, the symlink dangles.
Unlink Mechanics (unlink): Removes a directory entry and decrements nlink. Physical blocks are reclaimed only when nlink == 0 and all open file descriptors to that inode are closed.