Contiguous Allocation

Each process occupies a single contiguous region of RAM bounded by a base and limit register. Hardware checks every access for boundary violations.

Pros: simple, fast. Cons: external fragmentation, hard to grow a process.

Paging

The breakthrough idea: split logical address space into fixed-size pages and physical memory into equally sized frames. Any page can sit in any free frame — eliminating external fragmentation.

A logical address is divided into a page number p and offset d. The MMU consults the page table to translate p to a frame number f, producing the physical address f*frame_size + d.

Worked Example

Suppose page size = 4 KB (12 bits offset). Logical address 0x00003042 → page 3, offset 0x042. If page table maps page 3 to frame 7, physical address = 0x00007042.

Page Table Implementations

• Per-process page table in main memory with a hardware PTBR register pointing to it.
• Translation Lookaside Buffer (TLB) — small, fast cache of recent translations.
• Multi-level page tables — break the page-table itself into pages to handle 64-bit address spaces.
• Inverted page tables — one entry per physical frame.

Hit Ratio

Effective access time = hit_ratio (TLB + memory) + (1 - hit_ratio) (TLB + 2 memory). With TLB=20ns, memory=100ns, hit ratio 80%: 0.8120 + 0.2*220 = 140 ns.

Segmentation

A segment is a logical unit — code, data, stack, heap. The address is (segment number, offset). The segment table stores a base and limit per segment.

Pros: matches programmer view, sharing/protection per segment. Cons: variable-size segments → external fragmentation again.

Segmented Paging

Combine the two: segments are themselves divided into pages. x86 historically used segmentation; modern x86-64 mostly uses pure paging with flat segments.

Comparison Table

Summary

• Paging eliminates external fragmentation by working with fixed-size frames.
• Segmentation matches the programmer's logical view but reintroduces fragmentation.
• Real systems (Linux on x86-64) use multi-level paging with TLB caching.