🧠 L9: Virtual Memory Management

Lecture Goal

Understand how virtual memory decouples logical address spaces from physical memory, how page faults work, and master the algorithms that manage this illusion efficiently.

The Big Picture

Virtual memory is the crowning achievement of OS design — it allows processes to use more memory than physically exists, enables process isolation, and simplifies programming. The trick is making page faults so rare (via locality) that the system performs well despite disk being 10,000× slower than RAM.

1. Virtual Memory — Motivation & Basic Idea

🤔 The Core Problem

Traditional memory management assumes the entire logical address space of a process fits in physical memory. This breaks down when:

A single process is larger than available RAM
Many processes compete for limited physical memory simultaneously

💡 The Solution

Virtual Memory decouples the logical address space from physical memory by using secondary storage (disk) as an overflow area.

flowchart LR
    subgraph Process ["Process (Virtual View)"]
        V1["Page 0"]
        V2["Page 1"]
        V3["Page 2"]
        V4["Page 3"]
        V5["Page 4"]
    end

    subgraph RAM ["Physical Memory"]
        R1["Frame 0: Page 0"]
        R2["Frame 1: Page 2"]
        R3["Frame 2: Page 4"]
        R4["Frame 3: Empty"]
    end

    subgraph Disk ["Secondary Storage"]
        D1["Page 1"]
        D2["Page 3"]
    end

    V1 -.->|"Resident"| R1
    V2 -.->|"On Disk"| D1
    V3 -.->|"Resident"| R2
    V4 -.->|"On Disk"| D2
    V5 -.->|"Resident"| R3

    style Process fill:#e1f5fe
    style RAM fill:#c8e6c9
    style Disk fill:#ffccbc

The CPU always works with logical (virtual) addresses — it is the OS + hardware that transparently manages which pages are physically present.

📊 Key Benefits Summary

Benefit	Mechanism
Process size > Physical RAM	Only active pages need to be resident
Higher multiprogramming degree	More processes share limited RAM
Better CPU utilization	More runnable processes → fewer idle cycles
Memory isolation	Each process has its own virtual address space

📚 Key Terminology

Term	Definition
Virtual (Logical) Address Space	The address space a process “sees”; may be much larger than physical RAM
Physical Address Space	The actual addresses of physical RAM
Page	A fixed-size chunk of logical address space
Frame	A fixed-size chunk of physical memory (same size as a page)
Secondary Storage	Disk/SSD used to hold non-resident pages
Memory-Resident Page	A page currently loaded in a physical frame
Non-Memory-Resident Page	A page stored on disk, not currently in RAM

⚠️ Common Pitfalls

Pitfall 1: Confusing "virtual memory" with "physical memory size"

Virtual memory is a management scheme, not a hardware spec. A process with 8 GiB of virtual address space can run on a system with only 2 GiB of RAM.

Pitfall 2: Assuming all pages must be in RAM

Only the pages being actively accessed right now need to be resident. The rest can stay on disk.

Pitfall 3: Thinking disk is "free" to use as extra RAM

Disk access is ~1,000–10,000× slower than RAM. Over-reliance on disk (thrashing) severely degrades performance.

❓ Mock Exam Questions

Q1: Primary Motivation

Which of the following is the primary motivation for virtual memory?

Answer

To allow a process’s logical address space to exceed physical memory size

Virtual memory enables processes to use more memory than physically exists by keeping inactive pages on disk.

Q2: Hardware Component

In a virtual memory system, when a process accesses a virtual address, the first hardware component involved in translation is:

Answer

Page Table (via the MMU)

The Memory Management Unit (MMU) uses the page table to translate virtual addresses to physical addresses.

Q3: Pages and Frames

Which of the following is TRUE about pages and frames?

Answer

Pages are units of logical memory; frames are units of physical memory, both of equal size

Pages and frames must be the same size for the mapping to work correctly.

2. Page Fault, Access Flow & Locality

🔍 The Page Table Entry (PTE)

Every page in a process’s virtual address space has a corresponding Page Table Entry (PTE). The PTE stores:

