File Systems

A file system is the method and data structure an operating system uses to organize and store files on storage devices.

What is a File?

A file is a named collection of related information recorded on secondary storage. It is the smallest logical unit of secondary storage.

File Attributes

File Operations

Open File Table

• When file is opened, OS maintains information in tables:
  • Per-process table: Files open by that process
  • System-wide table: All open files in system
• Contains: File pointer, access rights, location, open count

File Types

By Extension

By Structure

Access Methods

Sequential Access

• Read/write in order, one record after another
• Most common method
• Example: Tape drives, log files

Beginning ──────────────────► End
           Read/Write
           ────────►

Direct (Random) Access

• Read/write records in any order
• File viewed as numbered sequence of blocks
• Example: Databases

Read block n
Write block m
Read block k

Indexed Access

• Index contains pointers to file blocks
• Search index, then access data directly
• Example: Database indexes

Directory Structure

A directory is a container for organizing files.

Single-Level Directory

┌─────────────────────────────────────┐
│              Directory              │
├──────┬──────┬──────┬──────┬─────────┤
│file1 │file2 │file3 │file4 │  ...    │
└──────┴──────┴──────┴──────┴─────────┘

Problems:

• Naming conflicts
• Grouping not possible
• Doesn't scale

Two-Level Directory

┌─────────────────────────────────────┐
│         Master File Directory       │
├─────────────────┬───────────────────┤
│      User1      │       User2       │
├─────────────────┼───────────────────┤
│file1 file2 file3│ fileA fileB fileC │
└─────────────────┴───────────────────┘

Advantages:

• Different users can have same file names
• Better organization
  Disadvantages:
• No subdirectories within user
• No file sharing mechanism

Tree-Structured Directory

Features:

• Arbitrary depth nesting
• Absolute and relative paths
• Current (.) and parent (..) directories

Acyclic-Graph Directory

• Allows sharing of files/directories
• Multiple paths to same file
• Uses links (hard links, symbolic links)
• Must handle dangling references

General Graph Directory

• Allows cycles
• Requires garbage collection
• More complex traversal algorithms

File Allocation Methods

How file blocks are allocated on disk.

1. Contiguous Allocation

All blocks of file are stored together.

┌────┬────┬────┬────┬────┬────┬────┬────┐
│ F1 │ F1 │ F1 │    │ F2 │ F2 │    │    │
└────┴────┴────┴────┴────┴────┴────┴────┘
 0    1    2    3    4    5    6    7

Directory Entry: (Start block, Length)

2. Linked Allocation

Each block contains pointer to next block.

Directory Entry: (Start block, End block)

FAT (File Allocation Table)

• Variation of linked allocation
• All pointers stored in separate table (FAT)
• FAT cached in memory for faster access

┌─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │  5  │ Block
├─────┼─────┼─────┼─────┼─────┼─────┤
│ eof │  3  │  -  │  5  │  -  │ eof │ FAT Entry
└─────┴─────┴─────┴─────┴─────┴─────┘
File: 1 → 3 → 5 → eof

3. Indexed Allocation

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

Directory Entry: (Index block number)

Multi-Level Index

For larger files, use multiple levels of index blocks.

Combined Scheme (Unix Inode)

Free Space Management

How to track free blocks on disk.

1. Bit Vector (Bitmap)

Each bit represents a block (1 = free, 0 = allocated).

Block:  0 1 2 3 4 5 6 7 8 9 ...
Bitmap: 0 0 1 1 0 1 0 0 1 1 ...
        (Blocks 2, 3, 5, 8, 9 are free)

Pros: Simple, efficient for finding contiguous blocks
Cons: Bitmap size grows with disk size

2. Linked List

Link all free blocks together.

Pros: No wasted space
Cons: Slow for finding contiguous blocks

3. Grouping

First free block contains addresses of n free blocks.

Block 2: [3, 5, 8, 9, 15, 20, ...]
         └── Last one points to next group

4. Counting

Keep (starting block, count) pairs for contiguous free regions.

(2, 3)  → Blocks 2, 3, 4 are free
(8, 5)  → Blocks 8, 9, 10, 11, 12 are free

File System Implementation

Boot Block

• First block(s) of partition
• Contains code to bootstrap OS
• Also called boot sector or MBR

Superblock

• Contains critical file system metadata:
  • Total blocks
  • Free blocks
  • Block size
  • Inode count
  • Mount status

Inode Area

• Array of inodes
• Each inode represents one file

Data Blocks

• Actual file content
• Directory content

Directory Implementation

Linear List

• List of (file name, pointer) entries
• Simple to implement
• Slow search O(n)

Hash Table

• Hash function on file name
• O(1) average lookup
• Must handle collisions
• Fixed size issues

B-Tree

• Balanced tree structure
• O(log n) operations
• Used by modern file systems (NTFS, HFS+)

File System Types

Journaling File Systems

A journal (log) records changes before they're applied to main file system.

Types of Journaling

Journal Recovery

1. On crash, check journal
2. Replay uncommitted transactions
3. Rollback incomplete transactions
4. File system consistent