Paging

Definition

Paging: Memory management scheme that divides process logical address space into fixed-size pages and physical memory into frames of same size. Non-contiguous memory allocation allowing process larger than RAM.

Page: Logical unit (from process perspective) Frame: Physical unit (actual RAM location)

Basic Paging Concept

Page and Frame

Process Address Space:          Physical RAM:
Page 0 (4KB)                    Frame 0 (4KB)
Page 1 (4KB) ────────────────→ Frame 1 (4KB)
Page 2 (4KB) ────────────────→ Frame 5 (4KB)
Page 3 (4KB) ────────────────→ Frame 12 (4KB)
Page 4 (4KB) (on disk)         Frame 2 (4KB) - free
Page 5 (4KB) (on disk)         Frame 3 (4KB)
...                            Frame 4 (4KB)

Page Table

Maps logical page numbers to physical frame numbers:

Virtual Page | Physical Frame | Valid Bit | Other bits
─────────────┼────────────────┼───────────┼──────────
      0      |       1        |     1     | ...
      1      |       5        |     1     | ...
      2      |      12        |     1     | ...
      3      |       3        |     1     | ...
      4      |      None      |     0     | ...  (on disk)
      5      |      None      |     0     | ...  (on disk)

Address Translation

Logical Address: 8196

Step 1: Calculate page number and offset
  Page Size: 4096 bytes (2^12)
  Page Number: 8196 / 4096 = 2
  Offset: 8196 % 4096 = 4

Step 2: Look up page table
  Page Table[2] = Frame 12

Step 3: Form physical address
  Physical Address = Frame * PageSize + Offset
  Physical Address = 12 * 4096 + 4 = 49156

Step 4: Access RAM
  Memory[49156] contains the data

Page Table Structure

Simple (One-Level) Page Table

Virtual Address: 32 bits
├─ Page Number (20 bits)
└─ Offset (12 bits)

Page Table:
Entries: 2^20 = 1,048,576 (1 million)
Each entry: 4 bytes (frame number + flags)
Total: 1,000,000 × 4 = 4MB per process!

32 processes × 4MB = 128MB just for page tables

Multi-Level Page Tables

Hierarchy to reduce page table size:

Virtual Address: 32 bits
├─ Directory (10 bits): Which page table?
├─ Table (10 bits): Which entry in page table?
└─ Offset (12 bits): Position in page

Page Directory: 2^10 = 1024 entries (4KB)
Page Table (if used): 2^10 = 1024 entries (4KB)
Sparse allocation: Only used page tables created

Example:
Program uses 4 pages: Need 4KB directory + 1 page table (4KB)
Total: 8KB (vs 4MB for single-level!)

Page Size Considerations

Small Pages (2KB)

Advantages:

✓ Less internal fragmentation
✓ Faster disk I/O per page fault
✓ More flexibility

Disadvantages:

❌ More pages per process
❌ Larger page table
❌ More TLB misses

Large Pages (2MB)

Advantages:

✓ Fewer pages per process
✓ Smaller page table
✓ Fewer TLB misses
✓ Faster for large sequential access

Disadvantages:

❌ More internal fragmentation
❌ Slower disk I/O per page fault
❌ Memory pressure higher

Typical Choices

Modern systems: 4KB pages
- Good trade-off
- Hardware TLB designed for 4KB

Large pages: 2MB pages (Huge Pages in Linux)
- For specific applications (databases, HPC)
- Significant memory access, less paging needed
- Need explicit configuration

Physical Address Calculation

Example 1

Virtual Address: 5000
Page Size: 4096

Virtual Page Number = 5000 / 4096 = 1
Offset = 5000 % 4096 = 904

Page Table[1] = 10 (frame 10)
Physical Address = 10 × 4096 + 904 = 41904

Example 2

Virtual Address: 12500
Page Size: 4096

Virtual Page Number = 12500 / 4096 = 3
Offset = 12500 % 4096 = 212

Page Table[3] = 25 (frame 25)
Physical Address = 25 × 4096 + 212 = 102656

Translation Lookaside Buffer (TLB)

Purpose

Speed up address translation:

Without TLB:
Logical Address → Page Table Lookup (memory access!) → Physical Address → Access Memory
= 2 memory accesses per address!

With TLB:
Logical Address → TLB Lookup (cache, fast!) → Physical Address → Access Memory
= 1 memory access if TLB hit!

TLB Structure

TLB Cache (16-512 entries, CPU cache size):
Virtual Page | Physical Frame | Valid
─────────────┼────────────────┼──────
     10      |       5        |  1
     15      |       12       |  1
     20      |       3        |  1
     25      |       8        |  1

TLB Hit vs Miss

TLB Hit (95-99% of accesses):

