Virtual Memory: Translation, TLBs, Page Faults, and Copy-on-Write

Module promise

By the end of this module, a learner should not merely know that “virtual memory maps virtual addresses to physical addresses.” They should be able to reason about a small virtual-memory subsystem the way an operating-system engineer reasons about it: what the source of truth is, what is only a cache, which invariants prevent data corruption, and where performance disappears when locality breaks.

This module is intentionally built as a ladder. It starts with one address and one page table entry. It ends with a small VM manager that combines mappings, page faults, fork, copy-on-write, reads, writes, and process exit cleanup.

The goal is not to memorize OS vocabulary. The goal is to learn the mechanics deeply enough that terms like TLB shootdown, ASID, working set, page fault, refcount leak, and COW race stop feeling abstract.

0. The pain first: why virtual memory exists

Imagine every program directly used physical memory addresses.

Program A writes to physical address 0x0010_0000. Program B accidentally writes to the same address. Now one program has corrupted the other. Worse, if a malicious program knows where the kernel or another process lives, it can write there directly.

A real machine needs at least three properties:

1. Isolation: one process should not freely overwrite another process.
2. Illusion of private memory: each process should feel like it owns a large contiguous address space.
3. Efficient sharing: the OS should share code pages, shared libraries, kernel mappings, and forked pages without copying everything immediately.

Virtual memory is the mechanism that gives all three.

A process does not normally issue physical addresses. It issues virtual addresses. Hardware and the OS cooperate to translate those virtual addresses into physical frames.

The page table is the source of truth. The TLB is a cache. Page faults are the control path. Copy-on-write is a rule that says: “share safely until someone writes.”

1. Pages, frames, and offsets

Memory is divided into fixed-size chunks.

A virtual page is a chunk in a process's virtual address space. A physical frame is a chunk in RAM. If the page size is 4096 bytes, then virtual address 8197 means:

virtual address = 8197
page size       = 4096
virtual page    = 8197 / 4096 = 2
page offset     = 8197 % 4096 = 5

The page table maps the virtual page number, often called VPN, to a physical frame number, often called PFN or PPN.

If VPN 2 -> PFN 10, then:

physical address = PFN * pageSize + offset
                 = 10 * 4096 + 5
                 = 40965

The offset does not change. Translation changes the page/frame number, not the byte position inside the page.

This tiny invariant is one of the most important facts in the whole topic:

virtual address = VPN + offset
physical address = PFN + same offset

A learner who cannot do this arithmetic will struggle with every later topic. That is why the first problem in this module is not a TLB problem. It is direct translation with permission checking.

2. Page table entries are not just addresses

A page-table entry is not only “VPN maps to PFN.” It usually contains metadata.

A simplified page-table entry might have:

frame    = physical frame number
present  = can this mapping currently be used?
read     = can this page be read?
write    = can this page be written?
exec     = can this page be executed?
dirty    = has the page been written?
accessed = has the page been touched recently?

The exact hardware format differs across architectures, but the idea is stable: translation and protection are coupled.

Two failures are especially important.

A page fault means the translation cannot currently complete. Maybe the page is not loaded, not mapped, demand-zero, swapped out, or file-backed and not resident yet.

A protection fault means the mapping exists, but the attempted operation violates permissions. For example, writing to a read-only mapping or executing a non-executable data page.

These are easy to confuse. Keep them separate:

no usable mapping      -> page fault
mapping exists, wrong permission -> protection fault

Copy-on-write intentionally uses this machinery. After fork, parent and child may share physical pages marked read-only. When either process writes, the write causes a fault. The OS checks that the fault is a COW fault, allocates a private copy, updates the page table, and resumes the instruction.

3. The page table is the source of truth; the TLB is a cache

Walking page tables on every load/store would be too expensive. Programs perform huge numbers of memory accesses. Hardware therefore keeps recent translations in a Translation Lookaside Buffer, or TLB.

A TLB entry is conceptually:

(address-space id, virtual page) -> physical frame + permissions

On memory access:

1. Split virtual address into VPN and offset.
2. Check whether the TLB has a valid entry for this address space and VPN.
3. If yes, use it quickly.
4. If no, walk the page table, validate permissions, and fill the TLB.

