****************************************
Chapter 12: File-System Implementation
****************************************

File-System Structure
========================

A file system is typically stored on disk using a layered structure:

1. **Boot Block**  
   Contains code to boot the OS.

2. **Superblock / File-System Control Block**  
   Holds metadata: size, number of blocks, free space, and layout.

3. **Inode Table / File-Control Blocks (FCBs)**  
   Stores per-file metadata.

4. **Data Blocks**  
   Contain actual file data.

5. **Directory Structure**  
   Maps file names to inodes/FCBs.

The OS uses in-memory structures such as caches, directory caches, buffer caches,
and file tables to improve performance.


Allocation Methods
======================

Contiguous Allocation
-------------------------

- **Description:** Files occupy a contiguous range of blocks.
- **Advantages:**
  - Fast sequential and direct access.
  - Simple to implement.
- **Disadvantages:**
  - External fragmentation.
  - Hard to grow files dynamically.


Linked Allocation
--------------------

- **Description:** Each block stores a pointer to the next block.
- **Advantages:**
  - No external fragmentation.
  - Easy file growth.
- **Disadvantages:**
  - No efficient direct access.
  - Reliability issues (pointer corruption).


Indexed Allocation
---------------------

- **Description:** An index block contains all pointers to the file's blocks.
- **Advantages:**
  - Supports direct access.
  - Avoids external fragmentation.
- **Disadvantages:**
  - Index block must be large enough.
  - For big files, may need multilevel indexing (e.g., UNIX inodes).


Free-Space Management
========================

Techniques used to track unused blocks:

Bitmaps (Bit Vectors)
-----------------------

- Each block represented by 1 (free) or 0 (allocated).
- **Advantages:** Compact, fast to search.
- **Disadvantages:** Bitmap must be held in memory for efficiency.

Free Lists (Linked Lists)
----------------------------

- Free blocks linked together.
- **Advantages:** Simple.
- **Disadvantages:** Slow for large file systems.

Grouping
----------

- First free block stores addresses of several free blocks.
- Reduces traversal overhead.

Counting
----------

- Tracks free blocks in runs (start block + count).
- Efficient for systems with contiguous free space.

Space Maps
------------

- Used in advanced file systems such as ZFS.
- Log-structured metadata for efficient free space tracking.