File Systems | Computer Science Fundamentals

Learning Objectives

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

Understand the purpose and structure of file systems
Explain file concepts, attributes, and operations
Describe directory structures and their implementation
Understand different file allocation methods (contiguous, linked, indexed)
Explain the FAT (File Allocation Table) file system
Understand the inode-based file system structure
Describe journaling file systems and their benefits
Understand free space management techniques
Explain file system mounting and disk organization

Introduction to File Systems
File Concept
File Operations
Directory Structure
File Allocation Methods
FAT File System
Inode-Based File Systems
Journaling File Systems
Free Space Management
File System Implementation
Exercises
Summary

Introduction to File Systems

A file system controls how data is stored and retrieved on storage devices. Without a file system, data would be one large undifferentiated blob with no way to identify where one piece of information stops and another begins.

Purpose of File Systems

Persistent Storage: Data survives system reboots
Organization: Logical structure for storing data
Naming: Human-readable names for data
Protection: Access control and permissions
Reliability: Data integrity and recovery

File System Layers

+-------------------------+
|   Application Layer     |  (Programs using files)
+-------------------------+
|   Logical File System   |  (Directory management, security)
+-------------------------+
| File Organization Module|  (File allocation, free space)
+-------------------------+
|   Basic File System     |  (Generic I/O commands)
+-------------------------+
|    I/O Control Layer    |  (Device drivers)
+-------------------------+
|    Physical Device      |  (Disk hardware)
+-------------------------+

Common File Systems

FAT32: Simple, widely compatible (USB drives)
NTFS: Windows default, journaling, large file support
ext4: Linux default, journaling, efficient
HFS+/APFS: macOS file systems
ZFS: Advanced features, snapshots, compression

File Concept

A file is a named collection of related information recorded on secondary storage.

File Attributes (Metadata)

File: document.txt
+------------------+------------------+
| Attribute        | Value            |
+------------------+------------------+
| Name             | document.txt     |
| Type             | .txt (text)      |
| Size             | 4096 bytes       |
| Created          | 2025-01-15 10:30 |
| Modified         | 2025-01-20 14:22 |
| Accessed         | 2025-01-21 09:15 |
| Owner            | user (UID: 1000) |
| Permissions      | rw-r--r--        |
| Location         | Block 5000       |
| Inode Number     | 12345            |
+------------------+------------------+

File Types

Regular Files: Contains user data
- Text files (ASCII, UTF-8)
- Binary files (executables, images)
Directory Files: Contains file names and pointers
Special Files: Represent devices
- Character special files (terminals, serial ports)
- Block special files (disks, USB drives)
Symbolic Links: Pointers to other files

File Structure

No Structure (Byte Sequence):
+--+--+--+--+--+--+--+--+
|01|23|45|67|89|AB|CD|EF|  Raw bytes
+--+--+--+--+--+--+--+--+

Record Structure:
+--------+--------+--------+
| Record | Record | Record |  Fixed-size records
|   1    |   2    |   3    |
+--------+--------+--------+

Tree Structure:
     Root
    /    \
   Key  Value
  /  \
Sub  Sub

Examples:
- Byte sequence: Most modern OS (Unix, Windows)
- Record: Legacy systems, databases
- Tree: XML, JSON files (application level)

File Operations

Operating systems provide system calls for file manipulation.

Basic File Operations

Create: Make new file
Open: Prepare file for access
Read: Read data from file
Write: Write data to file
Seek: Reposition file pointer
Delete: Remove file
Truncate: Erase contents but keep attributes
Close: Release resources

File Operations in C

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

int main() {
    int fd;
    char buffer[100];
    ssize_t bytes_read, bytes_written;

    // Create/Open file for writing
    fd = open("test.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (fd == -1) {
        perror("Error opening file");
        return 1;
    }

    // Write to file
    const char *text = "Hello, File System!";
    bytes_written = write(fd, text, strlen(text));
    printf("Wrote %zd bytes\n", bytes_written);

    // Close file
    close(fd);

    // Open file for reading
    fd = open("test.txt", O_RDONLY);
    if (fd == -1) {
        perror("Error opening file");
        return 1;
    }

    // Read from file
    bytes_read = read(fd, buffer, sizeof(buffer) - 1);
    buffer[bytes_read] = '\0';  // Null terminate
    printf("Read: %s\n", buffer);

    // Close file
    close(fd);

    return 0;
}

