Session 5.1 – Virtual Memory Fundamentals

Introduction to Virtual Memory

Virtual memory is a memory management technique that provides an "idealized abstraction of the storage resources that are actually available on a given machine" to create the illusion of a very large memory space.

Virtual Memory Concepts

Virtual memory extends the available memory by using secondary storage to simulate additional RAM, allowing programs to execute even when they don't entirely fit in physical memory.

Demand Paging

Demand paging is a method of virtual memory management where pages are loaded into memory only when they are accessed, rather than loading the entire program at startup.

main() {
    // Page 0
    int x = 10;
    
    // Page 1  
    func1();
    
    // Page 2
    func2();
}

void func1() {
    // Page 1
    printf("Function 1");
}

void func2() {
    // Page 2  
    printf("Function 2");
}

After T1:
Frame 0: Page 0 ✓
Frame 1: Empty
Frame 2: Empty

After T2:
Frame 0: Page 0 ✓
Frame 1: Page 1 ✓  
Frame 2: Empty

After T3:
Frame 0: Page 0 ✓
Frame 1: Page 1 ✓
Frame 2: Page 2 ✓

Page Fault Handling

A page fault occurs when a program attempts to access a page that is not currently loaded in physical memory. The operating system must handle this exception and load the required page.

Page Fault Handler Steps:

1. Trap to OS: Hardware generates page fault interrupt
2. Save State: Store current process state
3. Check Address: Verify address is valid
4. Find Free Frame: 
   - If available → Use it
   - If not → Run page replacement algorithm
5. Schedule Disk I/O: Read page from secondary storage
6. Block Process: Context switch to another process
7. I/O Completion: Disk interrupt when page loaded
8. Update Page Table: Set valid bit, frame number
9. Resume Process: Restart faulting instruction

Time Components:
- Interrupt handling: ~1-10 µs
- Page replacement: ~100 µs  
- Disk access: ~1-10 ms
- Memory update: ~1 µs

Principle of Locality

The principle of locality states that programs tend to access a relatively small portion of their address space at any given time. This principle makes virtual memory systems practical and efficient.

Code Example:
for (int i = 0; i < 1000; i++) {
    sum += array[i] * 2;    // Spatial locality: sequential array access
}                           // Temporal locality: i, sum, array accessed repeatedly

Memory Access Pattern:
Time 1: array[0]   → Page 0
Time 2: array[1]   → Page 0 (spatial locality - same page)
Time 3: array[2]   → Page 0 (spatial locality - same page)
...
Time N: array[255] → Page 1 (spatial locality - next page)

Working Set:
- Variables: i, sum (temporal locality)
- Array: sequential access pattern (spatial locality)
- Code: loop instructions (temporal locality)
- Pages needed: Only 2-3 pages for 1000-element array

Working Set Size:
W(t, τ) = {pages accessed in window [t-τ, t]}

Locality Ratio:
LR = (Hits in working set) / (Total accesses)

Example:
Program accesses 1000 pages total
Working set size: 50 pages  
Locality ratio: 0.95 (95% hits)
Page fault rate: 5%

Benefits and Challenges

Performance Analysis

Understanding the performance characteristics of virtual memory systems is crucial for system design and optimization.

Basic Formula:
EAT = (1 - p) × memory_access_time + p × page_fault_time

Where:
- EAT = Effective Access Time
- p = Page fault rate (0 ≤ p ≤ 1)
- memory_access_time = Time to access RAM
- page_fault_time = Time to handle page fault

Detailed Formula:
page_fault_time = page_fault_overhead + swap_page_out + swap_page_in + restart_overhead

Example Calculation:
Memory access time: 100 nanoseconds
Page fault rate: 0.001 (0.1%)
Page fault service time: 25 milliseconds = 25,000,000 ns

EAT = (1 - 0.001) × 100 + 0.001 × 25,000,000
    = 0.999 × 100 + 0.001 × 25,000,000  
    = 99.9 + 25,000
    = 25,099.9 nanoseconds ≈ 25.1 microseconds

Performance Impact:
Without page faults: 100 ns
With page faults: 25,100 ns
Slowdown factor: 251×

Key Metrics:

Page Fault Rate:
PFR = Page Faults / Memory Accesses

Memory Utilization:
MU = Used Pages / Total Pages

Thrashing Indicator:
TI = Page Fault Time / CPU Time

Working Set Size:
WSS = Unique pages in time window

Acceptable Values:
Page Fault Rate: < 0.01 (1%)
Memory Utilization: 60-80%
Thrashing Indicator: < 0.1

Impact of Page Fault Rate on System Performance:

Page Fault Rate | Effective Access Time | Performance Impact
----------------|----------------------|-------------------
0.0001 (0.01%) |        2,600 ns      |    26× slower
0.001  (0.1%)  |       25,100 ns      |   251× slower  
0.01   (1%)    |      250,000 ns      | 2,500× slower
0.1    (10%)   |    2,500,000 ns      |25,000× slower (thrashing)

Lesson: Page fault rate must be kept very low for acceptable performance.
Even 1% page fault rate makes system nearly unusable!

Practical Examples

Analysis:

1. Address Space Calculations:
Pages per process: 4 GB ÷ 4 KB = 1,048,576 pages
Page table entries per process: 1,048,576 entries
Page table size (4 bytes/entry): 4 MB per process
Maximum processes (memory only): 1 GB ÷ 4 MB = 256 processes

2. TLB Performance:
TLB hit: 1 ns + 100 ns = 101 ns
TLB miss: 1 ns + 100 ns + 100 ns = 201 ns (page table access + memory access)
Average TLB access time: 0.98 × 101 + 0.02 × 201 = 103 ns

3. Page Fault Impact (assuming 0.1% page fault rate):
No page fault: 103 ns (with TLB)
Page fault: 10 ms = 10,000,000 ns
Effective access time: 0.999 × 103 + 0.001 × 10,000,000 = 10,103 ns

Performance Analysis:
Without virtual memory: 103 ns
With virtual memory: 10,103 ns
Slowdown factor: ~98×

Optimization Recommendations:
1. Increase physical memory to reduce page fault rate
2. Use better page replacement algorithms
3. Implement prefetching for sequential access patterns
4. Consider larger page sizes for specific applications

Program Structure:
for (i = 0; i < 1000; i++) {
    for (j = 0; j < 1000; j++) {
        for (k = 0; k < 1000; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Memory Requirements:
Matrix A: 1000 × 1000 × 4 bytes = 4 MB = 1000 pages
Matrix B: 1000 × 1000 × 4 bytes = 4 MB = 1000 pages  
Matrix C: 1000 × 1000 × 4 bytes = 4 MB = 1000 pages
Total: 12 MB = 3000 pages

Access Pattern Analysis:
- Matrix A: Row-wise access (good spatial locality)
- Matrix B: Column-wise access (poor spatial locality)
- Matrix C: Single element repeated access (excellent temporal locality)

Working Set Estimation:
Active pages at any time:
- Matrix A: ~1 page (current row)
- Matrix B: ~1000 pages (entire matrix for column access)
- Matrix C: ~1 page (current element)
- Code: ~5 pages
Total working set: ~1007 pages ≈ 4 MB

Performance Prediction:
If physical memory ≥ 4 MB: Minimal page faults
If physical memory < 4 MB: Frequent page faults due to Matrix B
Optimization: Block/tile the multiplication to improve B's locality

Session Summary