The physical frame number (if the page is resident)
A valid/invalid (memory-resident) bit: 1 = in RAM, 0 = on disk

flowchart LR
    subgraph PTE ["Page Table Entry (PTE)"]
        V["Valid Bit<br/>1 bit"]
        FN["Frame Number<br/>N bits"]
        O["Other Bits<br/>(dirty, ref, etc.)"]
    end

    V -- "1" --> InRAM["Page in RAM ✓"]
    V -- "0" --> OnDisk["Page on Disk ✗"]

    style PTE fill:#fff9c4
    style InRAM fill:#c8e6c9
    style OnDisk fill:#ffccbc

⚡ The Page Fault Mechanism

When the CPU accesses a virtual address whose PTE has valid bit = 0, a page fault is triggered — a hardware trap that hands control to the OS.

flowchart TD
    A[CPU Accesses Virtual Address] --> B{Check PTE<br/>Valid Bit}
    B -- "Valid = 1" --> C[Access Physical Memory<br/>Done ✓]
    B -- "Valid = 0" --> D[Trigger Page Fault Trap]
    D --> E[OS: Save Process State]
    E --> F[OS: Locate Page on Disk]
    F --> G{Free Frame<br/>Available?}
    G -- "No" --> H[OS: Evict Victim Page<br/>Write if Dirty]
    G -- "Yes" --> I[OS: Load Page into Frame]
    H --> I
    I --> J[OS: Update PTE<br/>Set Valid = 1]
    J --> K[Restart Faulting Instruction]
    K --> B

    style C fill:#c8e6c9
    style D fill:#ff9999
    style H fill:#ffccbc

📐 Memory Access Time Formula

$T_{a ccess} = (1 - p) \cdot T_{m e m} + p \cdot T_{p a g e_f a u lt}$

Where:

$p$ = probability of a page fault on any given access
$T_{m e m}$ = time to access a memory-resident page
$T_{p a g e_f a u lt}$ = time to handle a page fault (includes disk I/O)

Since $T_{p a g e_f a u lt} ≫ T_{m e m}$ , even a tiny $p$ has a large impact on $T_{a ccess}$ .

Example Calculation

Given $T_{m e m} = 100 ns$ , $T_{p a g e_f a u lt} = 10 ms = 10, 000, 000 ns$ , target $T_{a ccess} = 120 ns$ :

$p \approx 0.000002 (about 1 in 500,000 accesses)$

This shows how extremely rare page faults must be for virtual memory to be practical.

🎯 Locality Principles — Why VM is Viable

flowchart LR
    subgraph Locality ["Locality Principles"]
        T["Temporal Locality<br/>Recent → Likely Again"]
        S["Spatial Locality<br/>Nearby → Likely Soon"]
    end

    T --> W["Working Set<br/>Stays in RAM"]
    S --> W

    VM["Virtual Memory"] --> Locality
    Locality --> PF["Few Page Faults<br/>Good Performance"]

    style Locality fill:#e1f5fe
    style PF fill:#c8e6c9

Principle	Description	VM Benefit
Temporal Locality	A recently accessed address is likely to be accessed again soon	A loaded page will likely be reused → loading cost is amortized
Spatial Locality	Addresses near a recently used one are likely to be used soon	A page contains contiguous addresses → nearby accesses won’t fault

📚 Key Terminology

Term	Definition
Page Fault	Exception triggered when CPU accesses a non-resident page
Valid/Invalid Bit	PTE bit indicating whether the page is currently in RAM
Trap	A synchronous exception that transfers control to the OS
Dirty Page	A page modified in RAM; must be written back before eviction
Clean Page	An unmodified page; can be evicted without writing to disk
Thrashing	State where a process spends more time on page faults than executing

⚠️ Common Pitfalls

Pitfall 1: Thinking page faults mean crashes

A page fault is a completely normal OS event. It’s how virtual memory transparently loads pages on demand.

Pitfall 2: Forgetting eviction step

Step 4 (load page) may first require evicting an existing page if no free frame exists. This is why page replacement algorithms are necessary.

Pitfall 3: Confusing clean and dirty pages