File Operations in Python

# Write to file
with open('test.txt', 'w') as f:
    f.write("Hello, File System!\n")
    f.write("Second line\n")

# Read entire file
with open('test.txt', 'r') as f:
    content = f.read()
    print(content)

# Read line by line
with open('test.txt', 'r') as f:
    for line in f:
        print(line.strip())

# Append to file
with open('test.txt', 'a') as f:
    f.write("Appended line\n")

# Binary file operations
with open('image.png', 'rb') as f:
    data = f.read(100)  # Read first 100 bytes
    print(f"Read {len(data)} bytes")

Open File Table

The OS maintains a table of open files:

System-Wide Open File Table:
+-------+--------+----------+---------+
| Index | Inode  | Count    | Offset  |
+-------+--------+----------+---------+
|   0   | 12345  |    2     |   150   |  (2 processes have this open)
|   1   | 67890  |    1     |    0    |
|   2   | 11111  |    3     |  1024   |
+-------+--------+----------+---------+

Per-Process Open File Table:
Process 1:
+----+------------------+
| FD | System Table Ptr |
+----+------------------+
|  0 | stdin            |
|  1 | stdout           |
|  2 | stderr           |
|  3 | -> Entry 0       |
|  4 | -> Entry 2       |
+----+------------------+

File Descriptor (FD): Integer identifying open file

Directory Structure

Directories organize files into a hierarchical structure.

Single-Level Directory

All files in one directory (early systems).

+-------------------------------------+
| file1 | file2 | file3 | file4 | ... |
+-------------------------------------+

Problems:
- Naming conflicts
- No organization
- Difficult to find files

Two-Level Directory

Separate directory for each user.

          Root
           |
    +------+------+
    |             |
  User1         User2
    |             |
+---+---+     +---+---+
| Files |     | Files |
+-------+     +-------+

Better, but:
- Still limited organization
- Can't group files logically

Tree-Structured Directory

Hierarchical directory structure (modern systems).

                    / (root)
                    |
        +-----------+-----------+
        |           |           |
      home         etc         usr
        |           |           |
    +---+---+   config       +--+--+
    |       |   files        |     |
  alice   bob              bin   lib
    |                        |
 +--+--+              +------+------+
 |  |  |              |      |      |
doc pics code       gcc    python  ls

Directory Operations

#include <dirent.h>
#include <stdio.h>

int main() {
    DIR *dir;
    struct dirent *entry;

    // Open directory
    dir = opendir(".");
    if (dir == NULL) {
        perror("opendir");
        return 1;
    }

    // Read directory entries
    printf("Contents of current directory:\n");
    while ((entry = readdir(dir)) != NULL) {
        printf("  %s\n", entry->d_name);
    }

    // Close directory
    closedir(dir);

    return 0;
}

Python Directory Operations

import os

# List directory contents
print("Current directory:", os.getcwd())
print("\nContents:")
for item in os.listdir('.'):
    print(f"  {item}")

# Walk directory tree
print("\nDirectory tree:")
for root, dirs, files in os.walk('.'):
    level = root.replace('.', '').count(os.sep)
    indent = ' ' * 2 * level
    print(f"{indent}{os.path.basename(root)}/")
    subindent = ' ' * 2 * (level + 1)
    for file in files:
        print(f"{subindent}{file}")

# Create and remove directories
os.mkdir('test_dir')
os.makedirs('path/to/nested/dir')  # Create intermediate dirs
os.rmdir('test_dir')

Directory Implementation

Directories are special files containing mappings:

Directory: /home/alice/

Linear List:
+----------------+-------+
| File Name      | Inode |
+----------------+-------+
| .              | 1000  |
| ..             | 100   |
| document.txt   | 1234  |
| image.png      | 5678  |
| script.py      | 9012  |
+----------------+-------+

