Notes › Operating Systems
Memory Management, Paging and Virtual Memory
The OS decides which part of RAM each process gets, keeps processes from touching each other's memory, and makes programs bigger than RAM possible.
Logical vs physical address
- Logical (virtual) address: what the program uses (generated by the CPU).
- Physical address: the real location in RAM.
- The MMU (Memory Management Unit, hardware) translates logical → physical on every access. This lets every process think it has its own memory starting at 0, and protects processes from each other.
Contiguous allocation and fragmentation
Early systems gave each process one continuous block.
| Strategy | Pick the hole that is… | Notes |
|---|---|---|
| First fit | first one big enough | fast |
| Best fit | smallest one big enough | leaves tiny useless holes |
| Worst fit | largest | leaves big holes |
Fragmentation:
- External: enough free memory in total, but split into holes too small to use. Fix: compaction (move processes together) or paging.
- Internal: a process gets a slightly bigger block than it needs; the leftover inside is wasted (happens with fixed-size blocks/pages).
Paging
Split logical memory into pages and physical memory into frames of the same size (e.g. 4 KB). Any page can go into any free frame → no external fragmentation (a little internal fragmentation in the last page).
Address translation
Logical address = page number (p) + offset (d).
- Page size 2ⁿ → the last n bits are the offset; the rest is the page number.
- Physical address = frame number × page size + offset.
Worked example: page size = 1 KB (2¹⁰), logical address = 5000.
- Page number = 5000 / 1024 = 4, offset = 5000 − 4096 = 904.
- Page table says page 4 → frame 9.
- Physical address = 9 × 1024 + 904 = 10,120.
Page table size example
32-bit logical addresses, 4 KB pages (2¹²) → 2³²/2¹² = 2²⁰ pages (~1 million). With 4-byte entries → 4 MB page table per process — too big to keep whole, hence multilevel paging.
TLB — Translation Lookaside Buffer
Every memory access would need two RAM accesses (page table + data). The TLB is a small, fast cache of recent page → frame translations.
- TLB hit: translation found instantly.
- TLB miss: read the page table, then update the TLB.
Effective access time (EAT): EAT = h × (TLB + memory) + (1 − h) × (TLB + 2 × memory) Example: TLB = 20 ns, memory = 100 ns, hit ratio h = 0.8 → 0.8 × 120 + 0.2 × 220 = 96 + 44 = 140 ns (vs 200 ns without a TLB).
Multilevel paging and other page tables
- Two-level paging: page the page table itself — only the parts in use are kept in memory.
- Inverted page table: one entry per frame (not per page) — saves memory, slower lookups (use hashing).
- Hashed page tables for 64-bit address spaces.
Segmentation
Divide memory by logical units of the program — code, stack, heap, functions — each a variable-size segment with a base and limit.
| Paging | Segmentation | |
|---|---|---|
| Unit size | fixed (pages) | variable (segments) |
| Seen by the programmer | no | yes (logical view) |
| Fragmentation | internal | external |
| Table | page table | segment table (base, limit) |
Many systems combined them (segmented paging).
Virtual memory
Run programs larger than physical RAM by keeping only the needed pages in RAM and the rest on disk (swap space). The program sees a big, continuous address space.
Demand paging
Load a page only when it's first used. Each page-table entry has a valid bit. Page fault (accessing a page not in RAM):
- The MMU traps to the OS.
- The OS checks the access is legal (else: segmentation fault).
- Finds a free frame (or replaces one — see Page Replacement Algorithms).
- Reads the page from disk into the frame.
- Updates the page table, then restarts the instruction.
Page faults are expensive (milliseconds vs nanoseconds), so even a tiny fault rate slows everything — see the effective access time formula in the page replacement note.
Copy-on-write
After fork(), parent and child share pages until one of them writes — then only that page is copied. Makes fork() fast.
Thrashing
When processes don't have enough frames, they page-fault constantly and the CPU does almost no work. Fix with the working-set model, fewer processes or more RAM.
Interview one-liners
- The MMU translates logical to physical addresses; the TLB caches translations.
- Paging removes external fragmentation; segmentation can cause it.
- Logical address = page number + offset; physical = frame × page size + offset.
- Virtual memory + demand paging let programs be bigger than RAM.
- A page fault isn't an error — the OS loads the page and retries.
- Related: Page Replacement Algorithms, Process vs Thread.