Only dirty pages need to be written back to disk on eviction. Evicting a clean page is faster because the disk already has an up-to-date copy.

Pitfall 4: Underestimating required p

A page fault rate of even 1-in-1000 ( $p = 0.001$ ) is catastrophically bad in practice. The fault rate must be ~1 in 100,000 or better.

❓ Mock Exam Questions

Q1: Page Fault Sequence

Which correctly describes the sequence during a page fault?

Answer

Answer: Hardware detects fault → OS loads page → hardware retries instruction

The hardware detects the invalid PTE, traps to the OS, the OS handles loading, then the instruction is restarted.

Q2: Page Fault Rate

Given $T_{m e m} = 50 ns$ and $T_{p a g e_f a u lt} = 5 ms$ , which page fault rate gives $T_{a ccess} \approx 100 ns$ ?

Answer

Answer: $p = 0.00001$

Solving: $100 = (1 - p) (50) + p (5, 000, 000)$ → $p \approx 0.00001$ or about 1 in 100,000.

Q3: Spatial Locality

Spatial locality in virtual memory means:

Answer

Answer: If one address is accessed, nearby addresses are also likely to be accessed

Spatial locality is about proximity in memory, not position in address space.

3. Demand Paging

🚀 The Core Idea

When a new process is launched, should all its pages be loaded into RAM immediately? Demand paging says: no.

Demand Paging Definition

Load a page into physical memory only when it is first accessed — i.e., on the first page fault for that page.

A process starts execution with zero pages in RAM. Every first access triggers a page fault, which loads the required page.

flowchart LR
    subgraph Without ["Without Demand Paging"]
        W1[Load ALL Pages] --> W2[Slow Startup]
        W2 --> W3[High Memory Use]
    end

    subgraph With ["With Demand Paging"]
        D1[Load ZERO Pages] --> D2[Fast Startup]
        D2 --> D3[Load on Fault]
        D3 --> D4[Low Memory Use]
    end

    style Without fill:#ffccbc
    style With fill:#c8e6c9

📊 Trade-off Analysis

Aspect	Without Demand Paging	With Demand Paging
Startup time	Slow — must load all pages	Fast — zero pages to load upfront
Memory footprint	Large — all pages resident	Small — only active pages in RAM
Runtime performance	Smooth after startup	Initial sluggishness (cold start faults)
Multiprogramming	Fewer processes fit in RAM	More processes can coexist

📚 Key Terminology

Term	Definition
Demand Paging	Strategy of loading pages only when first accessed
Cold Start	Initial phase where many page faults occur
Memory Footprint	Amount of physical memory a process currently occupies
Pre-paging	Alternative — load pages speculatively before needed

⚠️ Common Pitfalls

Pitfall 1: Confusing demand paging with virtual memory

Virtual memory is the broader system. Demand paging is one policy for when to load pages.

Pitfall 2: Thinking demand paging eliminates page faults

It defers them — the cold start will cause many page faults. After that, faults should be rare if locality holds.

Pitfall 3: Assuming demand paging reduces total faults

It reduces startup cost but doesn’t inherently reduce the total number of page faults over a process’s lifetime.

❓ Mock Exam Questions

Q1: Initial Pages

Under demand paging, how many pages are loaded when a process is first created?

Answer

Answer: Zero

Demand paging loads pages only on first access — none are loaded initially.

Q2: Disadvantage

Which is a disadvantage of demand paging?

Answer

Answer: Initial runtime slowness due to many page faults

The cold start causes many page faults until the working set is loaded.

Q3: Viability

Demand paging is viable primarily because:

Answer

Answer: Most processes access only a small fraction of their pages at any given time

Locality means most pages are never accessed during typical execution.

4. Page Table Structures

📏 The Problem: Page Tables Are Huge

A page table entry (PTE) exists for every page in the virtual address space. With large virtual address spaces, page tables themselves consume significant memory.

Direct (Flat) Paging Example

Given a 32-bit virtual address space with 4 KiB pages and 4-byte PTEs:

$Page bits p = 32 - 12 = 20$ $Number of PTEs = 2^{20} = 1, 048, 576$ $Page table size = 2^{20} \times 4 = 4 MiB per process$

