Concept and Definition
Definition
Virtual memory: abstraction providing an application a large, contiguous address space beyond physical memory limits. Enables concurrent execution of multiple processes without memory conflicts.
Purpose
Decouples logical address space from physical memory. Supports multiprogramming, memory protection, efficient memory usage via swapping.
Basic Mechanism
Logical addresses translated to physical addresses. Pages/segments loaded on demand. Unused data kept on secondary storage (disk).
"Virtual memory is the key to modern memory management, allowing efficient and secure use of limited physical resources." -- Abraham Silberschatz
Address Translation Mechanisms
Logical vs Physical Address
Logical address: generated by CPU, visible to process. Physical address: actual location in RAM. Translation required to map logical to physical.
Memory Management Unit (MMU)
Hardware component performing address translation. Uses page tables or segment tables. Supports protection checks and caching.
Translation Lookaside Buffer (TLB)
Cache for recent address translations. Reduces overhead of page table lookup. Key to efficient virtual memory performance.
Address Translation Process
CPU issues logical address → MMU consults TLB/page table → physical address returned → memory accessed.
Logical Address = Page Number + OffsetPhysical Address = Frame Number + OffsetPaging
Definition and Purpose
Paging: memory divided into fixed-size pages (logical) and frames (physical). Allows non-contiguous allocation, reduces fragmentation.
Page Table Structure
Maps page numbers to frame numbers. Stores valid/invalid bits, protection bits, reference bits.
Hierarchical Paging
Multi-level page tables reduce memory overhead of large single-level tables. Example: two-level page tables in 32-bit systems.
Inverted Page Table
One entry per physical frame, stores mapping back to logical page. Saves space but slower lookup.
| Page Table Entry Fields | Description |
|---|---|
| Frame Number | Physical memory frame index |
| Valid/Invalid Bit | Indicates if page is in memory |
| Protection Bits | Read/write/execute permissions |
| Reference Bit | Set if page accessed recently |
Segmentation
Definition
Segmentation: memory divided into variable-length segments representing logical units (code, data, stack). Provides modularity and sharing.
Segment Table
Maps segment numbers to base addresses and lengths. Includes protection information and status bits.
Segmentation vs Paging
Segmentation supports logical view, paging supports physical memory management. Often combined in systems.
Advantages and Disadvantages
Advantages: easier sharing and protection. Disadvantages: external fragmentation, complex handling.
Demand Paging
Concept
Pages loaded only when accessed (page fault). Reduces memory requirement and startup delay.
Page Fault Handling
CPU traps on invalid page reference → OS locates page on disk → loads into frame → updates page table → resumes process.
Advantages
Efficient memory usage, supports large virtual address spaces, enables multiprogramming.
Disadvantages
Page faults add latency, overhead of frequent disk I/O if poorly managed.
Page Replacement Algorithms
Need for Replacement
When no free frame available, OS must evict page to load new one. Choice affects performance and thrashing.
Common Algorithms
FIFO, Optimal, LRU, Clock, NRU, Second-Chance.
Algorithm Comparison
Optimal: theoretical best, requires future knowledge. LRU: approximates optimal using recent use. FIFO: simple but poor performance.
| Algorithm | Description | Advantages | Disadvantages |
|---|---|---|---|
| FIFO | Evicts oldest page | Simple, easy to implement | Can remove frequently used pages |
| LRU | Evicts least recently used page | Good performance, approximates optimal | High overhead to track usage |
| Clock | Approximate LRU using reference bit | Low overhead, effective | Less precise than true LRU |
// Pseudocode: Clock page replacementwhile(true) { if (reference_bit[hand] == 0) { evict_page(hand); break; } reference_bit[hand] = 0; hand = (hand + 1) % num_frames;}Thrashing and Performance
Definition
Thrashing: excessive paging activity causing severe performance degradation. CPU spends more time handling page faults than executing instructions.
Causes
Insufficient physical memory for working set, poor page replacement, high multiprogramming level.
Detection
High page fault rates, low CPU utilization.
Mitigation Techniques
Reduce multiprogramming, increase RAM, use working set or page fault frequency algorithms.
Working Set Model
Definition
Working set: set of pages actively used during a time window. Represents current locality of reference.
Working Set Size
Determined by window size (Δ). Controls how many pages must be in memory to avoid thrashing.
Working Set Algorithm
Allocates frames to processes based on working set size. Swaps out pages not in working set.
Advantages
Balances memory allocation, reduces thrashing, improves performance.
Hardware Support for Virtual Memory
MMU
Performs address translation with page/segment tables. Generates page faults on invalid access.
TLB
Cache for recent translations. Key to low-latency virtual memory.
Dirty and Reference Bits
Hardware sets bits to track page usage and modifications. Used by OS for replacement and write-back decisions.
Page Table Base Register
Holds physical address of current process’s page table. Enables fast context switching.
Advantages and Disadvantages
Advantages
- Allows programs larger than physical memory.
- Supports multiprogramming and protection.
- Enables efficient use of RAM via demand paging.
- Facilitates memory sharing and swapping.
Disadvantages
- Overhead of address translation and page faults.
- Potential for thrashing and degraded performance.
- Complex hardware and OS support required.
- Increased latency for page fault handling.
Implementation Issues
Page Size Selection
Tradeoff: large pages reduce page table size but increase internal fragmentation; small pages reduce fragmentation but increase overhead.
Page Table Management
Hierarchical tables, hashed/inverted tables balance memory and speed.
Swapping and Disk I/O
Efficient disk management critical to reduce page fault latency.
Security Considerations
Isolation of process address spaces, prevention of illegal memory access enforced via hardware and OS.
References
- Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Wiley, 2018, pp. 235-310.
- Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Pearson, 2015, pp. 142-180.
- Stallings, W. Operating Systems: Internals and Design Principles, 9th ed., Pearson, 2018, pp. 380-430.
- Bovet, D. P., & Cesati, M. Understanding the Linux Kernel, 3rd ed., O'Reilly, 2005, pp. 162-210.
- Denning, P. J. "The Working Set Model for Program Behavior," Communications of the ACM, vol. 11, no. 5, 1968, pp. 323-333.