Logical address page 15
TLB has entry: Virtual 15 → Frame 12
Immediate: Physical = 12 × 4096 + offset
No page table access needed!
Fast! (cache speed)

TLB Miss (1-5% of accesses):

Logical address page 30
TLB doesn't have entry
Access page table from memory
Get frame number
Access actual data
Update TLB with new entry
Slower (memory speed)

Performance

Access time with TLB:
= (TLB_hit_rate × TLB_access) + (TLB_miss_rate × page_table_access)
= (0.99 × 10ns) + (0.01 × 100ns)
= 9.9ns + 1ns
= 10.9ns ≈ TLB speed!

Without TLB:
Always need page table access:
= page_table_access + memory_access
= 100ns + 100ns
= 200ns
10x slower!

Internal Fragmentation

Problem

Last page usually not completely full:

Process size: 10,000 bytes
Page size: 4096 bytes

Pages needed: 3 pages
Allocated: 3 × 4096 = 12,288 bytes
Wasted: 12,288 - 10,000 = 2,288 bytes

Fragmentation = 2,288 / 12,288 = 18.6%

On average: 50% of page wasted (2048 bytes)

Minimize Fragmentation

Larger page size:

Page size: 8192 bytes
Waste: Average 4096 bytes
But this increases fragmentation too much
Slow disk I/O per fault

Smaller page size:

Page size: 2048 bytes
Waste: Average 1024 bytes
But more pages, larger page table
More overhead

Optimal: 4KB pages (hardware standard)

Page Fault Handling

Page Fault (Invalid Page)

Process accesses page not in memory:

Process: "I want page 5"
Page Table[5]: Valid bit = 0 (not in RAM)
Result: Page Fault! (interrupt/exception)

Handling Sequence

Step 1: Save context
  Save CPU registers
  Save PC (program counter)

Step 2: Determine fault cause
  Check page table entry
  Valid bit = 0? (not in memory)
  Protection bits check

Step 3: Locate page on disk
  Where is page 5 on disk?
  OS knows from page table/external storage map

Step 4: Free frame
  Need space for page
  If no free frame, evict another page
  (Page replacement algorithm)

Step 5: Load page from disk
  Read from disk to free frame (slow!)

Step 6: Update page table
  Set valid bit = 1
  Set frame number
  Update TLB

Step 7: Restart instruction
  Restore context
  Restart faulted instruction
  "Retry" address translation
  This time: TLB hit or page table hit

Performance Characteristics

Access Times

L1 Cache Hit: 4ns
L2 Cache Hit: 20ns
L3 Cache Hit: 40ns
RAM Access: 200ns
TLB Hit: 10ns
TLB Miss (page table): 100ns
Page Fault (disk): 5,000,000ns (5ms)

Page fault = 50,000x slower than RAM!

Example

Program runs normally:
TLB hits 99% of time
Average access: 0.99×10ns + 0.01×100ns = 11ns

Program touches new memory region:
TLB misses cause page faults
One page fault per 4096 bytes accessed
Much slower!

Locality of reference critical!

Benefits of Paging

1. Virtual Memory

Process can be larger than RAM:

RAM: 512MB
Process: 2GB
OS loads needed pages, keeps rest on disk
Process runs fine (slower when accessing disk pages)

2. No External Fragmentation

Fixed-size pages eliminate fragmentation:

Allocate page 1, 5, 10, 15
Free pages 5, 10
Fragments: pages 5 and 10 (both usable)
Allocate page 20: uses page 5
No fragmentation! (unlike contiguous allocation)

3. Memory Protection

Process A: pages 0-9
Process B: pages 10-19
Hardware prevents Page 0 access by Process B
MMU checks process ID + page number
Protection at hardware level!

Share physical frames:

Shared Library Code in Frame 50:
Process A: Page 5 → Frame 50
Process B: Page 10 → Frame 50
Process C: Page 20 → Frame 50

One physical copy, three logical views
Save memory!

Disadvantages

1. Translation Overhead

Every address needs translation (though TLB minimizes)

2. Page Table Overhead

32-bit system:
2^20 page table entries
Multi-level helps but still overhead

3. Complexity

Requires:

MMU hardware
Page table management
Page fault handling
Replacement algorithm
TLB management

Summary

Paging divides memory into fixed-size pages, mapping logical pages to physical frames. Page table maintains mapping, TLB caches translations. Eliminates external fragmentation, enables virtual memory, provides protection. Address translation fast when TLB hit (99% typical). Page faults slow (disk I/O) but necessary for virtual memory. Internal fragmentation minimal (average 50% of page). Requires hardware MMU and OS page fault handler. Most modern systems use 4KB pages. Paging combined with page replacement algorithms enables effective memory utilization with processes larger than RAM.