With 100 processes: 400 MiB just for page tables. And most entries map pages that are never used!

🏗️ Structure 1: 2-Level Paging

Key Insight: Most processes use only a small fraction of their virtual address space. A flat table wastes entries for unused regions.

flowchart TD
    subgraph VA ["Virtual Address (32 bits)"]
        D["Page Directory Index<br/>10 bits"]
        T["Page Table Index<br/>10 bits"]
        O["Offset<br/>12 bits"]
    end

    D --> PD["Page Directory<br/>(1 per process)"]
    PD --> |"Each entry points to"| PT["Page Table<br/>(only if used)"]
    PT --> |"Entry holds"| FN["Frame Number + Bits"]

    subgraph RAM ["Physical Memory"]
        F1["Frame"]
        F2["Frame"]
        F3["..."]
    end

    FN --> F1

    style VA fill:#e1f5fe
    style PD fill:#fff9c4
    style PT fill:#c8e6c9

Only allocate sub-tables for regions actually in use.

Structure	Size	When Efficient
Flat paging	4 MiB per process	Dense address space
2-level paging	~13 KiB typical	Sparse address space

🔄 Structure 2: Inverted Page Table

Key Insight: With $M$ processes, there are $M$ page tables. Yet only $N$ physical frames can be occupied. The majority of entries across all page tables are invalid.

flowchart LR
    subgraph Normal ["Normal Page Tables (Per-Process)"]
        N1["Process 1<br/>Page Table"]
        N2["Process 2<br/>Page Table"]
        N3["Process 3<br/>Page Table"]
    end

    subgraph Inverted ["Inverted Page Table (Global)"]
        I1["Frame 0: (P1, Page 5)"]
        I2["Frame 1: (P2, Page 3)"]
        I3["Frame 2: (P3, Page 1)"]
        I4["Frame N: ..."]
    end

    Normal -->|"Memory: O(V × M)"| Note1["Many invalid entries!"]
    Inverted -->|"Memory: O(N)"| Note2["Compact, but O(N) lookup"]

    style Normal fill:#ffccbc
    style Inverted fill:#c8e6c9

Property	Normal Page Table	Inverted Page Table
Table count	One per process	One global table
Table size	Proportional to virtual address space	Proportional to physical frame count
Lookup time	$O (1)$ — direct index	$O (N)$ — linear search (or hashed)
Multi-process support	Easy (separate tables)	Requires `pid` field in each entry

📚 Key Terminology

Term	Definition
Direct (Flat) Paging	Single-level page table with one entry per virtual page
Page Directory	Top-level table in 2-level paging; each entry points to a sub-table
Sub-table / Page Table	Second-level table in 2-level paging; entries map to physical frames
Inverted Page Table	Single global table indexed by frame number; stores `(pid, page#)`
PTE (Page Table Entry)	One record in a page table; stores frame number and status bits

⚠️ Common Pitfalls

Pitfall 1: Assuming 2-level paging is always smaller

2-level paging saves memory only when the address space is sparse. If a process uses nearly all its virtual address space, 2-level may use more memory due to directory overhead.

Pitfall 2: Forgetting extra memory accesses

In 2-level paging, address translation requires two memory accesses before reaching data — one for the page directory, one for the sub-table. This is why TLB is critical.

Pitfall 3: Mixing up indexing direction

Normal page table: indexed by virtual page → gives frame number. Inverted: indexed by frame number → gives (pid, page). The inverted table is used backwards.

Pitfall 4: Assuming inverted tables are faster

They are slower for lookup ( $O (N)$ search) but use less memory. Hashing speeds up the search but adds complexity.

❓ Mock Exam Questions

Q1: Flat Page Table Size

A system uses 32-bit virtual addresses and 4 KiB pages. Each PTE is 4 bytes. What is the size of a flat page table?

Answer

Answer: 4 MiB

$p = 32 - 12 = 20$ bits. Number of entries = $2^{20}$ . Size = $2^{20} \times 4 = 4$ MiB.

Q2: NULL Entry Meaning

