Skip to main content

9be19706-a99c-40e4-be5a-74523a25f27e

1. Virtual Memory Concept​

Virtual memory is essentially the illusion that each process has its own private, contiguous address space — even though physical memory is finite and shared.

Goals of Virtual Memory​

  • Security: Processes can’t access each other’s memory because the mapping is controlled by the OS and MMU.
  • Convenience: Programmers write code as if there’s an endless flat memory space starting at 0x00000000.
  • Efficiency: OS can move unused memory to disk (swap) and reuse physical memory between processes.

Think of it as: each process lives in a “matrix simulation” of memory — the OS + hardware decides what reality (physical memory) that maps to.

2. Address Translation Chain​

When the CPU executes load r1, [0x7fff_aaaa_bbbb], that’s a virtual address — not the actual RAM location.

The translation looks like this:

  1. Virtual address split into:

    • Page number (high bits)
    • Offset (low bits within the page)

  2. TLB (Translation Lookaside Buffer) lookup:

    • Hit: You immediately get the physical frame number (fast).
    • Miss: Must walk the page table (slow).

  3. Page table walk:

    • Uses page number to find which physical frame this virtual page maps to.

  4. Physical address = physical frame number + offset.

  5. If the mapping doesn’t exist → page fault.

3. Page Tables​

A page table maps virtual pages → physical frames.

Single-Level​

  • One big array indexed by page number.

  • Each entry stores:

    • Valid bit
    • Frame number
    • Protection bits

  • Problem: too big for large address spaces (e.g., 4 KB pages in 64-bit space = huge table).

Multi-Level​

  • Hierarchical:

    • Top-level table points to second-level tables, etc.

  • Only allocates intermediate tables for parts of the address space that are actually used.

  • Common: 2–4 levels for 64-bit systems.

Inverted Page Table​

  • Instead of one entry per virtual page, store one entry per physical frame.
  • Uses hashing to find which virtual page maps to a given frame.
  • Saves memory for large virtual spaces, but slower lookups.

4. TLB Hits/Misses​

TLB = small, fast cache in the MMU that stores recent virtual→physical translations.

  • Hit: Single-cycle address translation.

  • Miss:

    • Hardware or software page table walk.
    • Can be hundreds of cycles slower.

  • Context switches often flush the TLB (unless ASIDs or PCIDs are used).

5. Page Faults​

A page fault happens when the mapping for the virtual page is not in RAM.

Minor Fault​

  • Mapping exists, but the physical page isn’t in the CPU’s cache/TLB.
  • Page is already in RAM; OS just loads it into TLB.

Major Fault​

  • Page is not in RAM — must be loaded from disk (swap or file).
  • Very slow (microseconds → milliseconds).

6. Page Replacement Policies​

When physical memory is full, OS must evict a page.

Common algorithms:

  • LRU (Least Recently Used) – approximated via hardware reference bits.
  • FIFO – simple, but can suffer from Belady’s anomaly (increasing frames might increase page faults)
  • Clock algorithm – efficient LRU approximation using a circular buffer of frames.

7. Swapping to Disk​

  • Least-used pages are written to swap space.
  • When needed again, they’re read back in (major page fault).
  • Disk I/O dominates the cost — this is where “thrashing” happens if the working set doesn’t fit in RAM.

8. Copy-on-Write in fork()​

When you fork():

  • Parent and child initially share the same physical pages.

  • Both page tables mark those pages as read-only.

  • On write:

    • Page fault occurs.
    • OS allocates a new page, copies the data, and updates page table entry for the writing process.

  • Saves memory when child does exec() soon after.

Key Terms

Quick glossary​

  • VA (Virtual Address) – The address the CPU thinks it’s using when your program accesses memory. It’s an index into your virtual address space, not actual RAM.
  • PA (Physical Address) – The real location in RAM (or possibly on a device) that the VA maps to after translation.
  • VMA (Virtual Memory Area) – A contiguous range of virtual addresses in a process, all with the same permissions and backing.
  • PTE (Page Table Entry) – A record that maps one virtual page (part of a VA range) to its corresponding physical frame, plus flags.

PTE: What it is and isn’t​

  • What it is: A metadata entry in the page table that says where the page is and how it can be used.

    • Location = physical frame number (PFN) or info on where to fetch it (e.g., swap location)
    • Attributes = valid, writable, executable, accessed, dirty, etc.

  • Where it lives: In main memory (RAM) — page tables themselves are just kernel data structures in RAM. The CPU’s MMU reads them when needed.

  • Relation to TLB:

    • TLB = small, fast cache of recently used PTEs stored inside the CPU.
    • On a TLB miss, hardware walks the actual page table in RAM to fetch the PTE.

  • What it is not: It does not store the actual data for the page — only a pointer (the PFN) to the data’s location in RAM or swap.

VMA - In Depth​

  • Stands for: Virtual Memory Area

  • What it is: A kernel data structure describing a contiguous range of virtual addresses in a process with uniform attributes (same perms, same backing). In Linux this is struct vm_area_struct.

  • Typical fields (conceptually):

    • start, end: virtual address range
    • flags/perms: read write execute shared private
    • backing: file-backed mapping (file + offset) or anonymous (heap, stack)

  • Why VMAs exist: They’re the policy/contract for a region (what should be allowed, where data comes from), while PTEs are the mechanism for individual page mappings.

Think of a VMA as: [va_start, va_end) + perms + backing

How they work together on access or fault​

  1. CPU touches Virtuasl Address (VA) → TLB miss → page walk finds PTE.

  2. If PTE present: translate and go.

  3. If not present or permission fault: kernel first finds the VMA covering that VA:

    • If no VMA or perms don’t allow the access → segfault.
    • If VMA is valid: kernel materializes a PTE (e.g., bring page from file/swap) or handles COW by allocating a new frame and then updating the PTE.

Where you can see them (Linux)​

  • VMAs: /proc/<pid>/maps (human view), /proc/<pid>/smaps (stats)
  • PTE-ish info: /proc/<pid>/pagemap (low-level), or use pmap <pid> for a quick summary

Mental model​

  • VMA: “this whole region is stack, rw-, anonymous”
  • PTE: “for page N inside that region, here’s the exact frame and flags right now”

That distinction is why we talk about COW at the PTE level (mark RO to trigger a write fault) and exec/mmap at the VMA level (create/replace regions with new backing and perms).

Swimlane Diagram

Putting It All Together​

Example flow:

  1. Process executes: mov eax, [0x7fff_aaaa_bbbb]

  2. MMU checks TLB.

  3. If hit → use cached physical frame number.

  4. If miss → walk page table (multi-level likely).

  5. If page table says “valid” → load frame number into TLB, retry instruction.

  6. If page table says “invalid” → page fault handler in OS:

    • Check if page is on disk.
    • If so, read into free frame (maybe evict another).
    • Update page table.
    • Resume instruction.