Session 5.3 – File System Concepts

Understanding file and directory structures, file attributes, and directory implementation

2 Hours Module 5 I/O & File Management

Learning Objectives

By the end of this session, you will be able to:

  • Understand the fundamental concept of files and their role in operating systems
  • Identify and explain various file attributes and metadata
  • Analyze different file operations and their implementations
  • Explain directory structures and organization methods
  • Compare different directory implementation techniques
  • Understand path resolution and file system navigation
  • Describe the layered architecture of file systems

Introduction to File Systems

A file system provides a way to store, organize, and access data on storage devices. It acts as an interface between the operating system and storage hardware, providing abstraction and management capabilities.

Why File Systems?
  • Persistent data storage
  • Data organization and structure
  • Access control and security
  • Data sharing between programs
  • Efficient storage utilization
  • Data integrity and reliability
File System Services
  • File creation and deletion
  • Directory management
  • File access and modification
  • Metadata management
  • Space allocation
  • Backup and recovery
Applications
Word, Excel, Browser, Games
↓
Operating System
File System Interface (open, read, write, close)
↓
Storage Hardware
Hard Disk, SSD, Flash Drive

File Concept

A file is a named collection of related information that is recorded on secondary storage. Files provide a uniform logical view of data storage regardless of the physical storage medium.

File Definitions and Characteristics

From User Perspective:
  • Named Collection: Files have unique names
  • Persistent Storage: Data survives program termination
  • Sharable Resource: Multiple programs can access
  • Structured Data: Organized information
From System Perspective:
  • Storage Abstraction: Hide hardware details
  • Access Control: Permission management
  • Resource Management: Space allocation
  • Metadata Container: Store file attributes

File Types


Regular Files
  • Text files (.txt, .md)
  • Binary files (.exe, .jpg)
  • Source code (.c, .java)
  • Data files (.csv, .json)

Directory Files
  • Contains file entries
  • Organizes file system
  • Hierarchical structure
  • Navigation aid

