Chapter 11: File System Implementation

File Structure
- Definition: A file is a logical storage unit that is a collection of related information.
- Location: File systems reside on secondary storage devices (e.g., disks).
- Function: Provides a user interface to storage, mapping logical data to physical storage locations.
File Control Block (FCB)
- Definition: A storage structure that contains metadata about a file, such as its size, permissions, and timestamps.
- Role: Acts as the main structure for file management.
Device Driver
- Function: Manages the communication between the operating system and physical storage devices.
Layered File System
- Structure:
- Application Programs
- Logical File System
- File-Organization Module
- Basic File System
- I/O Control
- Devices

System Calls and Implementation
- System calls are API-level instructions that need corresponding implementations within the file system.
- Structures involved:
- Boot Control Block: Contains information required to boot the operating system from storage.
  - Usually located in the first block of the volume if it hosts the OS.
- Volume Control Block: Includes volume details like:
  - Total number of blocks
  - Number of free blocks
  - Block size
  - Free block pointers or arrays
- Directory Structure: Organizes files by linking names to inode numbers (indices in the file table).
Per-file File Control Block
- Contains detailed information such as:
- inode number
- Access permissions
- Size of the file
- Timestamps for creation, last access, and modification.
- NTFS (New Technology File System): Utilizes a master file table that incorporates data structures from relational databases for file storage.

File Management Structures
- Two types of control for open files:
- Per-process Open-File Table: Stores file control blocks for files opened by a specific process.
- System-wide Open-File Table: Contains all open files in the system, accessible to all processes.

VFS on Unix
- A framework that provides an object-oriented approach to file system functionality:
- Offers a uniform system call interface (API) across different file systems.
- Decouples file system generic operations from implementation specifics, allowing various file system types including network file systems.
- Uses vnodes to encompass inodes or network file details that direct operations to the appropriate implementation routines.

Linear List of File Names
- Structure: A straightforward list of file names with pointers to their respective data blocks.
- Advantages: Simplicity in programming.
- Disadvantages: Time-consuming linear search unless organized (e.g., alphabetically via a linked list or using a B+ tree).
Hash Table
- Structure: A linear list enhanced by a hash data structure for faster searches.
- Issues: May experience collisions (when two file names hash to the same location) and is most efficient with fixed-size entries.

Contiguous Allocation
- Each file occupies a set of contiguous blocks.
- Pros: Best performance, simplicity (requires only the starting block number and length of the allocation).
- Cons: Challenges include finding suitable space, ensuring knowledge of file size, potential for external fragmentation, and the need for compaction.
- Mapping: Logical to physical conversion:
  - ext{Logical Address} = ext{LA}/512
  - Access block = Q + ext{starting address}
  - Displacement into block = R
Extent-Based Systems
- Modern file systems (like Veritas) that allocate blocks in contiguous extents (contiguous disk blocks).
- A file can consist of one or more extents.
Linked Allocation
- Each file is a linked list of blocks, with each block containing a pointer to the subsequent block.
- Advantages: No external fragmentation, reduction of necessity for compaction.
- Disadvantages: Potential reliability issues, inefficiency in locating blocks due to multiple I/O operations and disk seeks.
- FAT (File Allocation Table): A more streamlined method similar to linked allocation but provides better performance and caching.
Indexed Allocation
- Each file has its index block(s) containing pointers to its data blocks, allowing random access based on indexed pointers.

Free-Space List
- Function: Manages unoccupied disk space effectively.
Linked Free Space List on Disk
- A linked list representation that can efficiently allocate space, but may not provide contiguous space easily.
- Advantages: Maintains no waste of space.
Grouping and Counting Methods
- Grouping: Enhance linked lists to store addresses of numerous free blocks in conjunction with pointers to subsequent free blocks.
- Counting: Tracking contiguous free space usage, maintaining the address of the first free block, and counting all subsequent free blocks.

This chapter provides a comprehensive overview of file system implementation, detailing structures such as FCBs, allocation methods, and management techniques, essential for understanding how operating systems effectively handle file storage and retrieval.