In 2-level paging, a NULL entry in the page directory means:

Answer

Answer: The corresponding region of virtual address space is not in use, and no sub-table is allocated

This is exactly the memory-saving benefit — sparse regions have NULL directory entries.

Q3: Inverted Table Advantage

The primary advantage of an inverted page table is:

Answer

Answer: Reduced total memory consumption for page table storage

One table proportional to physical frames, not multiple tables proportional to virtual address spaces.

5. Page Replacement Algorithms

🔄 When Is Replacement Needed?

When a page fault occurs and no free physical frame exists, the OS must evict an existing page to make room. The evicted page is written back to disk only if it is dirty (modified since loading).

flowchart TD
    PF[Page Fault Occurs] --> Free{Free Frame<br/>Available?}
    Free -- "Yes" --> Load[Load Page into Frame]
    Free -- "No" --> Select[Select Victim Page<br/>Using Algorithm]
    Select --> Dirty{Page Dirty?}
    Dirty -- "Yes" --> Write[Write to Disk]
    Dirty -- "No" --> Evict[Evict Page]
    Write --> Evict
    Evict --> Load
    Load --> Update[Update PTE<br/>Set Valid = 1]

    style PF fill:#ff9999
    style Load fill:#c8e6c9

📏 Performance Metric

$T_{a ccess} = (1 - p) \cdot T_{m e m} + p \cdot T_{p a g e_f a u lt}$

A good replacement algorithm minimizes total page faults, keeping $p$ small.

Algorithm 1: OPT (Optimal)

flowchart LR
    Ref["Reference String"] --> OPT["OPT Algorithm"]
    OPT -->|"Look into future"| Furthest["Evict page used<br/>FURTHEST in future"]

    style OPT fill:#c8e6c9

Strategy: Replace the page whose next use is furthest in the future.

Produces the minimum possible page faults — the theoretical lower bound
Not implementable in practice (requires future knowledge)
Used purely as a benchmark

Algorithm 2: FIFO (First-In, First-Out)

flowchart LR
    subgraph FIFO ["FIFO Queue"]
        Q1["Oldest Page"] --> Q2["..."] --> Q3["Newest Page"]
    end

    New["Page Fault"] --> Evict["Evict from Front"]
    Evict --> Add["Add to Back"]

    style FIFO fill:#fff9c4
    style Q1 fill:#ff9999

Strategy: Evict the page that has been in memory the longest.

Weakness — Belady’s Anomaly:

Adding more physical frames can increase the number of page faults under FIFO!

Frames	Page Faults
3	9
4	10 ← Anomaly!

Algorithm 3: LRU (Least Recently Used)

flowchart LR
    subgraph LRU ["LRU Stack (Most Recent at Top)"]
        R1["Page A<br/>Just Accessed"] --> R2["Page B"] --> R3["Page C<br/>Least Recent"]
    end

    Access["Page Accessed"] --> Move["Move to Top"]
    Fault["Page Fault"] --> Evict["Evict from Bottom"]

    style R3 fill:#ff9999

Strategy: Evict the page that has not been used for the longest time.

Exploits temporal locality: recently used pages are likely to be used again
Approximates OPT by looking backward in time
Does not suffer from Belady’s Anomaly

Algorithm 4: Second-Chance (CLOCK)

flowchart TD
    subgraph Clock ["Circular Queue with Clock Hand"]
        C1["Page 1<br/>ref=0"] --> C2["Page 2<br/>ref=1"]
        C2 --> C3["Page 3<br/>ref=0"]
        C3 --> C1
        Hand["Clock Hand ▶"] -.-> C1
    end

    Check["Check Current Page"] --> Ref{"Ref Bit?"}
    Ref -- "0" --> Evict["Evict This Page"]
    Ref -- "1" --> Clear["Clear to 0,<br/>Advance Hand"]
    Clear --> Check

    style Evict fill:#c8e6c9
    style C1 fill:#fff9c4

Algorithm:

Point clock hand at oldest page (victim candidate)
LOOP:
  If reference bit == 0 → EVICT this page. Done.
  If reference bit == 1 → Clear bit to 0, advance hand, continue loop.