A TLB hit is fast. A TLB miss is slower. A page fault is much slower because it enters the OS fault handler and may perform allocation or I/O.

Do not flatten these into one concept:

TLB hit  = translation cache had the answer
TLB miss = cache did not have the answer; page table may still have it
page fault = page table says translation cannot currently proceed

A TLB miss is not necessarily a page fault.

4. Locality and LRU

TLBs work because programs have locality.

Temporal locality: if a page is used now, it may be used again soon.

Spatial locality: if an address is used now, nearby addresses may be used soon; they are often on the same page.

A tiny example with capacity 2:

accesses: 1 2 1 3 1 2
TLB:      []
1 -> miss, [1]
2 -> miss, [1,2]
1 -> hit,  [2,1]
3 -> miss, evict 2, [1,3]
1 -> hit,  [3,1]
2 -> miss, evict 3, [1,2]

hits=2, misses=4

LRU means “least recently used.” On every hit, the entry becomes most recently used. On every miss when the cache is full, the least recently used entry is evicted.

This module keeps the first TLB simulator deliberately small so the replacement policy is visible. Later, the tagged TLB problem adds address-space identity and invalidation.

5. The context-switch trap: same virtual address, different process

Two processes can both use virtual address 0x400000. That does not mean they refer to the same physical memory.

Process 1 might have:

VPN 1000 -> PFN 77

Process 2 might have:

VPN 1000 -> PFN 912

If a TLB only cached VPN -> PFN, then after switching from process 1 to process 2, the CPU could accidentally reuse process 1's translation. That would break isolation.

Operating systems avoid this with one of two broad strategies:

1. Flush the TLB on context switch. Simple, but loses useful cached translations.
2. Use address-space tags, often called ASIDs or PCIDs. Then a TLB entry is keyed by (ASID, VPN), not only VPN.

A tagged TLB can keep entries from multiple processes at once because the tag distinguishes them.

This matters for professional-level reasoning. Many “simple cache” solutions are wrong once processes enter the picture.

6. Stale translations and invalidation

A cache is dangerous when the source of truth changes.

Suppose the page table changes:

before: PID 1, VPN 5 -> PFN 10
after:  PID 1, VPN 5 -> PFN 20

If the TLB still contains (PID 1, VPN 5) -> PFN 10, then future accesses may go to the wrong physical page.

That is a stale translation bug. In a real OS, stale TLB entries can cause data corruption, isolation failures, or mysterious crashes.

When a mapping changes, the OS must invalidate or update the relevant TLB entries. On multicore systems, if another CPU might have cached the translation, the OS may need a TLB shootdown: a cross-core request telling other CPUs to invalidate their local entries.

This module does not implement multicore shootdowns, but it makes the learner model the local invariant:

After map/unmap/remap, no old TLB entry may keep serving the previous translation.

7. Demand paging and page faults

A virtual mapping does not always mean a physical page is already resident.

Some examples:

• A stack page may be created only when touched.
• A memory-mapped file page may be loaded from disk on first access.
• A zero page may be shared until written.
• A swapped-out page may need to be read back into RAM.

The page fault handler is the OS path that decides what to do.

A simplified handler might ask:

Is this address part of a valid virtual memory area?
  no  -> segmentation fault / access violation
  yes -> continue

Is the operation allowed by the area's permissions?
  no  -> protection fault
  yes -> continue

Is the page missing but demand-loadable?
  yes -> allocate/load/map and resume
  no  -> fail

Professional systems work is mostly about these edge cases. The hardware gives a fault. The OS must classify it correctly.

8. Working set: when memory stops fitting

A program's working set is the set of pages it has used recently. If the working set fits in memory and TLB capacity, the program tends to run well. If it does not fit, replacement churn begins.

Consider a TLB with capacity 3 and this trace:

1 2 3 1 2 3 1 2 3

The working set is {1,2,3}. It fits. After warmup, hits dominate.

Now consider:

1 2 3 4 1 2 3 4 1 2 3 4

If capacity is 3, the active set has four pages. With a bad access pattern, every access may evict something needed soon. This is the same pain behind cache misses, page replacement misses, and TLB misses.

