The Problem with Contiguous Allocation
You learned that contiguous allocation leads to external fragmentation — memory gets chopped into small, unusable pieces. Paging solves this problem elegantly by eliminating the need for contiguous memory allocation entirely.
With paging, physical memory is divided into fixed-size blocks called frames, and logical memory (what a process sees) is divided into blocks of the same size called pages. A process's pages can be placed in any available frames, scattered anywhere in physical memory.
How Paging Works
Imagine a jigsaw puzzle where every piece is the same size and shape. You can fit them anywhere on the board — you don't need to find a specific-shaped spot. Paging works the same way:
- Physical memory is divided into frames (e.g., 4KB each).
- A process's logical memory is divided into pages of the same size.
- Each page can be loaded into any available frame.
- A page table maps each page to its frame.
When a process accesses memory, the CPU looks up the page table to find which physical frame contains that page. The address is translated from logical to physical, and the access proceeds.
Logical Memory Page Table Physical Memory
(Process View) (Mapping) (RAM)
┌─────────┐ ┌─────────┐ ┌─────────────┐
│ Page 0 │──────────→│ Frame 4 │─────────→│ Frame 0 │
├─────────┤ ├─────────┤ │ (other) │
│ Page 1 │──────────→│ Frame 1 │─────────→├─────────────┤
├─────────┤ ├─────────┤ │ Frame 1 │
│ Page 2 │──────────→│ Frame 7 │─────────→│ Page 1 │
├─────────┤ ├─────────┤ ├─────────────┤
│ Page 3 │──────────→│ Frame 3 │─────────→│ Frame 2 │
└─────────┘ └─────────┘ │ (other) │
├─────────────┤
Pages can be placed Each page maps │ Frame 3 │
anywhere in physical to any frame │ Page 3 │
memory (no contiguity needed) ├─────────────┤
│ ... │
├─────────────┤
│ Frame 4 │
│ Page 0 │
├─────────────┤
│ ... │
├─────────────┤
│ Frame 7 │
│ Page 2 │
└─────────────┘
Address Translation
A logical address consists of two parts: the page number and the offset within that page. The page number is used as an index into the page table to find the frame number. The offset stays the same.
For example, if pages and frames are 4KB (12-bit offset), a 20-bit address would have an 8-bit page number and a 12-bit offset. The page table maps page 5 to frame 11, so logical address 0x05A3 becomes physical address 0x0BA3.
This translation happens in hardware — the Memory Management Unit (MMU) — so it's extremely fast. The overhead of looking up the page table is negligible compared to the benefit of flexible memory allocation.
Advantages of Paging
- No external fragmentation — Any page can go in any frame. There are always enough frames because they're fixed-size.
- Efficient memory use — Memory is allocated in small, fixed chunks. There's no wasted space from finding contiguous blocks.
- Easy sharing — Multiple processes can share pages (like shared libraries). The page table entries just point to the same frames.
- Foundation for virtual memory — Paging makes it easy to move pages between RAM and disk, enabling virtual memory (covered next).
Internal Fragmentation
Paging isn't perfect. If a process's memory doesn't divide evenly into pages, the last page is partially filled. The remaining space in that page is wasted — this is called internal fragmentation.
For example, if pages are 4KB and a process needs 10KB, it gets 3 pages (12KB total), wasting 2KB. In practice, this waste is small and acceptable compared to the benefits of paging.