Algorithm	Faults (example)	Belady’s Anomaly	Implementable?	Hardware Needed
OPT	6 (minimum)	❌ No	❌ No	—
FIFO	9	✅ Yes	✅ Yes	None
LRU	7	❌ No	✅ Yes	Counter or stack
CLOCK	6	❌ No	✅ Yes	Reference bit only

📚 Key Terminology

Term	Definition
Page Replacement	Evicting a resident page to make room for a newly-faulted page
Dirty Page	A page modified in RAM; must be written to disk before eviction
Clean Page	An unmodified page; can be evicted without a disk write
Belady’s Anomaly	More frames leading to more page faults (FIFO-specific)
Reference Bit	Hardware bit in PTE; set to 1 on any access
Clock Hand	Pointer in CLOCK algorithm pointing to victim candidate
Reference String	A sequence of page numbers representing memory accesses

⚠️ Common Pitfalls

Pitfall 1: Thinking OPT is real

OPT is theoretically optimal but practically impossible — it requires knowing the future. It exists only as a benchmark.

Pitfall 2: Assuming more frames always reduces faults

True for LRU, OPT, and CLOCK — but FIFO can violate this (Belady’s Anomaly).

Pitfall 3: Confusing LRU with CLOCK

LRU is exact — it always evicts the true least-recently-used page but is expensive. CLOCK approximates LRU using the reference bit and is efficient.

Pitfall 4: Forgetting dirty page write-back

When a dirty page is evicted, it must be written to disk first — doubling the I/O cost compared to evicting a clean page.

Pitfall 5: Clock hand movement

In CLOCK simulations, the hand advances after clearing a reference bit. Track it carefully!

❓ Mock Exam Questions

Q1: Minimum Faults

Which page replacement algorithm is guaranteed to produce the minimum number of page faults?

Answer

Answer: OPT

OPT is the theoretical minimum by definition — it looks into the future.

Q2: Belady's Anomaly

Belady’s Anomaly refers to:

Answer

Answer: FIFO producing more page faults when given more physical frames

Counterintuitively, more frames can cause more faults under FIFO.

Q3: CLOCK Behavior

In the CLOCK algorithm, when a page with reference bit = 1 is encountered:

Answer

Answer: Its reference bit is set to 0 and the clock hand advances

The page gets a “second chance” — its bit is cleared and the hand moves on.

6. Frame Allocation

📊 The Problem

Given $N$ physical frames and $M$ competing processes, how should frames be distributed?

flowchart LR
    subgraph Frames ["Physical Frames (N)"]
        F1["Frame"]
        F2["Frame"]
        F3["..."]
        FN["Frame"]
    end

    subgraph Processes ["Processes (M)"]
        P1["Process 1"]
        P2["Process 2"]
        P3["Process 3"]
    end

    Alloc["Allocation Policy"] --> Frames
    Frames -->|"?"| Processes

    style Frames fill:#c8e6c9
    style Processes fill:#e1f5fe

Allocation Strategies

Equal Allocation: $Frames per process = ⌊ \frac{N}{M} ⌋$

Simple, but ignores process size.

Proportional Allocation: $Frames for process p = \frac{size _{p}}{size _{t o t a l}} \times N$

Fairer — larger processes get more frames proportional to their size.

Proportional Allocation Example

$N = 64$ frames, 3 processes of sizes 10, 30, and 60.

Total size = 100

Process allocations: $\frac{10}{100} \times 64 = 6$ , $\frac{30}{100} \times 64 = 19$ , $\frac{60}{100} \times 64 = 38$

🔄 Local vs. Global Replacement

flowchart TD
    subgraph Local ["Local Replacement"]
        L["Fault in Process P"] --> LP["Evict from P's frames ONLY"]
    end

    subgraph Global ["Global Replacement"]
        G["Fault in Process P"] --> GG["Evict from ANY frame"]
    end

    style Local fill:#c8e6c9
    style Global fill:#ffccbc

