Chapter 9: Virtual Memory

CS330 - Operating Systems

Demand Paging, Page Replacement, Thrashing & Working Set Model

9.1 Background

What is Virtual Memory?

Virtual memory is a technique that allows the execution of processes that are not completely in memory.

  • Separation of user logical memory from physical memory
  • Only part of program needs to be in memory for execution
  • Logical address space can be much larger than physical address space
  • Allows more programs to run concurrently
  • Less I/O needed to load or swap processes

Virtual Memory Benefits

  • ✓ Programs can be larger than physical memory
  • ✓ More programs can run at the same time
  • ✓ Less I/O needed (load only needed pages)
  • ✓ Faster program startup
  • ✓ Shared pages between processes
  • ✓ More efficient memory utilization

Virtual Memory Implementation

Virtual memory can be implemented via:

9.2 Demand Paging

Bring a page into memory only when it is needed

Valid-Invalid Bit

With each page table entry, a valid-invalid bit is associated:

Page Frame Valid Bit Meaning
0 4 v In memory
1 6 v In memory
2 - i Not in memory
3 9 v In memory
4 - i Not in memory

Page Fault Handling Steps

1
Reference
Page

CPU references page

→
2
Check
Valid Bit

Invalid bit set

→
3
Backing
Store

Find page on disk

→
4
Load into
Memory

Bring page to frame

→
5
Update
Page Table

Set valid bit

→
6
Restart
Instruction

Continue execution

1

Trap to OS

Page table entry has invalid bit set, causing page fault trap

2

Check Reference

OS checks internal table to verify if reference is valid

3

Get Empty Frame

Find free frame from free-frame list

4

Swap Page In

Read page from backing store into frame

5

Update Tables

Set page table entry, valid bit = v

6

Restart Process

Restart instruction that caused page fault

9.3 Performance of Demand Paging

Effective Access Time (EAT)

EAT = (1 - p) × ma + p × page_fault_time

Where:

  • p = page fault rate (0 ≤ p ≤ 1)
  • ma = memory access time
  • page_fault_time = time to service page fault

Page Fault Service Time Components:

  1. Page fault overhead (1-100 μs)
  2. Swap page out (if needed)
  3. Swap page in (8-20 ms)
  4. Restart overhead (1-100 μs)

Example Calculation:

Memory access time = 200 nanoseconds

Page fault service time = 8 milliseconds

Page fault rate (p) = 0.001

EAT = (1 - 0.001) × 200 + 0.001 × 8,000,000

EAT = 0.999 × 200 + 0.001 × 8,000,000

EAT = 199.8 + 8,000

EAT = 8,199.8 nanoseconds

This is about 40 times slower than no page faults!

⚠️ Performance Goal:

For acceptable performance, page fault rate must be very low (< 0.0001)

Even 1 page fault per 1,000 accesses causes significant slowdown

9.4 Page Replacement

When no free frame is available, we must replace a page

Basic Page Replacement Steps:

  1. Find location of desired page on disk
  2. Find a free frame:
    • If there is a free frame, use it
    • If not, use page replacement algorithm to select victim frame
  3. If victim page is modified (dirty bit set), write to disk
  4. Bring desired page into newly freed frame
  5. Update page and frame tables
  6. Restart process

Page Replacement Goal:

Want lowest page-fault rate

Evaluate algorithm by running on reference string and computing number of page faults

9.5 Page Replacement Algorithms

Reference String Example:

7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1

Using 3 frames

First-In-First-Out (FIFO) Algorithm

Replace the oldest page in memory

Reference 70120304230321201701
Frame 0 77722224440000000777
Frame 1 0000333222221111100
Frame 2 111100033333222221
Fault? FFFF-FFFFFF--FF--FFF

Total Page Faults: 15

Optimal Page Replacement

Replace page that will not be used for longest period of time

Reference 70120304230321201701
Frame 0 77722222222222222777
Frame 1 0000004400000000000
Frame 2 111333333331111111
Fault? FFFF-F-F-F---F---F--

Total Page Faults: 9 (Optimal but requires future knowledge)

Least Recently Used (LRU) Algorithm

Replace the page that has not been used for the longest time

Reference 70120304230321201701
Frame 0 77722224440001111111
Frame 1 0000000000333300000
Frame 2 111333233322222777
Fault? FFFF-F-FF-F-FF-F-F--

Total Page Faults: 12

Algorithm Comparison

Algorithm Description Page Faults Advantages Disadvantages
FIFO Replace oldest page 15 Simple to implement Poor performance, Belady's anomaly
Optimal Replace page not used for longest time in future 9 Minimum page faults Requires future knowledge (impossible)
LRU Replace least recently used page 12 Good performance, approximates optimal Expensive to implement exactly
Clock Approximation of LRU using reference bit ~13 Efficient implementation Not as good as true LRU
LFU Replace least frequently used Varies Considers usage frequency Pages used heavily initially stay

🚨 Belady's Anomaly

For some page replacement algorithms (like FIFO), more frames can cause MORE page faults!

Example: Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

  • With 3 frames: 9 page faults
  • With 4 frames: 10 page faults (MORE!)

