Operating Systems · Lesson 6 of 9 · Updated ·
Memory Management — Fragmentation, Paging and Segmentation
RAM is limited and shared by many processes. Memory management decides where each process lives in memory and keeps processes from touching each other's memory.
1. The memory hierarchy
The CPU is far faster than RAM, and RAM far faster than disk. Caches and the OS keep the data you're using now in the faster levels.
2. Logical vs physical addresses
- A program uses logical (virtual) addresses — it thinks it starts at address 0.
- The hardware MMU (Memory Management Unit) translates them to physical addresses in RAM.
This lets many programs each believe they own memory starting at 0, safely.
3. Contiguous allocation and fragmentation
Early systems gave each process one continuous block. To choose a free hole:
| Strategy | Picks | Note |
|---|---|---|
| First fit | the first hole big enough | fast |
| Best fit | the smallest hole big enough | leaves tiny useless holes |
| Worst fit | the largest hole | leaves big holes, rarely best |
This causes fragmentation:
| External fragmentation | Internal fragmentation | |
|---|---|---|
| What | enough free memory in total, but split into small non-adjacent holes | allocated block is bigger than needed; the extra inside is wasted |
| Example | 3 free holes of 10 KB can't fit a 25 KB process | asking for 13 KB, getting a 16 KB block → 3 KB wasted |
| Fix | compaction, or paging | smaller blocks/pages |
4. Paging
- Logical memory is split into fixed-size pages (e.g. 4 KB); physical memory into frames of the same size.
- A page table maps each page to a frame. Pages don't have to be next to each other → no external fragmentation (only a little internal fragmentation in the last page).
Address translation
A logical address = (page number, offset).
Example: page size 1 KB (1024 bytes). Logical address 2100 → page = 2100 ÷ 1024 = 2, offset = 2100 − 2048 = 52. If page 2 is in frame 7, the physical address = 7 × 1024 + 52 = 7220.
TLB: making paging fast
Looking up the page table in RAM for every access would double memory time. The TLB (Translation Lookaside Buffer) is a tiny, very fast cache of recent page → frame translations. Most lookups hit the TLB.
Effective access time = hit ratio × (TLB time + memory time) + miss ratio × (TLB time + 2 × memory time).
5. Segmentation
Instead of equal pages, memory is split into logical segments of different sizes: code, data, stack, heap. Each segment has a base and a limit.
| Paging | Segmentation | |
|---|---|---|
| Unit size | fixed (pages) | variable (segments) |
| Based on | hardware convenience | the program's logical structure |
| Fragmentation | internal (small) | external |
| Seen by programmer? | no | yes |
Modern systems mostly use paging (sometimes combined with segmentation).
Common mistakes
- Mixing up internal (inside a block) and external (between blocks) fragmentation.
- Forgetting that paging removes external fragmentation but not internal.
- Calculating offset incorrectly — offset = address mod page size.
Quick recap
- Logical addresses are translated to physical addresses by the MMU.
- First/best/worst fit for contiguous allocation; external vs internal fragmentation.
- Paging: fixed pages → frames via a page table; TLB caches translations.
- Segmentation: variable logical segments with base and limit.