Virtual Memory and Disk Storage Systems

Posted on Dec 31, 2025 in Computers

Virtual Memory Fundamentals

Virtual memory provides the separation of user logical memory and physical memory.

• Only part of the program needs to be in memory for execution; therefore, the logical address space is greater than the physical address space.
• It allows address spaces to be shared by multiple processes, which results in less swapping.
• It allows pages to be shared during fork(), leading to faster process creation.

Page Fault Mechanisms

A page fault occurs the first time there is a reference to a specific page, which traps to the Operating System (OS).

The OS must decide whether to:

• Abort: If the reference is invalid.
• Load the page: If the reference is valid but the page is not yet in memory.

Steps to resolve a page fault:

1. Get an empty frame.
2. Swap the required page into that frame.
3. Update the page table to mark the page as “in memory” (set the valid bit).
4. Restart the instruction that caused the page fault.

If an instruction accesses multiple nearby pages, the cost is lower due to the principle of locality of reference.

Demand Paging and Performance

Demand paging brings a page into memory only when needed, which reduces I/O and memory usage.

• Lazy swapper: This mechanism never swaps a page into memory unless that page will be used.
• This strategy could result in many page faults.

Performance Calculation:

EAT = [(1 − p) × memory access time] + [p × (page fault overhead + swap out + swap in + restart)]

Where p = page fault rate (0 ≤ p ≤ 1):

• If p = 0, there are no page faults.
• If p = 1, every reference is a fault.

Performance can be improved by preloading the process image into swap space at process load time.

Pure Demand Paging

In pure demand paging, a process starts with no pages in memory. Pages are loaded one by one only as they are referenced.

Copy-on-Write (COW)

Copy-on-Write (COW) allows parent and child processes to initially share the same physical pages after a fork() operation.

• When either process modifies a shared page, a copy is made for that specific process.
• This greatly reduces memory usage and speeds up process creation.

Modify (Dirty) Bit

The modify bit (or dirty bit) indicates whether a page has been modified since it was loaded.

• Only pages marked as dirty are written back to disk upon replacement, which reduces unnecessary writes.
• When replacing a page:
  • If the page is dirty, write it to disk first.
  • Then, swap in the desired page.

Page Replacement Algorithms

When physical memory is full, the OS must choose which page to replace.

• FIFO (First-In, First-Out): Replaces the oldest loaded page.
• LRU (Least Recently Used): Replaces the page that has not been used for the longest period of time.
• Second Chance (Clock Algorithm): Gives pages with recent use (reference bit = 1) a “second chance.”
• Optimal Algorithm (Theoretical): Replaces the page that will not be used for the longest time in the future.

Page Replacement and Frame Allocation

LRU (Least Recently Used) Implementation

• A stack can be used to record the most recent page references; therefore, LRU is considered a “stack algorithm.”
• Pages closer to the top are the most recently used.
• This is easy to update on each memory access.

Second-Chance (Clock) Algorithm

• Uses a reference bit to give pages a “second chance” before replacement.
• If the reference bit = 1, the system gives a second chance (sets the bit to 0 and skips it).
• If the reference bit = 0, the system replaces that page next.
• This is visualized as a circular buffer (“clock hand”) rotating through frames.

Frame Allocation Strategies

Fixed Page Allocation and Proportional Allocation

Allocate frames to each process proportional to its size:

• Let sᵢ = size of process Pᵢ
• Let S = Σ sᵢ (sum of all process sizes)
• Let m = total number of frames
• Then aᵢ = (sᵢ / S) × m

Larger processes get proportionally more frames.

Global vs Local Replacement

Page-Fault Rate and Thrashing

• When a process does not have enough pages in memory, the page-fault rate spikes.
• Thrashing: A process spends most of its time swapping pages in and out instead of executing instructions, causing CPU utilization to plummet.
• This is often caused by overcommitting memory or allocating too few frames per process.

Memory-Mapped File I/O

• Treats file I/O as routine memory access.
• Maps disk blocks directly to pages in memory.
• This simplifies file operations by removing the need for explicit read/write calls.

I/O Interlock

• Certain pages must be locked in memory (non-swappable) during active I/O operations.
• This prevents device I/O errors or page faults during the read/write process.

Magnetic Disk Structure

• Provides bulk secondary storage.
• Disks rotate at 60–250 times per second.
• Transfer rate: The speed at which data moves between the drive and the computer.
• Positioning time (random-access time): Consists of Seek time (moving the arm to the cylinder) plus Rotational latency (waiting for the sector).
• Head crash: Occurs when the disk head physically contacts the disk surface, causing catastrophic damage.

Disk Attachment and Communication

• Drives attach via I/O buses such as EIDE, ATA, SATA, and USB.
• A host controller communicates with the disk controller over the bus.
• Access latency = average seek time + average rotational latency.
  • Fast: ~5 ms | Slow: ~14.5 ms
• Average I/O Time = Avg access time + (data size / transfer rate) + controller overhead.
• Example: A 4 KB block @ 7200 RPM, 5 ms seek, 1 Gb/s transfer rate, and 0.1 ms overhead results in approximately 9.39 ms total.

Disk Organization

A disk is viewed as a 1-dimensional array of logical blocks, which are sequentially mapped to physical sectors on the platters.

Storage Connection Types

• Host-Attached Storage: Accessed through local I/O ports (bus-connected).
• Storage Area Network (SAN): Connects multiple hosts to multiple storage units. This is common in enterprise data centers and uses LUN masking to restrict storage access to specific servers.
• Network-Attached Storage (NAS): Provides file-level access via network protocols such as NFS or SMB.

Disk Scheduling Algorithms

The primary goal of disk scheduling is to minimize seek time, which is proportional to the seek distance. Bandwidth is the total bytes transferred divided by the total elapsed time.

Sources of I/O requests include the OS, system daemons, and user processes. The OS maintains per-device request queues.

Disk Structure and Management

• Low-level (physical) formatting: Divides the disk into 512-byte sectors that the controller can read and write.
• Partitioning: Divides the disk into logical sections (cylinders converted to logical disks).
• Logical formatting: Creates a file system within each partition.
• Clusters: Groups of blocks used to improve efficiency.
• Boot block: Contains the bootstrap loader which initializes the OS on startup.

Swap Space Management

• Used by virtual memory as an extension of main memory.
• The kernel tracks swap usage using swap maps.

RAID: Redundant Array of Independent Disks

RAID combines multiple disks to improve reliability and performance, increasing the Mean Time to Failure (MTTF).

• RAID 0 – Striping: Focuses on performance only with no redundancy.
• RAID 1 – Mirroring: Duplicates each disk for redundancy.
• RAID 10 (1+0): Striped mirrors providing high speed and redundancy.
• RAID 01 (0+1): Mirrored stripes; similar to RAID 10 but less robust.
• RAID 4/5/6 – Parity: Block-interleaved parity that saves space while remaining fault-tolerant.
• ZFS (Solaris): Adds checksums for all data and metadata to detect corruption and ensure integrity.

Tertiary Storage Systems

• Built using removable media such as optical discs or tapes.
• Available in WORM (Write Once, Read Many) or Read-only formats.
• These are managed similarly to fixed disks, though fixed disks are typically more reliable.
• Main memory remains faster but more expensive than disk storage.