9.6 Thrashing

What is Thrashing?

A process is thrashing if it is spending more time paging than executing

Thrashing Scenario:

  1. Low CPU utilization → OS increases multiprogramming
  2. More processes → Less memory per process
  3. Processes start page faulting frequently
  4. I/O queue grows, CPU utilization drops further
  5. OS adds more processes (thinking CPU is idle)
  6. System enters thrashing state

CPU Utilization vs Degree of Multiprogramming

Low
↑
Good
Optimal
↓
Thrashing
Severe

Degree of Multiprogramming →

⚠️ Thrashing Prevention:

  • Provide process with as many frames as it needs
  • Use working-set model to estimate needs
  • Monitor page-fault frequency
  • Suspend processes if thrashing detected

9.7 Working-Set Model

Locality of Reference

Temporal Locality

If a memory location is referenced, it will tend to be referenced again soon

Example: Loop counters, frequently used variables

Spatial Locality

If a memory location is referenced, nearby locations will tend to be referenced soon

Example: Array elements, sequential code

Working Set Definition

Working set W(t, Δ) = set of pages referenced in last Δ time units

Working Set Window (Δ = 10)

2
6
1
5
7
5
1
6
2
3

Working Set = {1, 2, 3, 5, 6, 7}

Working Set Size (WSS) = 6

Working Set Strategy:

If Total WSS > Available memory → Thrashing

If D = Σ WSSᵢ > m (available frames)

Then suspend one or more processes

9.8 Page-Fault Frequency (PFF)

PFF Scheme

Establish acceptable page-fault frequency range

  • If PFF too high → allocate more frames to process
  • If PFF too low → reduce frames allocated
  • If no free frames available → suspend process
Upper Bound
(increase frames)
Desired Range
Lower Bound
(decrease frames)

9.9 Allocation of Frames

Equal Allocation

Each process gets equal share

m frames, n processes

Each gets m/n frames

Proportional Allocation

Allocate according to size

sᵢ = size of process i

S = Σsᵢ

aᵢ = (sᵢ/S) × m

Priority Allocation

Based on process priority

Higher priority = more frames

Global vs Local Replacement:

  • Global replacement: Process can select replacement frame from all frames (even those of other processes)
  • Local replacement: Process can only select from its own allocated frames

9.10 Practice Problems

Problem 1: Page Replacement

Reference String: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

Frames: 3

Calculate page faults for FIFO, LRU, and Optimal algorithms

Solution:

FIFO: 16 page faults

LRU: 15 page faults

Optimal: 11 page faults

Problem 2: Effective Access Time

Memory access time = 100 ns

Page fault service time = 25 ms

Page fault rate = 0.0001

Calculate EAT

Solution:

EAT = (1 - 0.0001) × 100 + 0.0001 × 25,000,000

EAT = 99.99 + 2,500

EAT = 2,599.99 ns

Problem 3: Working Set

Reference string: 2, 3, 2, 4, 5, 3, 6, 3, 4, 5, 3

Window size Δ = 4

Find working set at t = 7

Solution:

Look at last 4 references: 5, 3, 6, 3

Working Set = {3, 5, 6}

WSS = 3

9.11 CS330 Exam Practice

Multiple Choice Questions

Q1. Which page replacement algorithm suffers from Belady's anomaly?

Answer: FIFO

Q2. A system is thrashing when:

Answer: Processes spend more time paging than executing

Q3. The working set model is based on:

Answer: Locality of reference

Q4. Valid-invalid bit in page table indicates:

Answer: Whether page is in memory (v) or on disk (i)

Short Answer Questions

Q5. List two ways to improve system performance when thrashing occurs.

Answer:

  1. Decrease degree of multiprogramming
  2. Increase size of main memory (RAM)
  3. Use better page replacement algorithm
  4. Improve locality of programs

Q6. Why is the optimal page replacement algorithm not implementable?

Answer: It requires future knowledge of the reference string, which is impossible to know in advance. It's used only as a benchmark to compare other algorithms.

9.12 Key Terms and Definitions

Virtual Memory: Technique allowing execution of processes not completely in memory
Demand Paging: Load pages only when they are demanded during execution
Page Fault: Trap generated when process accesses page not in memory
Page Replacement: Selecting victim page to swap out when no free frames
Reference String: Sequence of page references used to evaluate algorithms
Thrashing: Process spending more time paging than executing
Working Set: Set of pages process is actively using
Locality: Tendency to reference nearby memory locations
Belady's Anomaly: More frames causing more page faults (FIFO)
Dirty Bit: Indicates if page has been modified
EAT: Effective Access Time including page fault overhead
PFF: Page-Fault Frequency for frame allocation

9.13 Diagrams from Slides

📊 Page Fault Handling Steps

[Insert detailed page fault handling diagram with OS, memory, and disk]

📊 Page Replacement Algorithms Comparison

[Insert visual comparison of FIFO, LRU, and Optimal]

📊 Thrashing Graph

[Insert CPU utilization vs degree of multiprogramming curve]

📊 Working Set Model

[Insert working set window and WSS calculation example]

Note: Please provide the actual diagrams from your course materials to replace these placeholders.