Hash Table (faster lookup):
Hash(name) -> (name, inode) list

Tree Structure (sorted):
      document.txt
      /          \
  image.png   script.py

File Allocation Methods

How disk blocks are allocated to files.

1. Contiguous Allocation

Each file occupies contiguous blocks on disk.

Disk Blocks:
+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
      |File A |   |File B |   |File C |

Directory Entry:
+-------+-------+--------+
| Name  | Start | Length |
+-------+-------+--------+
| A     |   1   |   2    |
| B     |   4   |   2    |
| C     |   7   |   2    |
+-------+-------+--------+

Advantages:

Simple to implement
Excellent read performance (sequential access)
Random access is easy

Disadvantages:

External fragmentation
Difficult to grow files
Need to know file size in advance

2. Linked Allocation

Each block contains pointer to next block.

File A: Start at block 1

Directory Entry:
+-------+-------+
| Name  | Start |
+-------+-------+
| A     |   1   |
+-------+-------+

Disk Blocks:
Block 1: [Data | ptr=4]  →  Block 4: [Data | ptr=7]  →  Block 7: [Data | NULL]

Visual:
+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
      ↓           ↓           ↓
    File A      File A      File A
    (next=4)    (next=7)    (end)

Advantages:

No external fragmentation
Files can grow easily
No need to know file size in advance

Disadvantages:

Poor random access (must follow chain)
Reliability (if one pointer lost, rest of file inaccessible)
Overhead of pointers in each block

3. Indexed Allocation

Each file has an index block containing pointers to data blocks.

File A: Index block at 5

Directory Entry:
+-------+-------------+
| Name  | Index Block |
+-------+-------------+
| A     |      5      |
+-------+-------------+

Index Block 5:
+---+
| 1 |  →  Data block 1
| 4 |  →  Data block 4
| 7 |  →  Data block 7
| 9 |  →  Data block 9
| - |
+---+

Disk:
+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
      ↑       ↑   Index   ↑       ↑
   File A  File A  Block  File A  File A

Advantages:

Good random access
No external fragmentation
Can grow files (add more index blocks)

Disadvantages:

Index block overhead
For small files, wasted space in index block

Multilevel Index

For large files, use multiple levels of index blocks.

File Structure:
+---------------+
| Inode         |
+---------------+
| Direct [0]    | →  Data block
| Direct [1]    | →  Data block
| ...           |
| Direct [11]   | →  Data block
| Single Indirect| →  Index block  →  Data blocks
| Double Indirect| →  Index  →  Index blocks  →  Data blocks
| Triple Indirect| →  Index  →  Index  →  Index blocks  →  Data
+---------------+

Example with 4KB blocks, 4-byte pointers:
- Each index block holds 1024 pointers
- Direct: 12 blocks = 48 KB
- Single indirect: 1024 blocks = 4 MB
- Double indirect: 1024 × 1024 blocks = 4 GB
- Triple indirect: 1024 × 1024 × 1024 blocks = 4 TB

FAT File System

FAT (File Allocation Table) is a simple file system used on removable media.

FAT Structure

Disk Layout:
+---------------+
| Boot Sector   |
+---------------+
| FAT 1         |  (Primary)
+---------------+
| FAT 2         |  (Backup)
+---------------+
| Root Directory|
+---------------+
| Data Area     |
|  (Clusters)   |
+---------------+

File Allocation Table

The FAT is an array where each entry represents a cluster.

FAT Table:
+-------+-------+
| Index | Value |
+-------+-------+
|   0   | 0xF8  |  (Media descriptor)
|   1   | 0xFF  |  (Reserved)
|   2   |   5   |  (Next cluster of file)
|   3   | 0xFF  |  (End of chain)
|   4   |   0   |  (Free cluster)
|   5   |   8   |  (Next cluster)
|   6   |   7   |  (Next cluster)
|   7   | 0xFF  |  (End of chain)
|   8   | 0xFF  |  (End of chain)
+-------+-------+

