Paging Memory Management: Cutting Memory into “Tofu‑Sized” Blocks

Why Paging Is Needed

Continuous (contiguous) allocation requires a program to occupy a single uninterrupted memory region. The article illustrates a scenario where programs A (3 MB), B (2 MB), C (2 MB) and D (4 MB) are loaded, showing that after freeing B only 2 MB remains free, which is insufficient for D despite enough total memory—this is external fragmentation.

Contiguous allocation: program must occupy contiguous memory
Scenario:
- Program A: needs 3 MB
- Program B: needs 2 MB
- Program C: needs 2 MB
- Program D: needs 4 MB
Physical memory after allocation:
[ A:3 MB ][ B:2 MB ][ C:2 MB ][ free ]
After freeing B:
[ A:3 MB ][ free 2 MB ][ C:2 MB ][ free ]
Attempt to load D (4 MB)?
→ remaining 2 MB insufficient
→ but total 4 MB is enough
→ memory fragmentation!
This is the “external fragmentation” problem!

Paging Solution

Paging divides memory into fixed‑size page frames (e.g., 4 KB). Programs work with pages . Virtual pages can map to any physical page frame, eliminating the need for contiguity.

Paging idea:
- Divide memory into fixed‑size “page frames” (Page Frame)
- e.g., each block 4 KB
- Programs use “pages” (Page)

Virtual memory as seen by a program:
┌────┬────┬────┬────┬────┐
│ 0K │ 4K │ 8K │12K │16K │ ...
└────┴────┴────┴────┴────┘

Physical memory (page frames):
┌────┬────┬────┬────┬────┬────┐
│F0  │F1  │F2  │F3  │F4  │F5  │ ...
└────┴────┴────┴────┴────┴────┘

Virtual pages can map to any physical page frame
No need for contiguity!

Basic Concepts

Page Size

Standard page size: 4 KB
Page too large → more internal fragmentation
Page too small → larger page table, higher management overhead
Modern systems support multiple page sizes:
- Huge pages: 2 MB, 1 GB
- Used for databases, large‑memory applications

Virtual Address Structure

32‑bit system (4 GB virtual address space):
┌────────────────┬──────────┐
│  Virtual page number (VPN) │  Offset │
│      20 bits               │ 12 bits │
└────────────────┴──────────┘
- VPN: 2^20 = 1 M pages
- Offset: each page 4 KB = 2^12 bytes

64‑bit system:
┌────────────────┬────────────────┬──────────┐
│ Page‑directory index │ Page‑table index │ Offset │
│   high bits         │   middle bits   │ low bits │
└────────────────┴────────────────┴──────────┘

Page Table

Page table = mapping table from virtual page numbers to physical page frames

┌─────────────┬─────────────┐
│ Virtual page│ Physical frame│
├─────────────┼─────────────┤
│      0      │      5      │
│      1      │      2      │
│      2      │   page‑fault │
│      3      │      8      │
│   ...       │    ...      │
└─────────────┴─────────────┘

Page‑table entry (PTE) structure:
┌────┬────┬────┬────┬────────────────┐
│ Valid│ Protect│ Modified│ Accessed│ Physical page │
│ bit │  bit   │  bit   │  bit   │ number        │
└────┴────┴────┴────┴────────────────┘

Paging Workflow

CPU generates virtual address: 0x12345678
1. MMU splits address:
   Virtual page number: 0x12345
   Page offset: 0x678
2. MMU looks up page table:
   Virtual page 0x12345 → physical frame 0xABC
3. MMU composes physical address:
   Physical address = 0xABC000 + 0x678
                = 0xABC678
4. Access physical memory

┌─────────────────────────────────────────────────┐
│               Virtual address: 0x12345678    │
│   ┌──────────┬────────┐                        │
│   │ 0x12345  │ 0x678 │                        │
│   │   VPN    │ Offset│                        │
│   └─────┬─────┴────────┘                        │
│        ↓                                         │
│   ┌─────────────┐                                 │
│   │   Page table │                                 │
│   │0x12345→0xABC│                                 │
│   └─────┬───────┘                                 │
│        ↓                                         │
│   Physical frame: 0xABC                           │
│        ↓                                         │
│   Physical address: 0xABC678                     │
└─────────────────────────────────────────────────┘

Page‑Table Types

1. Single‑Level Page Table

Simplest, but has issues:
32‑bit system:
- Virtual address space: 4 GB
- Page size: 4 KB
- Number of pages: 4 GB / 4 KB = 1 M = 2^20
- Each PTE: 4 bytes
- Page‑table size: 4 MB
64‑bit system:
- Virtual address space: 16 EB (cannot be fully used)
- Page table becomes enormous!
Issues with single‑level tables:
- Each process has its own page table
- Each process consumes ~4 MB for the table
- Wastes memory

2. Two‑Level Page Table

Split a large page table into smaller ones.
Example on a 32‑bit system:
- First‑level table: 1024 entries (manages 1024 second‑level tables)
- Second‑level table: 1024 entries (each entry 4 KB, exactly one page)
- Each level 1024 = 2^10

Virtual address structure:
┌────────┬────────┬────────┐
│Level‑1 index│Level‑2 index│Offset│
│   10 bits   │   10 bits   │12 bits│
└────────┴────────┴────────┘

Advantages:
- Allocate second‑level tables on demand
- Unused virtual address ranges need no page tables

3. Multi‑Level Page Table (Modern CPUs)

Modern CPUs use multi‑level page tables:
- x86‑64: 4‑level (PML4 → PDPT → PD → PT)
- ARM64: 4‑level
More levels provide better flexibility and scalability, but increase lookup latency.

4. Inverted Page Table

Indexed by physical page instead of virtual page.
Physical pages are far fewer than virtual pages, so the table is smaller.
Disadvantages:
- Lookup slower (requires a search)
- Usually combined with a TLB.

TLB (Translation Lookaside Buffer)

TLB = Translation Lookaside Buffer, a fast cache inside the MMU.
Problem: each memory access needs a page‑table lookup, which itself is a memory access → low efficiency.
Solution: TLB caches frequently used page‑table entries.
TLB characteristics:
- Located inside the MMU
- Extremely fast access (1 cycle)
- Small capacity (tens to hundreds of entries)
TLB hit rate: >95%

Access flow (with TLB):
1. CPU generates virtual address
2. MMU first checks TLB
3. TLB hit → directly obtain physical address → very fast!
4. TLB miss → page‑table lookup → update TLB → slower

Advantages of Paging

1. Eliminates external fragmentation – physical memory can be fully utilized – only minimal internal fragmentation remains.
2. Simplifies allocation – all pages have the same size – allocation is straightforward.
3. Process address‑space isolation – each process has its own page table – cannot access other processes.
4. Supports virtual memory – pages can be swapped to disk – programs larger than physical memory can run.

Disadvantages of Paging

1. Page‑table overhead – large tables consume memory – multi‑level tables increase access time.
2. Internal fragmentation – the last page may be partially unused – average waste about half a page.
3. Increased access time – need to consult the page table – then access actual data – roughly doubles memory accesses.

Conclusion: Memory “Tofu‑Block” Management

Paging = dividing memory into fixed‑size page frames.
Core concepts:
1. Fixed size (4 KB) eliminates external fragmentation.
2. Virtual pages map to physical page frames.
3. Page tables manage the mapping.
4. TLB speeds up page‑table lookups.
5. Multi‑level tables reduce memory overhead.

Virtual memory + paging:
- Programs can use more space than physical memory.
- Provides flexible memory management.
- Ensures safe address isolation.

Remember: Paging is the foundation of modern operating systems; without it, modern computing would not be as powerful and flexible.