Virtual Memory: Translation, TLBs, Faults, and COW

A process uses virtual addresses. Hardware and the OS translate them into physical addresses.

Core promise:

isolation
private address-space illusion
efficient sharing

1 / 15

The pain

Without virtual memory:

one program can overwrite another
memory layout becomes global coordination
sharing and protection are hard

Virtual memory makes every process feel private while still letting the OS share physical pages.

2 / 15

Page translation

For page size 4096:

VPN    = virtualAddress / 4096
offset = virtualAddress % 4096

If:

VPN 2 -> PFN 10

then:

physicalAddress = 10 * 4096 + offset

The offset is preserved.

3 / 15

Page-table entry

A PTE is not only a frame number.

Typical simplified fields:

frame
present
read
write
execute
dirty/accessed metadata

Translation and protection are coupled.

4 / 15

Fault categories

No usable mapping:

page fault

Mapping exists but operation violates permission:

protection fault

Do not mix them.

5 / 15

TLB

The TLB is a translation cache.

(address-space id, VPN) -> PFN + permissions

The page table is the source of truth.

A TLB miss is not necessarily a page fault.

6 / 15

LRU TLB example

Capacity 2:

trace: 1 2 1 3 1 2

Result:

hits=2
misses=4

On hit: refresh recency. On miss: evict least recently used if full.

7 / 15

Context switches

Same VPN, different process:

PID 1: VPN 7 -> PFN 100
PID 2: VPN 7 -> PFN 200

A TLB key cannot be just VPN.

Use:

(PID or ASID, VPN)

or flush on context switch.

8 / 15

Stale translations

If the page table changes:

VPN 5 -> PFN 10
VPN 5 -> PFN 20

old TLB entries must be invalidated or updated.

Stale translations can corrupt memory.

9 / 15

Working set

Working set = pages used recently.

If the active set fits:

fewer misses
stable performance

If it does not fit:

eviction churn
TLB/cache/page-fault pressure

10 / 15

Copy-on-write fork

Before fork:

parent -> A, B
ref(A)=1, ref(B)=1

After fork:

parent -> A, B
child  -> A, B
ref(A)=2, ref(B)=2

Shared mappings become read-only/COW.

11 / 15

COW write

Child writes page A.

Wrong:

mutate A in place

Correct:

copy A -> C
child -> C
parent stays -> A
ref(A)--
ref(C)=1

Invariant: shared pages are not mutated in place.

12 / 15

Refcount invariant

For every physical page:

refcount == number of live mappings to that page

Fork increments. COW copy decrements old and creates new. Exit decrements and frees when zero.

13 / 15

Problem ladder

Page Translation and Protection Faults
TLB Simulator: LRU Translation Cache
Tagged TLB with ASIDs and Invalidation
Working Set Window
Copy-on-Write Reference Counting
Mini Virtual Memory Manager

14 / 15

Final model

Correct VM:

translates to the right physical byte
fails for the right reason
keeps stale translations out
avoids unnecessary copies
releases pages exactly once

15 / 15