File "document.txt" starts at cluster 2:
Cluster chain: 2 → 5 → 8 (end)

Directory Entry (FAT)

32-byte Directory Entry:
+----------------+--------+
| Offset | Field         |
+--------+---------------+
|   0    | Name (8)      | document
|   8    | Extension (3) | txt
|  11    | Attributes    | 0x20 (Archive)
|  12    | Reserved      |
|  14    | Create Time   |
|  16    | Create Date   |
|  18    | Access Date   |
|  20    | EA-Index      |
|  22    | Modified Time |
|  24    | Modified Date |
|  26    | First Cluster | 2
|  28    | File Size     | 12288
+--------+---------------+

Attributes:
0x01 - Read Only
0x02 - Hidden
0x04 - System
0x08 - Volume Label
0x10 - Directory
0x20 - Archive

FAT Variants

FAT12: 12-bit cluster numbers (max 4084 clusters)
FAT16: 16-bit cluster numbers (max 65,524 clusters)
FAT32: 28-bit cluster numbers (max 268M clusters)

FAT Example Implementation

class FATFileSystem:
    def __init__(self, num_clusters):
        self.fat = [0] * num_clusters
        self.fat[0] = 0xF8  # Media descriptor
        self.fat[1] = 0xFF  # Reserved
        self.clusters = {}  # Cluster data

    def allocate_file(self, name, num_clusters):
        """Allocate clusters for a new file"""
        # Find free clusters
        free_clusters = [i for i in range(2, len(self.fat))
                        if self.fat[i] == 0]

        if len(free_clusters) < num_clusters:
            return None  # Not enough space

        # Take first num_clusters
        allocated = free_clusters[:num_clusters]

        # Build chain in FAT
        for i in range(len(allocated) - 1):
            self.fat[allocated[i]] = allocated[i + 1]
        self.fat[allocated[-1]] = 0xFF  # End of chain

        return allocated[0]  # Return first cluster

    def read_file(self, start_cluster):
        """Read all clusters of a file"""
        clusters = []
        current = start_cluster

        while current != 0xFF and current != 0:
            clusters.append(current)
            current = self.fat[current]

        return clusters

    def delete_file(self, start_cluster):
        """Delete file and free its clusters"""
        current = start_cluster

        while current != 0xFF and current != 0:
            next_cluster = self.fat[current]
            self.fat[current] = 0  # Mark as free
            current = next_cluster

# Example usage
fs = FATFileSystem(20)

# Allocate file needing 3 clusters
start = fs.allocate_file("test.txt", 3)
print(f"File allocated starting at cluster {start}")
print(f"Cluster chain: {fs.read_file(start)}")

# Delete file
fs.delete_file(start)
print("File deleted")

Inode-Based File Systems

Inodes (Index Nodes) are data structures used in Unix-like file systems (ext2/3/4, XFS, etc.).

Inode Structure

Inode (128 bytes in ext4):
+------------------+------------------+
| Field            | Size             |
+------------------+------------------+
| Mode             | 2 bytes          | (File type + permissions)
| Owner            | 2 bytes          | (UID)
| Size             | 8 bytes          | (File size)
| Access Time      | 4 bytes          |
| Creation Time    | 4 bytes          |
| Modification Time| 4 bytes          |
| Deletion Time    | 4 bytes          |
| Group            | 2 bytes          | (GID)
| Link Count       | 2 bytes          | (Hard links)
| Block Count      | 4 bytes          | (512-byte blocks)
| Direct Blocks[12]| 48 bytes         | (Pointers to data blocks)
| Indirect Block   | 4 bytes          |
| Double Indirect  | 4 bytes          |
| Triple Indirect  | 4 bytes          |
| Generation       | 4 bytes          |
| File ACL         | 4 bytes          |
| Directory ACL    | 4 bytes          |
| ...              | ...              |
+------------------+------------------+

Inode Addressing

