File Management: Storage, Allocation, Directories & Linux FS

1. Overview of File Management

File management is the OS service that handles creation, deletion, reading, writing, and organization of files on secondary storage. It abstracts the physical disk into a hierarchical namespace, provides protection, and ensures data integrity.

Key responsibilities:

• File allocation – mapping logical file blocks to physical disk blocks.
• Directory management – organizing files into directories (folders).
• File attributes – storing metadata such as size, timestamps, permissions, and ownership.
• Access control – enforcing read/write/execute permissions.
• Recovery and consistency – using journaling or log‑based techniques.

2. File Allocation Methods

2.1 Linked List File System – Worked Example

Consider a disk with 10 blocks (0–9). A file F of 3 blocks is allocated using linked allocation.

1. Allocation

   • Block 2 → Block 5 → Block 8 → End.
   • FAT entry: 2 → 5 → 8 → -1.

2. Read Operation

   • Start at block 2.
   • Read data, follow pointer to 5.
   • Read data, follow pointer to 8.
   • End of file.

3. Write Operation

   • Append new block 9.
   • Update pointer of block 8 to 9.

Advantages

• No external fragmentation.
• Easy to extend file without moving existing blocks.

Disadvantages

• Random access requires traversing the list → O(n).
• Each block carries pointer overhead (typically 4 bytes).

3. File Attributes

File attributes are metadata that describe a file’s properties. Common attributes include:

3.1 Inode Structure (Linux example)

struct inode {
    uint32_t i_mode;      // File type & permissions
    uint32_t i_uid;       // Owner UID
    uint32_t i_gid;       // Owner GID
    uint32_t i_size;      // Size in bytes
    uint32_t i_atime;     // Last access time
    uint32_t i_mtime;     // Last modification time
    uint32_t i_ctime;     // Metadata change time
    uint32_t i_blocks;    // Number of 512‑byte blocks allocated
    uint32_t i_block[15]; // Direct, single/double/triple indirect pointers
    // ... other fields
};

The i_block array holds pointers to data blocks. The first 12 are direct pointers; the 13th is single indirect, 14th double, 15th triple.

4. Directory Implementation Techniques

Directories map file names to inodes. Two common techniques:

4.1 Single‑Level Directory

All files reside in one directory.

• Pros: Simple; fast lookup (hash or linear scan).
• Cons: Scalability issues; name collisions; no hierarchy.

4.2 Multi‑Level Directory (Tree)

Files organized in a hierarchical tree (root → sub‑directories).

• Pros: Logical grouping; avoids name collisions; scalable.
• Cons: Lookup requires traversing tree; more metadata overhead.

4.2.1 Directory Entry Format

4.2.2 Example: Unix‑style Directory Traversal

/ (root)
├── home
│   ├── alice
│   │   └── file.txt
│   └── bob
│       └── notes.doc
└── var
    └── log
        └── syslog

To access /home/alice/file.txt, the OS follows inode pointers: root → home → alice → file.txt.

5. Linux File System – ext4

5.1 Design Goals

• Scalability – support up to 1 EiB.
• Performance – fast allocation, journaling, delayed allocation.
• Reliability – journaling, checksums, extent trees.

5.2 Key Components

5.3 Extent Allocation – Worked Trace

Assume a file log.txt grows from 0 to 3 MiB.

1. Initial state – file size 0, inode has no extents.
2. First write (1 MiB)
   • Allocate extent: start block 1000, length 2048 blocks.
   • Update inode: extent tree node E1 = (1000, 2048).
3. Second write (1 MiB)
   • Allocate extent: start block 3000, length 2048.
   • Merge with previous? No, because non‑contiguous.
   • Inode now has two extents: E1 = (1000, 2048), E2 = (3000, 2048).
4. Third write (1 MiB)
   • Allocate extent: start block 5000, length 2048.
   • Inode now has three extents.

Benefits

• Reduces inode size compared to 15 block pointers.
• Faster sequential reads due to contiguous blocks.

5.4 Journaling Modes

6. Resource Allocation Graph (RAG) – File Locking Context

A RAG is a directed graph where vertices represent processes and resources (files). Edges represent requests or allocations.

• Request edge: Process → Resource (needs lock).
• Allocation edge: Resource → Process (currently holds lock).

6.1 Detecting Deadlock

A cycle in the graph indicates a potential deadlock.

• Example:
  • Process P1 requests file A → edge P1 → A.
  • Process P2 holds file A → edge A → P2.
  • Process P2 requests file B → edge P2 → B.
  • Process P1 holds file B → edge B → P1.
  • Cycle: P1 → A → P2 → B → P1.

6.2 Prevention Strategies

• Ordering: Impose a global order on file locks; always acquire in ascending order.
• Timeouts: Release lock if waiting too long.
• Deadlock detection: Periodically analyze RAG and abort one process.

7. Comparison of File Allocation Methods

8. Worked Example – File Creation in ext4

1. User creates report.doc

   • Kernel allocates inode number 1024.
   • Updates inode bitmap: mark block 1024 used.
   • Creates directory entry in /home/alice/ pointing to inode 1024.

2. User writes 2 MiB

   • Extent allocation: blocks 2000–4000.
   • Inode’s extent tree updated.
   • Block bitmap updated for blocks 2000–4000.

3. User deletes file

   • Directory entry removed.
   • Inode marked free in inode bitmap.
   • Blocks 2000–4000 freed in block bitmap.

9. Advantages & Disadvantages of Linked List File System

10. Exam Tip

• Understand the trade‑offs: Be able to compare allocation methods and directory structures in terms of fragmentation, access speed, and overhead.
• Trace examples: Practice walking through allocation/deallocation sequences for linked, indexed, and extent‑based systems.
• Know Linux specifics: ext4’s block groups, inode tables, extent trees, and journaling modes are frequent exam topics.
• Resource Allocation Graphs: Draw a RAG for a given scenario and identify cycles; explain prevention or detection strategies.
• Past question patterns:
  • Advantages/disadvantages of linked list FS → list pros/cons succinctly.
  • File attributes → define each attribute and show where stored.
  • Directory implementation → detail single vs multi‑level, include a sample directory entry format.

By mastering these concepts and practicing the worked examples, you’ll be well prepared for the Unit 5 exam.