File Systems, Secondary Storage, and Disk Scheduling

Operating systems must manage persistent storage, input/output (I/O) hardware, and high-speed memory caching efficiently. This chapter covers directory structures, file allocation methods, I/O management and direct memory access (DMA), disk architecture and scheduling algorithms, cache memory hierarchies, and system security.

1. Directory Structures in File Systems

A file system organizes files on secondary storage using directory structures. The evolution of directory structures ranges from simple flat hierarchies to complex graph-based models.

Structure & Concept Flow

Single-Level Two-Level Tree Structure General Graph

[Root Directory] [User 1] [User 2] [Root] [Root]

- file1.txt - f1.txt - f3.txt +-- /bin +-- dir1 <---+

- file2.txt - f2.txt - f4.txt +-- /home | |

| +-- user1 +-- dir2 ----+

| +-- docs (Shared links)

Single-Level Directory: All files are contained within a single directory.
- Limitation: Name collisions occur frequently since no two files can share the same name, making it completely unviable for multi-user or large-scale systems.
Two-Level Directory: Introduces a separate directory for each user.
- Benefit: Users have isolated namespaces, preventing name conflicts between different users, though users cannot easily share files.
Tree-Structured Directory: The standard hierarchical model used by modern operating systems (Windows, Linux, macOS).
- Benefit: Directories can contain subdirectories and files, creating a clean path-based traversal model (e.g., /home/user1/docs/notes.txt).
Acyclic-Graph Directory: Extends the tree structure by allowing directories and files to have shared links (aliases or symbolic links).
- Challenge: Requires careful garbage collection and reference counting to prevent dangling pointers when a shared file is deleted.
General Graph Directory: Allows cycles in the directory graph.
- Challenge: Requires complex garbage collection algorithms and cycle detection mechanisms to prevent infinite loops during file traversal.

2. File Allocation Methods

When storing files on disk blocks, the operating system must decide how to allocate disk space. There are three primary allocation strategies:

Allocation Method	Core Mechanism	Direct Access Support	External Fragmentation	Key Vulnerability
Contiguous Allocation	Each file occupies a set of contiguous blocks on disk.	Excellent ( $O(1)$ lookup via starting address + offset).	High (leads to free-space holes over time).	File growth is difficult if adjacent space is occupied.
Linked Allocation	Each file is a linked list of disk blocks, where each block contains a pointer to the next.	Poor / Sequential only ( $O(N)$ traversal).	None (any free block can be utilized).	Pointer overhead; broken pointer risks losing subsequent blocks.
Indexed Allocation	All pointers for a file are gathered into a dedicated Index Block.	Excellent (index block maps direct pointers).	Low / Minimal internal fragmentation.	Overhead of index block for small files; large files require multi-level indexing.

3. I/O Management and Device Drivers

Input/Output management is a critical OS responsibility. The OS must manage device drivers (for mice, keyboards, displays) securely without letting user programs compromise hardware stability or bypass memory access protections.

Core I/O Mechanisms

Polling (Busy-Waiting):
- The CPU continuously checks the status register of the I/O device in a tight loop to see if data is ready.
- Trade-off: Extremely simple to implement, but wastes significant CPU cycles polling idle devices.
Direct Memory Access (DMA):
- A specialized hardware controller (DMA Controller) handles data transfers between I/O devices and main memory directly, bypassing the CPU.
- Flow: CPU initializes the DMA transfer parameters (source, destination, byte count) $\rightarrow$ CPU continues executing other tasks $\rightarrow$ DMA controller moves data $\rightarrow$ DMA raises a hardware interrupt upon completion.
Buffering:
- Using a temporary memory area in RAM to hold I/O data while transferring between devices and applications. Types include Single Buffering, Double Buffering (Ping-Pong buffering), and Circular Buffering.
Spooling (Simultaneous Peripheral Operations On-Line):
- Data is held in temporary storage (typically on disk) so that a slower peripheral device (like a printer) can access it at its own pace.
- Example: Print spooling allows multiple applications to submit print jobs instantly without waiting for the physical printer to finish prior jobs.

4. Hardware Bus Architecture & Master-Slave Interfaces

Inside computer hardware, data flows across system buses coordinated by master and slave interfaces:

Structure & Concept Flow

[CPU (Master)] <=======================> [System Bus] <=======================> [Memory (Slave)]

^ ^

| |

+=============================== [DMA Controller (Master/Slave)] <------------------+

[Peripheral Units (I/O)]

Master Interface: A device component (such as the CPU or DMA Controller) that can initiate and control bus transactions (read/write requests).
Slave Interface: A device component (such as RAM chips or peripheral registers) that responds to requests made by bus masters.
DMA Controller Role: Acts as a bus master when moving data directly between I/O peripherals and main memory, freeing the CPU from routine byte-copying overhead.