Inode:
+---------------+
| Direct [0]    | →  Data block 1000
| Direct [1]    | →  Data block 1001
| Direct [2]    | →  Data block 1002
| ...           |
| Direct [11]   | →  Data block 1011
+---------------+
| Indirect      | →  Index Block 2000
+---------------+     +----+
| Double Indirect| →  | ...| →  Index blocks  →  Data
+---------------+     +----+
| Triple Indirect| →  Index  →  Index  →  Index  →  Data
+---------------+

For 4KB blocks with 4-byte pointers (1024 pointers per block):
- 12 direct blocks: 12 × 4KB = 48 KB
- 1 indirect: 1024 × 4KB = 4 MB
- 1 double indirect: 1024 × 1024 × 4KB = 4 GB
- 1 triple indirect: 1024³ × 4KB = 4 TB
Maximum file size: ~4 TB

Directory in Inode System

Directory is a special file containing:
+--------+----------+
| Inode  | Filename |
+--------+----------+
| 12345  | .        |  (This directory)
| 100    | ..       |  (Parent directory)
| 12346  | file1.txt|
| 12347  | file2.c  |
| 12348  | subdir   |
+--------+----------+

Directory data blocks:
+------+-------+---------+----------+
| Inode| RecLen| NameLen | Name     |
+------+-------+---------+----------+
| 12345|  12   |   1     | .        |
| 100  |  12   |   2     | ..       |
| 12346|  20   |   9     | file1.txt|
| 12347|  16   |   7     | file2.c  |
| 12348|  16   |   6     | subdir   |
+------+-------+---------+----------+

Hard Links vs Symbolic Links

Hard Link: Multiple directory entries point to same inode

Directory A:          Directory B:
+-------+-------+     +-------+-------+
| inode | name  |     | inode | name  |
+-------+-------+     +-------+-------+
| 1234  | file1 |     | 1234  | file2 |
+-------+-------+     +-------+-------+
         ↓                     ↓
         +---------------------+
                   |
              Inode 1234
           (link count = 2)
                   |
              Data Blocks

Deleting file1 doesn't delete data (link count becomes 1)
Only when link count reaches 0 is data deleted

Symbolic Link: Special file containing path to another file

Directory:
+-------+--------+
| inode | name   |
+-------+--------+
| 1234  | file1  |
| 5678  | link1  | (Symbolic link)
+-------+--------+
    ↓         ↓
Inode 1234   Inode 5678 (type = symlink)
    ↓         ↓
Data blocks  Data: "/path/to/file1"

If file1 deleted, link1 becomes broken (dangling)

Inode Simulator

class Inode:
    def __init__(self, inode_num, file_type, size):
        self.inode_num = inode_num
        self.file_type = file_type  # 'f' or 'd'
        self.size = size
        self.link_count = 1
        self.direct_blocks = [None] * 12
        self.indirect = None
        self.double_indirect = None
        self.triple_indirect = None

    def allocate_blocks(self, block_allocator, num_blocks):
        """Allocate data blocks to this inode"""
        allocated = 0

        # Allocate direct blocks first
        for i in range(12):
            if allocated >= num_blocks:
                break
            self.direct_blocks[i] = block_allocator.allocate()
            allocated += 1

        # TODO: Handle indirect blocks for larger files
        return allocated

class Directory:
    def __init__(self, inode):
        self.inode = inode
        self.entries = {}  # name -> inode_num

    def add_entry(self, name, inode_num):
        self.entries[name] = inode_num

    def lookup(self, name):
        return self.entries.get(name)

class SimpleInodeFS:
    def __init__(self):
        self.inodes = {}
        self.next_inode = 1
        self.block_allocator = BlockAllocator(1000)

    def create_file(self, name, size):
        inode_num = self.next_inode
        self.next_inode += 1

        inode = Inode(inode_num, 'f', size)
        num_blocks = (size + 4095) // 4096  # Ceiling division
        inode.allocate_blocks(self.block_allocator, num_blocks)

        self.inodes[inode_num] = inode
        return inode_num

class BlockAllocator:
    def __init__(self, num_blocks):
        self.free_blocks = list(range(num_blocks))

    def allocate(self):
        if self.free_blocks:
            return self.free_blocks.pop(0)
        return None

