Operating Systems: File System Implementation Flashcards
What role do disks play in the file-system structure?
Serve as the primary medium for file system storage
Support both random access and sequential access
Provide the physical basis onto which logical file systems are mapped
What are the two independent design challenges in file systems?
Determining how the file system should appear to the user
Designing algorithms and data structures to map the logical file system to physical storage
How does a layered approach benefit file system implementation?
Separates user-level file access from low-level disk operations
Enhances efficiency by organizing responsibilities into distinct layers
Allows for independent evolution of file-system components
What are the layers in the layered file system diagram?
What are the layers in the layered file system diagram?
Describe the four layers involved in a file system’s design.
Logical File System:
Manages metadata, protection, and path resolution
File Organisation Module:
Maps logical file names to physical disk blocks
Tracks and allocates free space/blocks
Basic File System:
Performs low-level disk operations (e.g., reading/writing blocks)
I/O Control:
Coordinates communications between the file system and I/O devices
Optimizes throughput and minimizes latency
What are the key on-disk data structures in a file system?
Boot Control Block: Stores boot-related information
Volume Control Block: Contains details such as total blocks and free blocks
Directory Structure: Organizes file names and metadata pointers
File Control Block (FCB): Holds file metadata (e.g., permissions, ownership, location)
What information is typically stored in a File Control Block (FCB)?
File permissions
File dates (creation, access, write)
File owner, group, and access control list (ACL) details
File size
Data blocks or pointers to file data blocks
What are the main in-memory data structures used in file system implementation?
Mount Table: Tracks mounted volumes
Directory Cache: Accelerates directory lookups by reducing disk I/O
Open File Tables:
System-wide table for open files
Per-process tables for file descriptors
What purpose does the Mount Table serve in memory?
Keeps track of which volumes are currently mounted
Enables efficient management and access of multiple file systems
How does a Directory Cache improve file system performance?
Reduces the need for repetitive disk I/O during directory lookups
Enhances responsiveness for frequently accessed directories
What concept is illustrated by in-memory file system structure diagrams?
The interaction between kernel memory and user space
Maintenance of directory structures, file control blocks, and open file tables
The flow from secondary storage to active file operations
What are the key considerations regarding partitions and mounting?
Partitions may be “cooked” (with an existing file system) or raw (a sequence of blocks)
The boot block can point to a boot volume or to a separate boot loader
The root partition contains the OS and must be mounted at boot time
During mounting, file system consistency is checked and corrected if necessary
What is the purpose of the Virtual File System (VFS) in modern operating systems?
Provides a unified API for multiple file system types
Hides the complexity of handling different disk formats and network file systems
Enables seamless file access across various storage devices
Which file systems are commonly supported by VFS?
EXT (e.g., ext4 for Linux)
NTFS for Windows
APFS for macOS and iOS
FAT for removable drives and embedded systems
Outline the three layers of the VFS design.
File-System Interface (Top Layer):
Implements system calls such as open(), read(), write(), and close()
VFS Interface Layer (Middle Layer):
Defines standard objects and operations using vnode structures
Actual File-System Implementations (Bottom Layer):
Contains file-system-specific drivers (e.g., ext4, NTFS, NFS) that implement the VFS functions
What is the role of the schematic view of the Virtual File System?
Demonstrates how local and remote file systems are integrated via the VFS
Illustrates the abstraction layer that decouples application calls from hardware specifics
What are the two primary directory structures used in file systems?
Linear List
Hash Table
What are the characteristics of a Linear List directory structure?
Each directory entry contains a file name and a pointer to file metadata
Searching requires a full linear scan, resulting in O(n) time complexity
Simple implementation but inefficient for large directories
What are the advantages and challenges of using a Hash Table for directory implementation?
Advantages:
Provides O(1) average time complexity for lookup, insertion, and deletion
Challenges:
Requires a well-designed hash function
Must incorporate collision resolution techniques such as chaining
What is a Linear List directory structure?
A simple directory structure where each entry contains a file name and a pointer to file metadata.
Searching requires scanning the entire list (O(n) time complexity).
Simple to implement but inefficient for large directories.
What is a Hash Table directory structure and what are its key characteristics?
Uses a hash function to map file names to indexes.
Offers O(1) average time complexity for lookup, insertion, and deletion.
Requires a well-designed hash function and collision resolution techniques (e.g., chaining)
What are the three main file allocation methods used by file systems?
Contiguous Allocation
Linked Allocation
Indexed Allocation
How does Contiguous Disk Space Allocation work and what are its drawbacks?
Each file occupies a set of contiguous blocks on the disk.
Requires only the starting block and length to manage a file.
Drawbacks include difficulty in finding space, external fragmentation, and the potential need for compaction (either off-line or on-line).
What is Modified Contiguous Allocation and how do modern file systems use it?
Uses extent-based allocation where an extent is a contiguous set of disk blocks.
Extents are allocated based on the file’s expected size.
A file may consist of one or more extents, and if free space follows the current extent, it is extended; otherwise, a new extent is created and linked.
Used in file systems like ext4 (Linux) and NTFS (Windows).
