M10-OS File Systems Support

CS 439 Principles of Computing Systems

1. Disk Cache

• Main Memory Buffer: Serves as a temporary storage area containing the most recently accessed disk sectors to enhance access speed.

• Cache Organization: Arranged by blocks to optimize data retrieval, enabling quicker access to frequently used data segments.

• File Block Size Consideration: It is crucial to evaluate the trade-offs of having a file block size equal to the page size or multiple of it, affecting performance and efficiency.

• Access Efficiency: Utilizes a hash table structure for achieving constant time (O(1)) access to disk sectors, significantly improving retrieval times.

• Cache Replacement Algorithm: Implements LRU (Least Recently Used) strategy to replace cache blocks to maintain optimal cache performance by evicting the least recently accessed items.

• Memory Competition: Disk cache must compete for memory resources with user processes and the kernel, necessitating efficient memory management strategies to ensure system performance.

• Cache Size Variability: Some systems are designed to allow variable cache sizes; blocks may be dynamically allocated from the main memory list based on workload requirements.

2. Cache Operation: Read

• Read Process: The sequence includes the following steps:

  1. Check Cache: Determine whether the requested sector is present in the cache.

  2. Copy Data: If the data is available, it is copied from the cache; if not, a free cache block must be located.

  3. Free Block Availability: If no free cache blocks are available:

     • Use LRU order to select which block to replace.

     • If the selected block has modified data, it must be written back to the disk before being overwritten.

  4. Schedule Read: Initiate a read from the designated disk sector into the newly freed cache block.

  5. Final Copy: Once completed, again copy the data from the cache to the user's request context.

3. Cache Operation: Write

• Write Policies:

  • Write Through: This approach ensures that data is written simultaneously to both cache and disk, providing immediate consistency.

  • Write Back (or Write Behind): If the sector exists in the cache, data is written directly to it; otherwise, a new frame is allocated in cache and updated. A write operation to the disk is scheduled as necessary for write-through scenarios.

4. Data Structures

• Key Structures:

  • Hash Table: Supports quick access to cache entries.

  • Cache Blocks: Stores data temporarily until it can be committed to disk.

  • Free Block List: Keeps track of unallocated cache blocks.

  • LRU List: Maintains order of cache blocks to facilitate LRU replacement strategy.

5. Cache Block Bits

• Block Attributes:

  • M: Modified flag indicating that the block has been changed but not yet written to the disk.

  • B: Busy flag shows that the block is currently involved in an I/O operation.

  • S: Semaphore, utilized in multithreaded kernels to manage concurrent access.

  • U: Used bit reflects whether the block is currently in use.

6. Additional File System Structures

• File System Operation Management: Orchestrates tracking of open files globally or per process, enhancing overall efficiency.

• Concurrency Control Information: Supports safe access by maintaining information regarding file usage across multiple processes.

• Seamless Client File Access: Allows users to access files transparently regardless of their physical location in the system.

• Resource Usage Management: Implements quotas to prevent excessive resource consumption.

• Memory-Mapped Files: Supports unconventional access methods allowing applications to map files directly into process memory for enhanced performance.

7. Per-Process Open File Table

• Table Allocation: Allocates an entry for each process’s active open files.

  • Entry Contents: Includes current read/write pointer tracking, access mode (read/write/append), and index to a global open file table for concrete file details.

8. Global File Table

• System-wide Table: Contains an entry for each open file across the system.

  • Entry Contents: Comprises methods to locate files (e.g., pointers to inodes), information whether files are text or binary, the count of processes accessing the file, concurrency control metrics (like read/write locks), and detailed permission settings.

9. Concurrency Control Information

• Simultaneous Access Issues: Identifies potential conflicts in file access, including:

  • Read-Write Conflicts

  • Write-Write Conflicts

  • Write-Read Conflicts

10. Solutions

• Synchronization Methods:

  • Do Nothing: Places the onus of synchronizing applications on the developer.

  • Advisory Locks: Require dual calls (lock/unlock) for read/write operations, independent of specific files.

  • Real Locks: Enforce a locking mechanism, verifying operations against locks to ensure safe sharing between independent processes; however, this introduces system overhead and increased complexity.

11. Seamless File Access

• File System Namespace: Can be configured to span various disks and machines. It necessitates file system reorganization on a disk or over machines.

• User Awareness: Ideally, users should be shielded from underlying complexities of these operations.

12. File System Mounting

• Mount Points Concept: Establishes a structured approach to accessing different file systems, simplifying user interaction with complex back-end file management.

13. Logical Volumes

• Device Abstraction: Dissociates the notion of physical disks, presenting an array of blocks instead.

  • Logical Volume Manager (LVM): Optimizes access and performance across stored abstractions, supporting logical volumes that may extend across multiple disks and incorporate replication or resizing capabilities.

14. Virtual Node Layer

• Core Functionality: Serves as an abstract representation of file locations, analogous to inodes, improving client access to file systems.

15. Quotas

• Purpose: A critical mechanism for controlling and accounting storage usage.

  • UNIX Example: Administrators can impose limits on the number of files per user or total disk space utilized with soft or hard variants on each limit.

16. Quota Operation

• Soft Limit Behavior: Users can temporarily exceed soft limits but are notified with warnings; accounts risk being disabled after repeated violations.

• Hard Limits: Strict upper limits that users cannot surpass, ensuring system integrity.

17. Quota Implementation

• Data Structure Arrangement: Involves a Global Open File Table and a user quota table, which contains tracked numbers and limits relevant to storage usage. All file creation and appending actions necessitate validation against the user quota table.

18. Memory-Mapped Files

• Mapping Interface: Maps files directly into user space, bypassing traditional file handling mechanisms, streamlining operations.

• Advantages: Offers flexibility for handling complex data structures on disk and delivers enhanced performance by minimizing data copying overhead. Facilitates resource sharing with lower administrative burdens as compared to conventional methods.

19. Implementation Issues

• Challenges: Involves managing consistency between standard and mapped access methodologies, addressing necessary updates across multiple processes mapping identical files simultaneously, and enforcing locking mechanisms while handling potential truncations during the mapping process.

20. A Solution

• System Management Mechanisms: Use a strategic combination of a process page table, hash table, and cache blocks to consistently manage file operations and ensure reliable access coordination.

21. Possible Restrictions

• Alignment Requirements: File blocks must be aligned with page boundaries in both disk caches and process maps to avoid operational anomalies.

• Growth/Shrinkage Considerations: Adjustments to mappings do not immediately reflect changes on process maps to prevent stale data usage, ensuring data integrity across sessions.

• Mapping Modes for Processes: Permit the utilization of private or shared mappings, including anonymous regions, allowing independent access strategies as needed.