# Example
fs = SimpleInodeFS()
inode_num = fs.create_file("test.txt", 8192)
inode = fs.inodes[inode_num]
print(f"Created file with inode {inode_num}")
print(f"Direct blocks: {inode.direct_blocks[:3]}")

Journaling File Systems

Journaling provides reliability by logging changes before committing them.

The Problem: Crash Consistency

Operation: Delete file
Steps:
1. Remove directory entry
2. Mark inode as free
3. Mark data blocks as free

If crash occurs between steps:
- After step 1: Inode and blocks leaked (space wasted)
- After step 2: Blocks still marked used (space wasted)
- Inconsistent file system state

Journaling Solution

Write changes to a log (journal) first, then apply to file system.

Journal:
+------------------+
| TxBegin          |
| Update directory |
| Update inode     |
| Update bitmap    |
| TxEnd            |
+------------------+
        ↓
  After TxEnd written:
        ↓
Apply changes to
actual file system
        ↓
   Mark journal
transaction complete

Journal Workflow

1. Journal Write:
   Write intended changes to journal
   +--------+
   | Begin  |
   | Op 1   |
   | Op 2   |
   | Commit |
   +--------+

2. Checkpoint:
   Apply changes to actual file system locations
   Directory → Updated
   Inode → Updated
   Bitmap → Updated

3. Free:
   Mark journal space as free
   +--------+
   |  Free  |
   +--------+

If crash occurs:
- Before commit: Ignore journal entry (do nothing)
- After commit: Replay journal on reboot (redo changes)

Types of Journaling

Data Journaling: Log both metadata and data
- Most safe
- Slower (everything written twice)
Metadata Journaling: Log only metadata
- Faster
- Data may be inconsistent
Ordered Journaling: Write data first, then journal metadata
- Good balance
- Used by ext3/ext4 (default)

Journaling Example

class Journal:
    def __init__(self):
        self.transactions = []
        self.current_tx = None

    def begin_transaction(self, tx_id):
        """Start new transaction"""
        self.current_tx = {
            'id': tx_id,
            'operations': [],
            'committed': False
        }

    def log_operation(self, op_type, data):
        """Add operation to current transaction"""
        if self.current_tx:
            self.current_tx['operations'].append({
                'type': op_type,
                'data': data
            })

    def commit_transaction(self):
        """Commit current transaction"""
        if self.current_tx:
            self.current_tx['committed'] = True
            self.transactions.append(self.current_tx)
            print(f"Transaction {self.current_tx['id']} committed")
            self.current_tx = None

    def replay(self, file_system):
        """Replay committed transactions after crash"""
        print("Replaying journal...")
        for tx in self.transactions:
            if tx['committed']:
                print(f"  Replaying transaction {tx['id']}")
                for op in tx['operations']:
                    file_system.apply_operation(op)

class FileSystem:
    def __init__(self):
        self.files = {}
        self.journal = Journal()

    def delete_file(self, filename):
        """Delete file with journaling"""
        tx_id = len(self.journal.transactions) + 1

        # Begin transaction
        self.journal.begin_transaction(tx_id)

        # Log all operations
        self.journal.log_operation('remove_dir_entry', filename)
        self.journal.log_operation('free_inode', self.files[filename]['inode'])
        self.journal.log_operation('free_blocks', self.files[filename]['blocks'])

        # Commit transaction
        self.journal.commit_transaction()

        # Now apply changes
        self.apply_delete(filename)

    def apply_delete(self, filename):
        """Actually delete the file"""
        del self.files[filename]
        print(f"File {filename} deleted")

    def apply_operation(self, op):
        """Apply a journaled operation"""
        print(f"    Applying {op['type']}: {op['data']}")

# Example
fs = FileSystem()
fs.files['test.txt'] = {'inode': 100, 'blocks': [1, 2, 3]}
fs.delete_file('test.txt')

Free Space Management

Track which disk blocks are free for allocation.

1. Bitmap (Bit Vector)

Each block represented by one bit.

Bitmap:
Block:  0  1  2  3  4  5  6  7  8  9
Bit:   [1][0][1][1][0][0][1][1][0][1]
        ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑  ↑
        Used Free Used Used Free Free...

