Directory Structures & File Allocation Methods (Contiguous, Linked, Indexed)

1. Directory Structure in Operating Systems

A modern computer hard disk stores ratusan of thousands of files. To organize these files cleanly, the OS uses Directories (Folders).

• What is a Directory? A Directory can be viewed as a Symbol Table that translates human-readable file names into their corresponding directory entries (file metadata and disk locations).

Your DAVV Unit 5 syllabus lists 5 types of Directory Structures:

1. Single-Level Directory

• Structure: The simplest directory structure. All files are contained in the exact same single directory, regardless of how many users or files exist.
• Drawback (Naming Problem & Grouping Problem): Since all files are in one folder, no two files can have the same name (if User A creates test.c, User B cannot create a file named test.c!), and users cannot group their files by topic.

2. Two-Level Directory

• Structure: Solves the naming collision between different users by creating a separate directory for each user!
  • At the top sits the MFD (Master File Directory), indexed by Username/Account Number.
  • Each MFD entry points to that user’s private UFD (User File Directory).
• Benefit: Two different users can now both have a file named notes.txt (User1/notes.txt and User2/notes.txt).
• Drawback: A user still cannot create subfolders inside their own UFD to organize their projects.

3. Tree-Structured Directory (Used in Windows/Linux!)

• Structure: Extends the two-level directory into a Tree of arbitrary height! Starting from the Root Directory (/ or C:\), users can create their own Subdirectories (folders inside folders) to organize files logically by subject or project.
• Path Names: Supports Absolute Path (starting from Root, e.g., C:\BCA\Sem6\os.pdf) and Relative Path (starting from Current Working Directory).
• Drawback: Pure trees do not allow sharing of files or folders between two parent directories.

4. Acyclic-Graph Directory

• Structure: A generalization of the Tree-Structured Directory that allows directories to share subdirectories and files! The exact same file or folder can appear in two different places at once using a Shared Link (Symbolic Link or Hard Link), provided there are NO cycles (loops) in the graph.
• Benefit: Perfect for team projects where two programmers need direct access to the same shared project folder.

5. General Graph Directory

• Structure: When links are added freely to an existing tree-structured directory, Cycles (closed loops) can accidentally form, turning it into a General Graph Directory.
• Drawback: Needs Cycle-Detection algorithms (so a file-search program doesn’t get trapped in an infinite loop!) and Garbage Collection to know when a file can be safely deleted.

2. File Allocation Methods (How Files Are Stored on Disk Blocks)

A hard disk is divided into thousands of equal-sized physical Disk Blocks (Block 0, Block 1, Block 2...). When you save a file that needs several disk blocks, how does the OS allocate disk blocks to that file?

There are 3 major Disk File Allocation Methods (this is one of the most frequently asked 8-mark questions in Unit 5!):

Method 1: Contiguous Allocation

• How It Works: Each file occupies a set of contiguous (adjacent) blocks on the disk. If a file is 4 blocks long and starts at Block 10, it will occupy Blocks 10, 11, 12, and 13.
• Directory Entry Stores Only 2 Numbers:
  1. Starting Block Address (Start = 10)
  2. Length in Blocks (Length = 4)
• Advantages:
  • Fastest performance! Minimal disk head movement (seek time) because all blocks are right next to each other.
  • Supports both Sequential and Direct (Random) Access effortlessly (to read the k-th block of a file starting at b, immediately go to disk block b + k!).
• Disadvantages:
  • Suffers severely from External Fragmentation on the disk (requires disk defragmentation/compaction).
  • File Growth Problem: It is hard to know how big a file will grow when creating it; if the adjacent block is already occupied by another file, the file cannot grow in place!

Method 2: Linked Allocation

• How It Works: Solves all problems of Contiguous Allocation! A file is stored as a Linked List of scattered disk blocks. The blocks may be scattered anywhere on the disk!
• Directory Entry Stores: A pointer to the First Block (Start) and the Last Block (End) of the file.
• Each disk block reserves a few bytes at the end as a Pointer to the Next Disk Block (e.g., Block 9 → Block 16 → Block 1 → Block 10 [EOF = -1]).
• Advantages:
  • Zero External Fragmentation! Any free block on the disk can be used.
  • Files can grow dynamically as long as a single free block exists on the disk.
• Disadvantages:
  • Does NOT support efficient Direct (Random) Access! To reach the 50-th block of a file, the disk head must slowly read and follow pointers through blocks 1, 2, 3 … 49 sequentially!
  • Pointer Overhead & Reliability Risk: Pointers waste space inside every block, and if even ONE pointer gets corrupted, the entire remainder of the file is lost! (Note: MS-DOS FAT — File Allocation Table improves this by storing all block links in one separate table at the start of the disk).

Method 3: Indexed Allocation

• How It Works: Combines the best of both worlds (supports Direct Access without External Fragmentation)!
• Instead of scattering pointers across every block like Linked Allocation, Indexed Allocation brings ALL the pointers of a file together into one single location called the file’s Index Block (or Inode in UNIX/Linux)!
• Directory Entry Stores: Only the address of the Index Block (e.g., Index Block = 19).
• Inside Block 19 (the Index Block) is an ordered array of disk block numbers ([9, 16, 1, 10, 25]). The i-th entry in the Index Block points directly to the i-th data block of the file!

• Advantages of Indexed Allocation:
  • Supports fast Direct (Random) Access!
  • Zero External Fragmentation (data blocks can be placed anywhere on disk).
• Disadvantage: For a tiny 1-block file, dedicating an entire extra Index Block wastes pointer space.

3. Master Comparison: Contiguous vs Linked vs Indexed Allocation

💡 Exam Preparation Tips for DAVV BCA

• Always draw the 3-column comparison table (Contiguous vs Linked vs Indexed Allocation) above—this question appears in almost every DAVV BCA OS paper!
• For Directory Structures, draw small node hierarchies for Single-Level, Two-Level (MFD → UFD), and Tree-Structured directories.