Assignment 08: File Systems: Allocation and Organization

I. Objective & Theoretical Framework

A file is a logical entity that divides data into meaningful groups, but as a physical entity, it must be carefully organized and allocated on a storage disk. The term “file organization” refers to the way data is stored and the methods by which it can be accessed.

In this laboratory, you will simulate two critical aspects of file system design:

1. File Allocation Strategies:

Sequential Allocation: Records of the file are stored one after another both physically and logically. A record can only be accessed by reading all previous records.
Linked Allocation: Each file is a linked list of disk blocks that may be scattered anywhere on the disk. The directory contains a pointer to the first and last blocks, and each block contains a pointer to the next block.
Indexed Allocation: Brings all the pointers together into one location called an index block. Each file has its own index block (an array of disk-block addresses), and the directory contains the address of this index block.

2. Directory Organization Techniques:

Single-Level Directory: All files are placed in one root directory. It is simple but suffers from name collision problems.
Two-Level Directory: Each user has their own User File Directory (UFD), and the system maintains a Master File Directory (MFD). This isolates users from one another and solves name collisions.
Hierarchical (Tree) Directory: Allows users to create their own subdirectories to organize files, where every file has a unique path name.

II. Prerequisite Knowledge & Resources

C Structs and Pointers: You will rely heavily on struct arrays to simulate directories and struct pointers to simulate Linked Allocation and Hierarchical Trees.
String Manipulation: <string.h> is required. You will frequently use strcmp() to search for file names within your simulated directories.

III. Starter Code & Partial Implementations

The following skeleton code provides a clean data structure for simulating Sequential File Allocation. You can expand upon this basic array-of-structures model to handle Two-Level directories.

#include <stdio.h>
#include <string.h>

// Structure to simulate a file entry in a directory table
struct fileTable {
    char name[20];
    int start_block; // Used for Sequential Allocation
    int num_blocks;  // Length of the file in blocks
} ft[30];

int main() {
    int i, j, n;
    char search_name[20];

    printf("Enter number of files to allocate: ");
    scanf("%d", &n);

    for(i = 0; i < n; i++) {
        printf("\nEnter file %d name: ", i + 1);
        scanf("%s", ft[i].name);
        printf("Enter starting block of file %d: ", i + 1);
        scanf("%d", &ft[i].start_block);
        printf("Enter number of blocks in file %d: ", i + 1);
        scanf("%d", &ft[i].num_blocks);
    }

    printf("\nEnter the file name to be searched: ");
    scanf("%s", search_name);

    // [Insert Linear Search Logic using strcmp() here]

    // [Insert Output Logic: Print File Name, Start Block, and all occupied blocks]

    return 0;
}

IV. Step-by-Step Task List

Allocation Simulation: Complete the starter code to simulate Sequential Allocation. Next, create separate C programs to simulate Linked and Indexed allocation. For Linked Allocation, use a struct containing a block number and a next pointer. For Indexed Allocation, use an array within your file table struct to store the specific blocks.
Single & Two-Level Directories: Write a program with a switch menu to simulate a Single-Level Directory allowing users to Create, Delete, and Search for files. Expand this into a new program for a Two-Level Directory by upgrading your struct to include an array of directories, each containing its own array of files.
Hierarchical Directory Structure: Simulate a Tree directory structure. Create a node struct that contains a character array for the name, a flag indicating if it is a file or a directory, and an array of pointers linking to its children (subdirectories or files).

V. Common Pitfalls & Debugging Strategies

The graphics.h Trap: Older laboratory manuals often use #include <graphics.h> to visually draw the hierarchical tree on the screen. This library is deprecated and does not exist in modern Linux GCC compilers. Do not attempt to use initgraph() or circle(); instead, focus purely on the backend logic and print the tree output using standard text indentation.
String Comparison: A common C programming error is attempting to compare file names using if (search_name == ft[i].name). This compares memory addresses, not the strings themselves. You must use if (strcmp(search_name, ft[i].name) == 0).
Dangling Pointers in Linked Allocation: When simulating Linked Allocation, ensure every file’s final block pointer is explicitly set to NULL to prevent infinite loops when printing the allocated blocks.
Dangling Pointers & Segfaults: When implementing Linked Allocation, if your final block pointer is uninitialized rather than explicitly set to NULL, traversing the file will result in a Segmentation Fault. If your program crashes, do not rely on printf. Compile with the -g flag (gcc -g file.c) and use gdb ./a.out or valgrind ./a.out to trace the exact memory address where the pointer derailed.

VI. Real-World Case Study

These exact allocation strategies form the backbone of the file systems you use daily. The FAT32 file system (commonly used on USB flash drives) is a highly optimized version of Linked Allocation, utilizing a File Allocation Table to link clusters together. The ext4 file system (the default for most Linux distributions) and NTFS (Windows) utilize highly advanced versions of Indexed Allocation using structures called “inodes” and “Master File Tables” respectively, combined with hierarchical B-Trees to ensure extremely fast file retrieval even with millions of stored files.

VII. Advanced Variant Tasks

Recursive Directory Search: In your Hierarchical Directory simulation, write a recursive C function that behaves like the Linux find command. It should accept a file name as a parameter, traverse the entire directory tree using Depth-First Search (DFS), and print the exact absolute path (e.g., /ROOT/USER1/SUBDIR/file.txt) if the file is found.
File System Defragmenter: Write a compaction engine. Provide your program with an array representing a heavily fragmented disk map resulting from simulated file creations and deletions. Write logic to shift all active data blocks to the beginning of the disk, consolidate all FREE blocks at the end, and update the master directory pointers accordingly.

VIII. Resources & Further Reading

OSTEP - Files and Directories: Read Chapter 39: Files and Directories (PDF) for the UNIX file system API.
OSTEP - File System Implementation: Read Chapter 40: File System Implementation (PDF). This perfectly visualizes contiguous vs. linked vs. indexed (inode) allocation strategies.
The Linux VFS: Review the Kernel.org VFS Documentation to understand how Linux unifies various file systems (ext4, FAT32) under a single hierarchical tree architecture.