Property	Local Replacement	Global Replacement
Victim scope	Only the faulting process’s frames	Any frame in physical memory
Frame count	Fixed per process	Dynamic — can grow or shrink
Performance	Stable, predictable	Self-adjusting, adaptive
Isolation	Strong — one process can’t hurt another	Weak — a greedy process can starve others
Efficiency	May under-use frames if process needs fewer	Better overall utilization

📚 Key Terminology

Term	Definition
Equal Allocation	Every process receives $⌊ N / M ⌋$ frames
Proportional Allocation	Frames distributed based on process size
Local Replacement	Victim selected only from faulting process’s frames
Global Replacement	Victim selected from any frame in the system

⚠️ Common Pitfalls

Pitfall 1: Thinking equal allocation is fair

A process with 10 pages and a process with 10,000 pages receiving the same frames is not fair — the large process will thrash while the small one wastes frames.

Pitfall 2: Assuming global replacement always wins

Global replacement is more adaptive, but a single poorly-behaved process can steal frames from others, causing cascading thrashing.

Pitfall 3: Forgetting local means fixed

Local replacement means frame allocation is fixed for the process — when it needs a new page, it must replace one of its own.

❓ Mock Exam Questions

Q1: Proportional Allocation

A system has 100 frames and 4 processes of sizes 20, 30, 40, and 10. Under proportional allocation, how many frames does the size-30 process receive?

Answer

Answer: 30 frames

$\frac{30}{100} \times 100 = 30$ frames.

Q2: Local Replacement

Under local page replacement, if a process has too few frames:

Answer

Answer: It thrashes within its own frame allocation, slowing only itself

Local replacement contains the damage — other processes’ frames are protected.

Q3: Global Replacement Disadvantage

Which is a disadvantage of global page replacement?

Answer

Answer: A misbehaving process can reduce the frame count of other processes

Global replacement allows frame stealing, which can cascade problems.

7. Thrashing & the Working Set Model

🚨 What is Thrashing?

Thrashing occurs when a process (or system) spends more time swapping pages between disk and RAM than actually executing useful instructions.

flowchart LR
    subgraph Normal ["Normal Operation"]
        N1["CPU executes"] --> N2["Occasional fault"]
        N2 --> N1
    end

    subgraph Thrash ["Thrashing"]
        T1["CPU waits for I/O"] --> T2["Page fault"]
        T2 --> T3["Load page"]
        T3 --> T4["Fault again"]
        T4 --> T1
    end

    Normal -->|"Frames < Working Set"| Thrash

    style Normal fill:#c8e6c9
    style Thrash fill:#ff9999

Root cause: A process has fewer allocated frames than needed to hold its active working pages.

🔄 Cascading Thrashing (Global Replacement)

flowchart TD
    P1["Process P1 Thrashes"] --> P1a["P1 steals frames from P2"]
    P1a --> P2["Process P2 has too few frames"]
    P2 --> P2a["P2 thrashes, steals from P3"]
    P2a --> P3["Process P3 thrashes"]
    P3 --> All["ALL Processes Thrashing"]
    All --> Collapse["CPU Utilization Collapses<br/>Disk I/O Maxed Out"]

    style Collapse fill:#ff0000,color:#fff

📐 The Working Set Model

flowchart LR
    subgraph Window ["Working Set Window (Δ)"]
        R1["ref t-Δ"] --> R2["..."] --> R3["ref t"]
    end

    Window --> WS["Working Set W(t, Δ)"]
    WS --> Distinct["Set of Distinct Pages<br/>Accessed in Window"]

    style Window fill:#e1f5fe
    style Distinct fill:#c8e6c9

Working Set Definition: $W (t, Δ) = set of distinct pages accessed in (t - Δ, t]$

Where $Δ$ is the working set window — the number of past references to consider.

$Δ$ too small	$Δ$ too large
Misses pages in current locality	Spans multiple localities
Underestimates frame need	Overestimates frame need

Working Set Example

Reference string: ... 2 6 5 7 1 | 1 2 7 5 6 | 3 4 4 4 3 ...

With $Δ = 5$ :

$W (t_{1}, Δ) = {1, 2, 5, 6, 7}$ → 5 frames needed

