File Systems & Disk Management: Structures, Allocation, Scheduling & Linux

TAKEAWAYS:

• File systems organize data hierarchically (directories, inodes) and manage metadata (permissions, timestamps) using inodes and data blocks.
• Disk allocation methods (contiguous, linked, indexed) trade off fragmentation vs. flexibility—contiguous is fastest but suffers from external fragmentation.
• Scheduling algorithms (FCFS, SSTF, SCAN, LOOK, C-SCAN) optimize seek time and head movement—NTC’s fiber-optic cable routing uses SCAN-like logic to minimize delays.
• RAID levels (0–6) balance speed, redundancy, and cost—eSewa’s payment servers use RAID 10 for high availability.
• Linux commands (ls, df, fdisk, mkfs) and file permissions (chmod, chown) are exam staples—Daraz’s order processing relies on chmod 755 for secure script execution.
• Bad blocks, disk defragmentation, and slack space are critical for performance—Pathao’s ride-matching app pre-allocates disk space to avoid fragmentation during peak hours.

1. File System Basics: Hierarchy, Metadata, and Inodes

A file system is the OS’s method of storing and organizing files on disk. It defines:

• File structure: How data is stored (sequential, indexed, etc.).
• Directory structure: Hierarchical organization (e.g., /home/user/documents).
• Metadata: Attributes like permissions (rwx), owner (chown), timestamps (ls -l), and size.

Key Components

classDiagram
    class File {
        +name: string
        +size: int
        +permissions: rwx
        +owner: user
        +timestamp: datetime
    }
    class Inode {
        +file_id: int
        +size: int
        +links: int
        +permissions: rwx
        +owner: user
        +pointers: [block_address]
    }
    class DataBlock {
        +block_id: int
        +data: bytes
    }
    File "1" --> "references" Inode : "metadata"
    Inode "1" --> "*" DataBlock : "points to"

• Inode: A data structure storing metadata (not the filename!). Each file has one inode, but multiple filenames can point to the same inode (hard links).
• Data Blocks: Actual file content stored in clusters (e.g., 4KB blocks). The inode contains pointers to these blocks.

Real-World Example: Linux File System

• eSewa’s Payment Records:
  • Stored in /var/lib/esewa/transactions/ with chmod 600 (owner-only read/write).
  • Inodes track transaction IDs, timestamps, and amounts (metadata), while data blocks store encrypted payment details.
  • Command: ls -li /var/lib/esewa/transactions/ shows inode numbers and permissions.

2. Disk Partitioning and Allocation Methods

Disks are divided into partitions (e.g., /boot, /home) for organization. Allocation methods determine how files are placed on disk.

Comparison Table: Allocation Methods

Worked Example: Contiguous Allocation

Scenario: Daraz’s order processing system stores customer orders in a contiguous block. Orders arrive in sequence: Order1 (500B), Order2 (300B), Order3 (400B), Order4 (600B).

• Allocation:
  • Order1: Blocks 1–1 (500B)
  • Order2: Blocks 2–2 (300B)
  • Order3: Blocks 3–3 (400B)
  • Order4: Cannot fit in contiguous space → external fragmentation occurs.
• Solution: Use linked allocation or indexed allocation to avoid fragmentation.

3. Disk Scheduling Algorithms

The disk arm (read/write head) moves to locate data, causing seek time (movement time) and rotational latency (waiting for the sector to rotate). Scheduling algorithms optimize this.

Algorithms and Their Logic

stateDiagram-v2
    [*] --> FCFS: "First-Come-First-Served (FCFS)"
    [*] --> SSTF: "Shortest-Seek-Time-First (SSTF)"
    [*] --> SCAN: "Elevator Algorithm (SCAN)"
    [*] --> LOOK: "SCAN but only to last request (LOOK)"
    [*] --> CLOOK: "Circular SCAN (C-SCAN)"
    FCFS --> [*]
    SSTF --> [*]
    SCAN --> [*]
    LOOK --> [*]
    CLOOK --> [*]
    note right of FCFS: "Oldest request first"
    note right of SSTF: "Minimizes seek time"
    note right of SCAN: "Moves in one direction"
    note right of LOOK: "Stops at last request"
    note right of CLOOK: "Circular movement"

Worked Example: SCAN Algorithm

Scenario: NTC’s fiber-optic cable routes requests to cylinders: Current head at 162, previous at 128. Pending requests (FIFO order): 90, 150, 386, 94, 187, 48, 17.