5. Disk Structure and Geometry

Secondary storage (HDD) mechanical architecture relies on precise physical positioning components:

Platter: Circular magnetic disk coated with storage media. Disks typically have multiple platters stacked vertically.
Tracks: Concentric circles on a platter surface where data is recorded.
Sectors: The smallest allocatable unit of a disk track (typically 512 bytes or 4KB).
Cylinders: The collection of tracks of the same radius across all stacked platters, forming a vertical cylinder shape.
Read/Write Head: Electromagnetic transducer hovering just above the platter surface to read or write magnetic flux changes.

6. Disk Scheduling Algorithms

When multiple I/O requests queue up for disk access, disk scheduling algorithms reorder the requests to minimize mechanical head movement (seek time).

First-Come, First-Served (FCFS):
- Requests are serviced strictly in the order they arrive.
- Pros: Fair and simple.
- Cons: Wild head movements cause high average seek times.
Shortest Seek Time First (SSTF):
- Services the request closest to the current head position first.
- Pros: Dramatically reduces seek time compared to FCFS.
- Cons: Can cause starvation for requests located at distant tracks if continuous requests arrive near the head.

Note: Advanced algorithms like SCAN (Elevator), C-SCAN, LOOK, and C-LOOK further refine disk scheduling by enforcing directional sweeps across disk cylinders, eliminating starvation while maintaining high throughput.

7. Storage and Cache Hierarchy

To bridge the speed gap between the ultra-fast CPU and slower main memory (RAM), modern computer architectures employ a multi-level cache hierarchy.

CODE

[CPU Core Registers] (Fastest, 0 cycle latency)
        |
[L1 Cache] (~1-2 ns)
        |
[L2 Cache] (~3-10 ns)
        |
[L3 Cache (Shared)] (~20-40 ns)
        |
[Main Memory (RAM)] (~50-100 ns)
        |
[Secondary Storage (SSD/HDD)] (Slowest, milliseconds)

Cache Hit vs. Cache Miss

Cache Hit: Requested data is found within the cache memory level, allowing lightning-fast retrieval.
Cache Miss: Requested data is absent from the cache, forcing the system to fetch it from a slower backing store (e.g., RAM or Disk) and load it into the cache.

Average Memory Access Time (AMAT) Formula

The average time required to access memory given a cache hit ratio is expressed as:

\begin{aligned} \text{AMAT} &= t_{\text{hit}} + (1 - h) \times t_{\text{miss}} \end{aligned}

Where:

$t_{\text{hit}}$ = Time to access cache (Hit latency)
$h$ = Cache hit ratio ( $0 \le h \le 1$ )
$t_{\text{miss}}$ = Miss penalty (Time required to fetch data from lower memory tier)

8. Protection and Security in Operating Systems

Operating systems enforce resource isolation and security to prevent unauthorized access and privilege escalation.

Authentication vs. Authorization:
- Authentication: Verifying who the user is (e.g., passwords, multi-factor authentication, biometric tokens).
- Authorization: Determining what resources and permissions an authenticated user can access (Read, Write, Execute).
Access Control Lists (ACLs):
- Associated with files and directories, ACLs specify exact permissions granted to individual users or user groups.
- In Unix-like systems, file permissions are traditionally structured into three distinct categories (Owner, Group, Others), with read (r), write (w), and execute (x) permission bitmasks.

Summary and Key Takeaways

Hierarchical Directories: Modern file systems rely on tree structures to organize files and folders efficiently without naming collisions.
Allocation Trade-offs: Contiguous allocation provides fast direct access but suffers from fragmentation; linked allocation avoids fragmentation but lacks direct access; indexed allocation balances access speed using dedicated index blocks.
Polling vs. DMA: Polling wastes CPU cycles through active waiting, whereas Direct Memory Access (DMA) offloads bulk data transfers to a dedicated hardware controller.
Spooling Utility: Spooling buffers output data on disk so slower peripheral devices (like printers) can process jobs sequentially without blocking applications.
Disk Scheduling: Algorithms like FCFS and SSTF manage disk arm movement to minimize mechanical seek latency and optimize I/O throughput.
Cache Hierarchy: L1, L2, and L3 caches placed between the CPU and RAM leverage locality of reference to drastically reduce average memory access latency.
AMAT Metric: Average Memory Access Time combines hit latency and miss penalty weighted by hit/miss probabilities.
Access Control: Operating systems enforce security via authentication, authorization, and Access Control Lists (ACLs) to safeguard file system resources.