Special Files
  • Device files (/dev/*)
  • Named pipes (FIFO)
  • Symbolic links
  • Socket files
File Structure Models
1. Unstructured (Stream)
Byte 0: H
Byte 1: e
Byte 2: l
Byte 3: l
Byte 4: o
Byte 5: \n
Byte 6: W
...

Simple sequence of bytes
Most flexible approach
Used by Unix/Linux
2. Record-Based
Record 1: [John, Doe, 25]
Record 2: [Jane, Smith, 30]  
Record 3: [Bob, Wilson, 28]
...

Fixed or variable records
Database-like structure
Used in mainframes
3. Tree-Based
Root
├── Branch 1
│   ├── Leaf 1.1
│   └── Leaf 1.2
└── Branch 2
    └── Leaf 2.1

Hierarchical structure
Key-value organization
Used in databases

File Attributes

File attributes (metadata) contain information about the file beyond its actual data content. This metadata is essential for file management and access control.

Common File Attributes

Attribute Description Example Purpose
Name Human-readable file identifier document.txt User identification
Type File format or extension .txt, .exe, .jpg Application association
Size File size in bytes 2,048 bytes Storage management
Location Physical storage address Block 1024-1030 System access
Created File creation timestamp 2025-01-15 10:30:45 Audit trail
Modified Last modification time 2025-01-16 14:22:10 Version tracking
Accessed Last access timestamp 2025-01-17 09:15:20 Usage monitoring
Owner User who created the file john_doe (UID: 1001) Access control
Permissions Access rights (read/write/execute) rwxr--r-- (755) Security
Links Number of hard links 3 links Reference counting
Permission Systems
Unix/Linux Permissions:
Format: rwxrwxrwx
Position: Owner|Group|Others
Example: rwxr-xr-- (754)

r = Read (4)    - View file contents
w = Write (2)   - Modify file
x = Execute (1) - Run as program

Common Combinations:
755: rwxr-xr-x (owner: all, others: read+exec)
644: rw-r--r-- (owner: read+write, others: read)
600: rw------- (owner only: read+write)
Timestamps
Three Important Times:
  • mtime (modification): Content changed
  • atime (access): File was read
  • ctime (change): Metadata changed
Unix stat command:
Access: 2025-01-17 09:15:20
Modify: 2025-01-16 14:22:10
Change: 2025-01-16 14:22:10

File Operations

File systems provide a standard set of operations for manipulating files. These operations form the interface between applications and the file system.

Basic File Operations

Create

Allocate space and create file entry

int fd = creat("file.txt", 0644);
FILE* fp = fopen("file.txt", "w");
Open

Prepare file for access, get file descriptor

int fd = open("file.txt", O_RDWR);
FILE* fp = fopen("file.txt", "r+");
Read

Retrieve data from file

ssize_t n = read(fd, buffer, size);
size_t n = fread(buffer, 1, size, fp);
Write

Store data to file

ssize_t n = write(fd, buffer, size);
size_t n = fwrite(buffer, 1, size, fp);
Seek

Change file position pointer

off_t pos = lseek(fd, offset, SEEK_SET);
int ret = fseek(fp, offset, SEEK_CUR);
Close

Release file descriptor

int ret = close(fd);
int ret = fclose(fp);
Delete

Remove file from file system

int ret = unlink("file.txt");
int ret = remove("file.txt");
Stat

Get file attributes and metadata

struct stat st;
int ret = stat("file.txt", &st);

File Access Methods

1. Sequential Access:
- Read/write from beginning to end
- Natural for many applications
- Efficient for streaming data
- Example: Processing log files

2. Direct (Random) Access:  
- Jump to any position in file
- Efficient for databases
- Requires seek operations
- Example: Database records

3. Indexed Access:
- Use index structure for fast access
- Combination of sequential and direct
- Complex but very efficient
- Example: Database indexes

File Locking

Shared Lock (Read Lock):
- Multiple readers allowed
- No writers allowed
- Example: Database queries

Exclusive Lock (Write Lock):
- Only one writer allowed
- No readers allowed  
- Example: File updates

Implementation:
struct flock lock;
lock.l_type = F_WRLCK;    // Write lock
lock.l_whence = SEEK_SET;
lock.l_start = 0;
lock.l_len = 0;           // Entire file
fcntl(fd, F_SETLKW, &lock);

Directory Structure

Directories provide organization for files, creating a hierarchical namespace that allows users and programs to locate and manage files efficiently.

Directory Types
1. Single-Level Directory
  • All files in one directory
  • Simple but limited
  • Name collision problems
  • Used in early systems
2. Two-Level Directory
  • Separate directory per user
  • Solves name collision
  • Still limited organization
  • No subdirectories
3. Hierarchical Directory
  • Tree structure with subdirectories
  • Most common in modern systems
  • Flexible organization
  • Unlimited depth
Typical Directory Tree
/                          (root)
├── bin/                   (system binaries)
│   ├── ls
│   ├── cp
│   └── mv
├── home/                  (user directories)
│   ├── alice/
│   │   ├── documents/
│   │   │   ├── report.txt
│   │   │   └── presentation.ppt
│   │   ├── pictures/
│   │   └── music/
│   └── bob/
│       ├── projects/
│       └── downloads/
├── etc/                   (configuration)
│   ├── passwd
│   └── hosts
├── usr/                   (user programs)
│   ├── bin/
│   ├── lib/
│   └── share/
└── var/                   (variable data)
    ├── log/
    └── tmp/

Path Types

Absolute Path:
- Starts from root directory (/)
- Complete path specification
- Unambiguous location
- Examples:
  /home/alice/documents/report.txt
  /usr/bin/gcc
  /etc/passwd

Relative Path:
- Relative to current directory
- Shorter specification
- Context-dependent
- Examples:
  documents/report.txt
  ../bob/projects/
  ./script.sh

Special Directory Entries

Special Entries:
.     Current directory
..    Parent directory
~     User home directory (shell)
/     Root directory

Examples:
cd .          # Stay in current directory
cd ..         # Go to parent directory  
cd ../..      # Go up two levels
cd ~          # Go to home directory
cd /          # Go to root directory

Hidden Files:
Files starting with '.' are hidden
.bashrc       Shell configuration
.ssh/         SSH keys
.gitignore    Git ignore file
Directory Operations
Create Directory
mkdir("newdir", 0755);
mkdir -p path/to/dir    # Shell
List Directory
DIR *dp = opendir(".");
struct dirent *entry;
while ((entry = readdir(dp)))
Remove Directory
rmdir("dirname");       # Empty only
rm -rf dirname          # Recursive
Change Directory
chdir("/home/alice");
cd /home/alice          # Shell

Directory Implementation

Directories are implemented as special files that contain mappings between file names and file system structures (inodes or file allocation entries).

Implementation Methods

1. Linear List
Structure:
Entry 1: filename1 -> inode1
Entry 2: filename2 -> inode2
Entry 3: filename3 -> inode3
...

Pros:
- Simple implementation
- Low memory overhead
- Sequential access efficient

Cons:
- O(n) search time
- Slow for large directories
- Insertion/deletion costly
2. Hash Table
Structure:
Hash("file1") -> Bucket 0
Hash("file2") -> Bucket 5
Hash("file3") -> Bucket 2
...

Pros:
- O(1) average search time
- Fast lookups
- Good for large directories

Cons:
- Hash collisions
- Complex implementation
- Memory overhead
3. B-Tree
Structure:
      [M, S]
     /   |   \
  [A,G] [P,Q] [U,Z]
  
Pros:
- O(log n) search time
- Sorted order maintained
- Efficient range queries
- Good for very large dirs

Cons:
- Complex implementation
- Higher memory overhead
- Rebalancing required
Directory Entry Structure
Unix Directory Entry:
struct dirent {
    ino_t d_ino;           // Inode number
    off_t d_off;           // Offset to next entry
    unsigned short d_reclen; // Record length
    unsigned char d_type;   // File type
    char d_name[];         // Filename (null-terminated)
};

Windows Directory Entry:
- Long filename support (up to 255 chars)
- 8.3 compatibility names
- File attributes stored in entry
- Timestamps and size information
Directory Search Optimization
  • Caching: Keep recent entries in memory
  • Indexing: Separate index structure
  • Hashing: Fast name lookup
  • Sorting: Binary search possible
Directory Cache (dcache):
- Recent lookups cached in memory
- Negative caching (file not found)
- LRU replacement policy
- Significant performance improvement

Path Resolution

Path resolution is the process of converting a pathname into the corresponding file system object (inode). This involves traversing the directory hierarchy and resolving each component.

Path Resolution Algorithm

Path Resolution Steps for "/home/alice/documents/report.txt":

1. Start at root directory (/):
   - Current inode = root inode (typically inode 2)
   - Remaining path = "home/alice/documents/report.txt"

2. Process "home" component:
   - Search current directory (root) for "home"
   - Find entry: "home" -> inode 1024
   - Current inode = 1024
   - Remaining path = "alice/documents/report.txt"

3. Process "alice" component:
   - Search directory (inode 1024) for "alice"
   - Find entry: "alice" -> inode 2048
   - Current inode = 2048
   - Remaining path = "documents/report.txt"

4. Process "documents" component:
   - Search directory (inode 2048) for "documents"
   - Find entry: "documents" -> inode 3072
   - Current inode = 3072
   - Remaining path = "report.txt"

5. Process "report.txt" component:
   - Search directory (inode 3072) for "report.txt"
   - Find entry: "report.txt" -> inode 4096
   - Final result: inode 4096

Path Resolution Challenges

  • Symbolic Links: May point to other paths
  • Mount Points: Cross file system boundaries
  • Permissions: Check execute permission on directories
  • Case Sensitivity: Varies by file system
  • Long Paths: Maximum path length limits
  • Circular Links: Infinite loop prevention

Performance Optimizations

  • Name Cache: Cache recent lookups
  • Directory Cache: Keep directories in memory
  • Prefetching: Read ahead for sequential access
  • Batching: Group multiple operations
  • Short-circuit: Skip unnecessary checks
  • Parallel Lookup: Multiple components simultaneously
Path Resolution Example
File System Structure
/ (inode 2)
├── home (inode 1024)
│   └── alice (inode 2048)
│       ├── documents (inode 3072)
│       │   ├── report.txt (inode 4096)
│       │   └── notes.md (inode 4097)
│       └── pictures (inode 3073)
└── usr (inode 1025)
    └── bin (inode 2049)
Resolution Trace
Resolving: "/home/alice/report.txt"

Step 1: Start at root (inode 2)
Step 2: Look for "home" in root directory
        → Found: inode 1024
Step 3: Look for "alice" in inode 1024
        → Found: inode 2048  
Step 4: Look for "report.txt" in inode 2048
        → Not found! Wrong directory
        
Error: No such file or directory

Correct path should be:
"/home/alice/documents/report.txt"

File System Architecture Layers

Modern file systems are organized in layers, each providing specific functionality and abstracting lower-level details.

File System Layer Architecture
Application Layer
User programs (editors, compilers, databases)
↓ System calls (open, read, write, close)
Logical File System
File operations, directory management, security
↓ File organization methods
File Organization Module
File allocation, free space management
↓ Block operations
Basic File System
Physical block management, device drivers
↓ I/O control
I/O Control
Device drivers, interrupt handlers
↓ Hardware interface
Devices
Hard disks, SSDs, flash drives

Layer Responsibilities

1. Application Layer:
- File manipulation by user programs
- High-level operations (copy, move, search)
- User interface and commands

2. Logical File System:
- File system interface (system calls)
- Directory operations and name resolution
- File access control and security
- File metadata management

3. File Organization Module:
- Logical to physical block translation
- File allocation methods (contiguous, linked, indexed)
- Free space management
- File system consistency

4. Basic File System:
- Physical block I/O operations
- Buffer cache management
- Device abstraction layer

Inter-layer Communication

Example: Reading a file

Application: fread(buffer, size, 1, fp)
     ↓
Logical FS: Resolve filename to inode
           Check permissions
           Get file position
     ↓
File Organization: Translate file offset to block numbers
                  Check for cached blocks
     ↓
Basic FS: Issue block read requests
         Manage buffer cache
     ↓
I/O Control: Send commands to device
            Handle interrupts
     ↓
Device: Physical read operation

Practical Examples

File System Operations Example

Scenario: Creating and Managing a Project Directory Structure
Shell Commands
# Create project structure
mkdir -p myproject/{src,docs,tests,build}
cd myproject

# Create files
touch src/main.c src/utils.c
touch docs/README.md docs/design.txt
touch tests/test_main.c

# Set permissions
chmod 755 src/*.c        # Executable source
chmod 644 docs/*         # Read-only docs
chmod 600 config.secret  # Owner only

# List with details
ls -la
total 24
drwxr-xr-x  6 user group 4096 Jan 17 10:30 .
drwxr-xr-x  3 user group 4096 Jan 17 10:25 ..
drwxr-xr-x  2 user group 4096 Jan 17 10:30 build
drwxr-xr-x  2 user group 4096 Jan 17 10:30 docs
drwxr-xr-x  2 user group 4096 Jan 17 10:30 src
drwxr-xr-x  2 user group 4096 Jan 17 10:30 tests
C Programming Example
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
    struct stat st;
    int fd;
    
    // Create directory
    mkdir("output", 0755);
    
    // Create file
    fd = creat("output/results.txt", 0644);
    if (fd == -1) {
        perror("creat failed");
        return 1;
    }
    
    // Write data
    write(fd, "Hello, World!\n", 14);
    close(fd);
    
    // Get file information
    if (stat("output/results.txt", &st) == 0) {
        printf("File size: %ld bytes\n", st.st_size);
        printf("Permissions: %o\n", st.st_mode & 0777);
        printf("Links: %ld\n", st.st_nlink);
        printf("Owner: %d\n", st.st_uid);
    }
    
    return 0;
}
Directory Listing Program
#include <stdio.h>
#include <dirent.h>
#include <sys/stat.h>
#include <string.h>

void list_directory(const char *path) {
    DIR *dp;
    struct dirent *entry;
    struct stat statbuf;
    char fullpath[1024];
    
    dp = opendir(path);
    if (dp == NULL) {
        perror("opendir");
        return;
    }
    
    printf("Directory listing for %s:\n", path);
    printf("%-20s %10s %s\n", "Name", "Size", "Type");
    printf("----------------------------------------\n");
    
    while ((entry = readdir(dp)) != NULL) {
        // Skip hidden files starting with '.'
        if (entry->d_name[0] == '.' && strlen(entry->d_name) > 1) 
            continue;
            
        // Build full path
        snprintf(fullpath, sizeof(fullpath), "%s/%s", path, entry->d_name);
        
        if (stat(fullpath, &statbuf) == 0) {
            printf("%-20s %10ld %s\n", 
                   entry->d_name,
                   statbuf.st_size,
                   S_ISDIR(statbuf.st_mode) ? "DIR" : "FILE");
        }
    }
    
    closedir(dp);
}

int main() {
    list_directory(".");
    return 0;
}

Path Resolution Example

Trace: Resolving the path "/usr/local/bin/gcc"

Step Current Directory Looking For Found Inode Remaining Path Status
1 / (inode 2) usr 1025 local/bin/gcc Found
2 /usr (inode 1025) local 2050 bin/gcc Found
3 /usr/local (inode 2050) bin 3075 gcc Found
4 /usr/local/bin (inode 3075) gcc 4100 (empty) Complete

Result: Path "/usr/local/bin/gcc" resolves to inode 4100

Operations: 4 directory searches, 4 inode accesses

Optimization: Directory cache could reduce this to 1-2 disk accesses if components are cached

Session Summary

Key Concepts
  • Files: Named collections of data with persistent storage
  • File Attributes: Metadata including size, permissions, timestamps
  • File Operations: Create, open, read, write, seek, close, delete
  • Directories: Special files organizing hierarchical namespace
  • Path Resolution: Converting pathnames to file system objects
  • Layered Architecture: Abstraction levels from hardware to applications
Design Principles
  • Abstraction: Hide hardware complexity from users
  • Persistence: Data survives program termination
  • Organization: Hierarchical structure for easy navigation
  • Security: Access control and permission management
  • Performance: Caching and optimization strategies
  • Reliability: Data integrity and error handling
Next Session Preview

Session 5.4 will cover File Allocation Methods, exploring contiguous, linked, and indexed allocation strategies, along with free-space management techniques for efficient storage utilization.

Previous: Session 5.2
Next: Session 5.4