Memory Management and Virtual Memory
Address spaces
Programs use logical (virtual) addresses; the MMU translates them to physical addresses. This gives each process its own isolated address space.
Contiguous allocation
- Fixed / variable partitions
- Placement strategies: first fit, best fit, worst fit
- Problems: external fragmentation (free memory scattered) and internal fragmentation (unused space inside a block)
Paging
Memory is split into fixed-size frames, and a process into same-size pages. A page table maps page numbers to frame numbers, which removes external fragmentation.
Logical address = (page number p, offset d)
Physical address = frame(p) * page_size + d
A TLB (translation look-aside buffer) caches recent translations so most accesses avoid an extra memory read.
Effective access time = hit * (TLB + mem) + (1 - hit) * (TLB + 2 * mem)
Segmentation
Memory is divided into logical segments (code, stack, heap). Each segment has a base and a limit. It matches how programmers think but suffers from external fragmentation. Many systems combine segmentation with paging.
Virtual memory and demand paging
Only the pages that are needed are loaded. Touching a page that is not in RAM raises a page fault:
- The trap goes to the OS; it verifies the access is legal.
- A free frame is found (or a victim page is evicted).
- The page is read from disk.
- The page table is updated and the instruction restarts.
Page replacement algorithms
| Algorithm | Evicts | Notes |
|---|---|---|
| FIFO | Oldest page | Can show Belady's anomaly (more frames, more faults) |
| Optimal | Page used farthest in the future | Theoretical best, not implementable |
| LRU | Least recently used | Good approximation of optimal; needs tracking |
| Clock (second chance) | Page with reference bit 0 | Cheap approximation of LRU |
Thrashing
If a process lacks enough frames it spends more time paging than executing. Fixes: reduce multiprogramming, use the working-set model, or add RAM.