$W (t_{2}, Δ) = {3, 4}$ → 2 frames needed

System-level policy: If $\sum_{all processes} ∣ W (t, Δ) ∣ > N$ (total frames), the system is overcommitted. The OS should suspend (swap out) one or more processes.

📚 Key Terminology

Term	Definition
Thrashing	State where a process spends more time on page fault handling than execution
Cascading Thrashing	Thrashing spreading across processes due to global frame stealing
Locality	The set of pages actively used during a phase of execution
Working Set	$W (t, Δ)$ — distinct pages accessed within the last $Δ$ references
Overcommitment	Total working set size exceeds available frames

⚠️ Common Pitfalls

Pitfall 1: Blaming slow CPU or large programs

Thrashing is caused by insufficient frame allocation relative to the working set. A small process can thrash if given only 1 frame.

Pitfall 2: Confusing locality with working set

Locality is the concept (programs tend to access a small active set). Working set is the formalization — a precisely defined window-based measurement.

Pitfall 3: Thinking large Δ is safe

A very large $Δ$ captures pages from multiple localities (including inactive ones), leading to frame overallocation.

Pitfall 4: Confusing local vs global replacement effects

Global replacement + thrashing → cascading (one process hurts all)

Local replacement + thrashing → contained (one process hurts itself)

❓ Mock Exam Questions

Q1: Thrashing Cause

Thrashing occurs when:

Answer

Answer: A process has fewer frames than its working set size

When frames < working set, the process constantly faults on pages it needs.

Q2: Small Window

In the working set model, if $Δ$ is very small:

Answer

Answer: The working set may miss pages in the current locality

A small window might not capture all active pages, leading to excess page faults.

Q3: Cascading Thrashing

Under global replacement, cascading thrashing is caused by:

Answer

Answer: A thrashing process stealing frames from other processes

Global replacement allows one process’s thrashing to affect all others.

🔗 Connections

📚 Lecture	🔗 Connection
L1	OS structure — VM manager is a core OS component
L2	Memory context — logical address space may exceed physical memory
L3	Scheduling — working set size affects frame allocation decisions
L4	IPC — shared memory regions can be paged out
L5	Threads — all threads share the same virtual address space
L6	Synchronization — page table updates need atomicity in multiprocessors
L7	Memory abstraction — logical addresses enable VM
L8	Paging — VM builds on paging with disk backing
L10	File buffer cache — similar replacement algorithms (LRU, CLOCK)
L12	File system — VM concepts used for file system caching

The Key Insight

Virtual memory works because of locality — programs don’t access all their pages uniformly. They cluster in small working sets. The entire system is designed to make those working sets fit in RAM. When they don’t, thrashing happens. Keep the working set in RAM, and the illusion holds. 💾

Quartz 4

Explorer

L9

🧠 L9: Virtual Memory Management

1. Virtual Memory — Motivation & Basic Idea

🤔 The Core Problem

💡 The Solution

📊 Key Benefits Summary

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

2. Page Fault, Access Flow & Locality

🔍 The Page Table Entry (PTE)

⚡ The Page Fault Mechanism

📐 Memory Access Time Formula

🎯 Locality Principles — Why VM is Viable

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

3. Demand Paging

🚀 The Core Idea

📊 Trade-off Analysis

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

4. Page Table Structures

📏 The Problem: Page Tables Are Huge

🏗️ Structure 1: 2-Level Paging

🔄 Structure 2: Inverted Page Table

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

5. Page Replacement Algorithms

🔄 When Is Replacement Needed?

📏 Performance Metric

Algorithm 1: OPT (Optimal)

Algorithm 2: FIFO (First-In, First-Out)

Algorithm 3: LRU (Least Recently Used)

Algorithm 4: Second-Chance (CLOCK)

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

6. Frame Allocation

📊 The Problem

Allocation Strategies

🔄 Local vs. Global Replacement

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

7. Thrashing & the Working Set Model

🚨 What is Thrashing?

🔄 Cascading Thrashing (Global Replacement)

📐 The Working Set Model

📚 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

🔗 Connections

Graph View

Table of Contents