The working-set problem in this module is deliberately framed as a sliding-window data-structure problem. That is not accidental. Systems performance often becomes data-structure reasoning under pressure.

9. Copy-on-write: fork without immediate copying

The naive implementation of fork would copy the parent's entire address space. That is expensive. Many forked processes immediately call exec, replacing their address space. Copying everything first would waste time and memory.

Copy-on-write avoids this.

Before fork:

parent:
  VPN 0 -> Page A, writable
  VPN 1 -> Page B, writable

refcounts:
  A: 1
  B: 1

After fork:

parent:
  VPN 0 -> Page A, read-only, COW
  VPN 1 -> Page B, read-only, COW

child:
  VPN 0 -> Page A, read-only, COW
  VPN 1 -> Page B, read-only, COW

refcounts:
  A: 2
  B: 2

If the child writes VPN 0, the OS must not mutate Page A in place, because the parent still sees Page A. Instead:

old Page A refcount: 2 -> 1
new Page C allocated with copied content
child VPN 0 -> Page C, writable
copies += 1

After the write:

parent:
  VPN 0 -> Page A
  VPN 1 -> Page B

child:
  VPN 0 -> Page C
  VPN 1 -> Page B

refcounts:
  A: 1
  B: 2
  C: 1

This module's COW problems focus on the key invariant:

A write must not mutate a physical page that is still shared by another process.

If you violate this, the bug may be silent. The program still runs, but parent and child see corrupted state.

10. Reference-count invariants

Reference counts are simple until they are not.

For COW, the refcount of a physical page should equal the number of process page-table entries that point to that physical page.

That gives a powerful invariant:

refcount[page] == number of live mappings to page

Operations must preserve it.

On fork:

for each mapped page in parent:
    child maps same page
    refcount[page]++

On COW write when shared:

old = mapping[pid][vpn]
refcount[old]--
new = allocate copy of old
refcount[new] = 1
mapping[pid][vpn] = new

On exit:

for each mapped page:
    refcount[page]--
    if refcount[page] == 0:
        free page
remove process page table

Most wrong solutions fail one of these transitions. The common failure modes are:

• forgetting to decrement old refcount on copy
• forgetting to increment refcount on fork
• copying even when refcount is one
• leaving pages live after process exit
• allowing a write to mutate shared data
• treating virtual page indexes as physical page IDs

The problems are designed to expose these mistakes.

11. How the module should be taught

Do not start with the full VM manager. Use this sequence:

1. Translate one address by hand.
2. Translate many addresses and classify faults.
3. Simulate a tiny LRU TLB.
4. Add process identity and invalidation.
5. Measure working-set size over a trace.
6. Simulate COW with refcounts.
7. Build the mini VM manager.

Each step should produce one crisp invariant. The learner should be able to say the invariant before coding.

page translation: offset is preserved
TLB: page table is source of truth; TLB is cache
ASID: same VPN in different address spaces is not the same translation
invalidation: mapping changes must remove stale cache entries
working set: recent distinct pages predict pressure
COW: shared pages cannot be mutated in place
exit: every mapping must release its physical page reference

This is also how code reviews should be done. Do not ask only, “Does it pass tests?” Ask, “Which invariant does this line preserve?”

12. Professional extensions after the pack

After finishing the module, the learner is ready to read real OS material about:

• multi-level page tables
• huge pages
• kernel/user address-space split
• page cache and memory-mapped files
• NUMA effects
• TLB shootdowns on multicore machines
• page replacement algorithms beyond LRU
• memory overcommit
• swap behavior
• dirty-page writeback
• zero pages
• page deduplication
• COW races and locking

The pack does not try to implement all of these. It prepares the learner to understand them without pretending they are magic.

Final mental model

Virtual memory is a contract between hardware, the OS, and processes.

The hardware performs fast translation and raises faults. The OS maintains page tables, handles faults, allocates pages, invalidates stale translations, and preserves isolation. Processes see a private address space and mostly do not know any of this is happening.

When the system is correct, every virtual access either translates to the right physical byte or fails for the right reason.

When the system is fast, common translations stay cached and the active working set fits.

When the system is memory-efficient, sharing and copy-on-write avoid unnecessary copies.

Those three goals—correctness, speed, and efficient sharing—are the heart of this module.