Chapter 9: Virtual Memory

Overview

Virtual memory allows a system to execute processes that may not be completely in main memory. It provides an abstraction that gives each process the illusion of having a large, continuous address space.

Goals: - Efficient memory utilization - Process isolation and protection - Ability to run large programs - Support for multitasking and increased CPU utilization

Background

  • Physical memory is limited; virtual memory expands it by using disk space.

  • The logical address space is larger than the physical address space.

  • The Memory Management Unit (MMU) translates virtual addresses to physical addresses at runtime.

  • Virtual memory enables partial loading of processes — only the needed parts (pages) are kept in RAM.

Benefits

  • Allows more processes to run simultaneously.

  • Simplifies program development (no need to manage limited memory manually).

  • Enables sharing and protection of memory.

Demand Paging

Definition

  • A technique where pages are loaded into memory only when needed during program execution.

Key Concepts

  • Page fault: Occurs when a page referenced by a process is not in memory.

  • Valid-invalid bit: Used to indicate if a page is in memory (valid) or not (invalid).

Steps in Handling a Page Fault

  1. Check if the address is valid.

  2. Locate the required page on disk.

  3. Find a free frame in physical memory.

  4. Load the page into the free frame.

  5. Update the page table.

  6. Restart the instruction that caused the fault.

Performance

  • Effective Access Time (EAT):

    EAT = (1 - p) * memory_access_time + p * page_fault_time

    where p = probability of page fault.

  • Lower page-fault rate ⇒ better performance.

Copy-on-Write (COW)

Definition

  • An optimization strategy where parent and child processes initially share the same memory pages.

How It Works

  • Upon a fork() system call, both processes share pages marked as read-only.

  • When one process modifies a page, a copy is made (hence “copy-on-write”).

  • Reduces memory usage and process creation time.

Advantages

  • Efficient process creation.

  • Minimizes unnecessary duplication.

  • Increases overall system performance.

Page Replacement Algorithms

When a page fault occurs and there are no free frames, the OS must select a page to replace.

Goals

  • Minimize the number of page faults.

  • Maintain good system performance.

Common Algorithms

  • FIFO (First-In, First-Out): - Replace the oldest loaded page. - Simple but can lead to Belady’s anomaly (more frames → more faults).

  • Optimal: - Replace the page that will not be used for the longest period. - Theoretical minimum number of page faults. - Not practical (requires future knowledge).

  • LRU (Least Recently Used): - Replace the page that hasn’t been used for the longest time. - Approximates optimal behavior. - Requires tracking recent usage (time stamps or counters).

  • LFU (Least Frequently Used): - Replace the page used the fewest times. - Can perform poorly if usage changes over time.

  • Clock (Second-Chance): - Circular list of pages with reference bits. - Gives each page a “second chance” before replacement.

Comparison Table

Page Replacement Algorithm Comparison

Algorithm

Description / Notes

FIFO

Simple but can suffer from Belady’s anomaly.

Optimal

Theoretical best; not implementable in practice.

LRU

Approximates optimal; commonly used.

LFU

Replaces least used pages; may not adapt quickly.

Clock

Efficient approximation of LRU using reference bits.

Thrashing

Definition

  • A condition where the system spends more time swapping pages than executing processes.

Causes

  • Too many processes competing for too little memory.

  • High page fault rate.

  • Inadequate frame allocation.

Effects

  • Drastic drop in CPU utilization.

  • Continuous paging activity.

  • Severe system slowdown.

Solutions

  • Reduce the degree of multiprogramming.

  • Use working-set model to allocate sufficient frames.

  • Apply page-fault frequency (PFF) control mechanisms.

Summary

Virtual Memory Summary

Concept

Key Points

Virtual Memory

Provides an illusion of large memory using disk space.

Demand Paging

Loads pages only when needed; uses page faults.

Copy-on-Write

Shares memory until modification occurs.

Page Replacement

Determines which page to evict on a fault.

Thrashing

Occurs when excessive paging reduces performance.
Key Takeaways

  • Virtual memory separates logical from physical storage.

  • Demand paging improves efficiency but must minimize page faults.

  • Replacement algorithms balance simplicity and performance.

  • Thrashing must be controlled for stable system operation.