• Direction: Assume head moves upward (toward higher cylinders).
• Order Served:
  1. 187 (distance: |187–162| = 25)
  2. 386 (distance: |386–187| = 199)
  3. Head reaches end (400), reverses direction.
  4. 150 (distance: |400–150| = 250)
  5. 128 (previous request, but already served—skip or re-queue).
  6. 94 (distance: |150–94| = 56)
  7. 90 (distance: |94–90| = 4)
  8. 48 (distance: |90–48| = 42)
  9. 17 (distance: |48–17| = 31)
• Total Head Movement: 25 + 199 + 250 + 56 + 4 + 42 + 31 = 597 cylinders.
• Alternative: If head moved downward first, total movement would be higher (worse for SCAN).

4. RAID Levels: Redundancy and Performance

RAID (Redundant Array of Independent Disks) combines multiple disks for speed, redundancy, or both. Used by banks (e.g., Nabil Bank’s transaction servers) and e-commerce (eSewa’s payment systems).

RAID Levels Table

Real-World Example: eSewa’s RAID 10

• Why RAID 10?
  • Redundancy: If one disk fails, data remains available (mirroring).
  • Speed: Striping across mirrored pairs reduces I/O bottlenecks.
• Implementation:
  • 4 disks arranged as 2 mirrored pairs, each pair striped.
  • Command: mdadm --create /dev/md0 --level=10 --raid-devices=4 /dev/sd[1-4].

5. Linux File System Commands and Permissions

Linux uses ext4 (default) or XFS for file systems. Key commands:

File System Management

File Permissions

• Permissions: rwx for owner (u), group (g), others (o). Example: chmod 755 file.txt → rwxr-xr-x.
• Special Permissions:
  • setuid (4): Run as owner (e.g., passwd).
  • setgid (2): Inherit group permissions.
  • sticky bit (1): Only owner can delete (e.g., /tmp).

Worked Example: Daraz’s Order Script

• Scenario: Daraz’s order processing script (process_order.sh) needs:
  • Owner (root) to execute.
  • Group (staff) to read.
  • Others: no access.
• Command:

  chmod 740 process_order.sh
  chown root:staff process_order.sh
  

• Verification:

  ls -l process_order.sh
  # Output: -rwxr------ 1 root staff 1024 Jun 10 10:00 process_order.sh
  

6. Bad Blocks, Defragmentation, and Slack Space

• Bad Blocks: Physical disk sectors that fail. Handled via:
  • Remapping: OS marks bad blocks and uses spares.
  • Command: badblocks -v /dev/sdX (scan for bad blocks).
• Defragmentation: Rearranges fragmented files for contiguous storage.
  • Command: e4defrag /path/to/file (ext4).
• Slack Space: Unused space in a block after storing a file (e.g., 4KB block for a 1KB file leaves 3KB slack). Used for file recovery (e.g., forensic tools like foremost).

Real-World Example: Pathao’s Ride-Matching

• Problem: Frequent small file writes (ride logs, user data) cause fragmentation.
• Solution:
  • Pre-allocate disk space for logs (fallocate).
  • Use ext4 with larger block sizes (4KB) to reduce slack space overhead.

Exam Tip

1. Diagrams Are Mandatory:

   • Draw Gantt charts for scheduling (e.g., FCFS vs. SCAN).
   • Sketch disk allocation (contiguous vs. linked) with block numbers.
   • Show RAID configurations (e.g., RAID 10 with 4 disks).

2. Linux Commands:

   • Memorize chmod, chown, df, du, fdisk, mkfs.
   • Know permission octals: 755 (rwxr-xr-x), 644 (rw-r--r--).

3. Worked Examples:

   • Disk Scheduling: Always show head movement distances.
   • File Allocation: Calculate fragmentation (e.g., "After allocating 3 files of sizes 100B, 200B, 300B in contiguous blocks, what’s the remaining free space?").

4. Real-World Links:

   • eSewa: RAID 10 for payments, chmod 600 for security.
   • Daraz: Contiguous allocation for order logs, chmod 755 for scripts.
   • NTC: SCAN-like scheduling for fiber-optic routes.

5. Common Pitfalls:

   • FCFS vs. SSTF: FCFS is fair but slow; SSTF is fast but can starve far requests.
   • RAID 0 vs. RAID 1: RAID 0 is fast but not redundant; RAID 1 is safe but no speed gain.
   • Inodes vs. Filenames: A filename is a pointer to an inode, not the inode itself.

Pro Tip: For numerical questions (e.g., disk scheduling), always calculate total head movement and compare algorithms. For example:

"Given requests at 10, 50, 200 with head at 50, calculate total movement for FCFS and SSTF."

• FCFS: |50–10| + |10–50| + |50–200| = 40 + 40 + 150 = 230.
• SSTF: |50–10| + |10–50| + |50–200| = same as FCFS in this case (but differs if requests are 10, 200, 50).