1 = Used
0 = Free

For 1TB disk with 4KB blocks:
- 256M blocks
- 256M bits = 32 MB bitmap

2. Linked List

Link all free blocks together.

Free List Head → Block 5 → Block 9 → Block 15 → NULL
                  [next]    [next]    [next]

Each free block stores pointer to next free block

3. Grouping

Store addresses of free blocks in first free block.

Block 100:
+-----+
| 101 | →  Block 101 (free)
| 105 | →  Block 105 (free)
| 200 | →  Block 200: [More free block addresses...]
| ... |
+-----+

4. Counting

Store starting block and count of consecutive free blocks.

Free Space List:
+-------+-------+
| Start | Count |
+-------+-------+
|  100  |   5   | (Blocks 100-104 are free)
|  200  |   3   | (Blocks 200-202 are free)
|  500  |  10   | (Blocks 500-509 are free)
+-------+-------+

File System Implementation

Disk Layout Example (ext4)

Disk:
+------------------+  Block 0
| Boot Block       |
+------------------+  Block 1
| Superblock       |  (File system metadata)
+------------------+
| Group Descriptors|
+------------------+
| Block Bitmap     |  (Free block tracking)
+------------------+
| Inode Bitmap     |  (Free inode tracking)
+------------------+
| Inode Table      |  (Array of inodes)
+------------------+
| Data Blocks      |  (File and directory data)
|                  |
|    ...           |
|                  |
+------------------+

Superblock

Contains critical file system information:

Superblock:
+--------------------+--------+
| Field              | Value  |
+--------------------+--------+
| Magic Number       | 0xEF53 | (ext2/3/4 signature)
| Total Inodes       | 100000 |
| Total Blocks       | 400000 |
| Free Blocks        | 300000 |
| Free Inodes        | 95000  |
| Block Size         | 4096   |
| Blocks per Group   | 32768  |
| Inodes per Group   | 8192   |
| Mount Time         | ...    |
| Write Time         | ...    |
| Mount Count        | 15     |
| Max Mount Count    | 30     |
| State              | Clean  |
+--------------------+--------+

File System Mounting

Before Mount:
/
├── home
├── etc
└── mnt (empty)

After mounting /dev/sdb1 at /mnt:
/
├── home
├── etc
└── mnt
    ├── file1.txt
    ├── file2.c
    └── subdir

The file system on /dev/sdb1 is now accessible under /mnt

Mount Example

import os

# Linux mount (requires root)
# os.system("mount /dev/sdb1 /mnt")

# List mounted file systems
with open('/proc/mounts', 'r') as f:
    for line in f:
        device, mount_point, fs_type, options, _, _ = line.split()
        print(f"{device} on {mount_point} type {fs_type}")

Exercises

Basic Exercises

File Attributes
- List all attributes of a file
- Use stat command or os.stat() to examine a file
- Explain what each attribute means
Directory Navigation
- Write a program to recursively list all files in a directory tree
- Count total files and directories
- Calculate total size
File Operations
- Create a file, write data, read it back
- Demonstrate seek operations
- Test file locking mechanisms

Intermediate Exercises

FAT Simulator Implement a simple FAT file system:
- Initialize FAT with given number of clusters
- Implement file creation, deletion
- Implement file read (follow cluster chain)
- Track free space
Inode File System Create a simplified inode-based system:
- Implement inode structure with direct blocks
- Create directory structure
- Support file creation and deletion
- Implement hard links (increment link count)
File Allocation Comparison Compare contiguous, linked, and indexed allocation:
- Implement all three methods
- Measure access time for sequential reads
- Measure access time for random reads
- Analyze fragmentation

Advanced Exercises

Journaling Implementation Build a simple journaling layer:
- Log operations before applying
- Implement transaction commit
- Simulate crash and recovery
- Replay journal to restore consistency
Free Space Manager Implement multiple free space management techniques:
- Bitmap
- Linked list
- Grouping
- Compare space overhead and allocation speed
Directory Cache Implement a directory cache (dentry cache):
- Cache recently accessed paths
- Use LRU for eviction
- Measure hit rate improvement
File System Checker Write a program that checks file system consistency:
- Verify all blocks are accounted for
- Check for orphaned inodes
- Detect circular directory links
- Verify inode link counts

Challenge Exercises

Complete File System Design and implement a full file system:
- Support files and directories
- Implement hierarchical directory structure
- Use inodes with multi-level indexing
- Include journaling for reliability
- Provide mount/unmount functionality
- Support basic permissions
File System Performance Analysis Analyze real file system performance:
- Measure read/write speeds with different block sizes
- Test impact of fragmentation
- Compare different file systems (ext4, XFS, Btrfs)
- Benchmark metadata operations
- Create performance visualization

Summary

In this reading, we explored file systems in depth:

Key Takeaways

File System Purpose: Organize persistent storage, provide naming, protection, and reliability
Files: Named collections of data with attributes (metadata) like size, timestamps, permissions
Directories: Special files organizing other files in hierarchical structures
File Allocation Methods:
- Contiguous: Fast but inflexible
- Linked: Flexible but slow random access
- Indexed: Best balance for large files
FAT File System: Simple linked allocation using file allocation table
- Easy to implement
- Still used on removable media
- Limited features
Inode-Based Systems: Unix/Linux approach
- Separate metadata (inode) from data
- Efficient multi-level indexing
- Support for hard and symbolic links
Journaling: Ensures consistency after crashes
- Log changes before applying
- Replay journal on recovery
- Trade-off between safety and performance
Free Space Management: Various techniques
- Bitmap: Fast, space-efficient for random access
- Linked list: Space-efficient but slow
- Hybrid approaches common

Important Concepts to Remember

File systems provide abstraction over raw storage blocks
Metadata (inodes, directory entries) is as important as data
Trade-offs exist between performance, reliability, and complexity
Journaling adds overhead but prevents corruption
Different allocation methods suit different workloads

Best Practices

Choose Right File System: Match to use case (journaling for OS, FAT for USB)
Regular Backups: File systems can fail
Monitor Fragmentation: Especially on spinning disks
Proper Unmounting: Prevents corruption
Understand Limits: File size, path length, number of files

Looking Ahead

In the next reading, we'll explore Synchronization and Deadlocks, examining how to coordinate concurrent access to shared resources, prevent race conditions, and avoid deadlock situations that can freeze systems.

File systems provide the persistent storage foundation, while synchronization ensures that concurrent processes and threads access this storage (and other shared resources) safely and correctly.

Previous Reading: 03-memory-management.md - Memory Management

Next Reading: 05-synchronization.md - Synchronization and Deadlocks

Learning Objectives

Table of Contents

Introduction to File Systems

Purpose of File Systems

File System Layers

Common File Systems

File Concept

File Attributes (Metadata)

File Types

File Structure

File Operations

Basic File Operations

File Operations in C

File Operations in Python

Open File Table

Directory Structure

Single-Level Directory

Two-Level Directory

Tree-Structured Directory

Directory Operations

Python Directory Operations

Directory Implementation

File Allocation Methods

1. Contiguous Allocation

2. Linked Allocation

3. Indexed Allocation

Multilevel Index

FAT File System

FAT Structure

File Allocation Table

Directory Entry (FAT)

FAT Variants

FAT Example Implementation

Inode-Based File Systems

Inode Structure

Inode Addressing

Directory in Inode System

Hard Links vs Symbolic Links

Inode Simulator

Journaling File Systems

The Problem: Crash Consistency

Journaling Solution

Journal Workflow

Types of Journaling

Journaling Example

Free Space Management

1. Bitmap (Bit Vector)

2. Linked List

3. Grouping

4. Counting

File System Implementation

Disk Layout Example (ext4)

Superblock

File System Mounting

Mount Example

Exercises

Basic Exercises

Intermediate Exercises

Advanced Exercises

Challenge Exercises

Summary

Key Takeaways

Important Concepts to Remember

Best Practices

Looking Ahead