Paging

 

Paging — Detailed Explanation

Paging is a memory-virtualization technique designed to solve the major problems of segmentation:

• ❌ External fragmentation

• ❌ Complex free-space management

• ❌ Limited flexibility

Paging provides a cleaner, more scalable way to virtualize memory.

---

Basic Idea of Paging

Instead of dividing memory into variable-sized segments, paging divides memory into:

• Fixed-size blocks in virtual memory → Pages

• Fixed-size blocks in physical memory → Page Frames

Page size = Frame size

---

Example

Virtual Address Space = 64 bytes
Page Size = 16 bytes

Virtual Pages:
Page 0
Page 1
Page 2
Page 3

Physical memory is also split into frames of 16 bytes.

Each virtual page can be placed in any free frame in physical memory.

---

Why Paging Is Better Than Segmentation

✔ No External Fragmentation

Because:

• All frames are same size

• Any free frame can hold any page

✔ Easy Allocation

OS just:

• Maintains a free-frame list

• Picks any free frame

✔ Flexible Address Spaces

No assumptions about:

• Heap growth

• Stack direction

• Memory layout

---

Page Table — The Core Data Structure

Each process has its own page table.

Purpose:

Maps:

Virtual Page Number (VPN) → Physical Frame Number (PFN)

Example mapping: ( refer fig above)

VPN	PFN
0	3
1	7
2	5
3	2

This means:

• Virtual page 1 is stored in physical frame 7.

---

Address Translation Process

A virtual address is divided into:

[ VPN | Offset ]

Where:

• VPN → identifies page

• Offset → identifies byte inside page

---

Example

Virtual Address = 21
Binary (6-bit VA for 64-byte space):

010101

Split:

01 | 0101
VPN  Offset

VPN = 1
Offset = 5

If page table says:

VPN 1 → PFN 7

Physical Address becomes:

PFN | Offset
111 | 0101

Binary: 1110101
Decimal: 117

---

Where Are Page Tables Stored?

Page tables can be very large.

Example:

32-bit address space
4 KB pages

• 20-bit VPN → 2²⁰ entries (~1 million entries)

• If each entry = 4 bytes
  → 4 MB per process!

If 100 processes:
→ 400 MB just for page tables

Because of this:

• Page tables are stored in physical memory

• Not in special CPU hardware

CPU stores:

Page Table Base Register (PTBR)

This points to the page table location in memory.

---

What’s Inside a Page Table Entry (PTE)?

A PTE contains more than just PFN.

Important bits:

Bit	Purpose
Valid	Is mapping valid?
Present	Is page in memory?
Read/Write	Write allowed?
User/Supervisor	User access allowed?
Dirty	Has page been modified?
Accessed	Has page been used?
PFN	Physical frame number

---

Example: x86 PTE

In systems like Intel architecture:

PTE includes:

• Present (P)

• Read/Write (R/W)

• User/Supervisor (U/S)

• few bits (PWT, PCD, PAT, and G) that determine how hardware caching works for

  these pages

        PWT (Page-level Write-Through)

         PCD (Page-level Cache Disable)

         PAT (Page Attribute Table)

         G ( Global)

• Accessed (A)

• Dirty (D)

• Page Frame Number (PFN)

---

Paging Is Slower — Why?

For every memory access:

1. Access page table (to get PFN)

2. Access actual memory

So each reference becomes:

Memory Access → Page Table Access + Real Access

👉 Roughly doubles memory cost.

---

Translation Steps (Hardware)

For each virtual address:

1. Extract VPN
2. Locate PTE using PTBR
3. Fetch PTE from memory
4. Check valid/protection bits
5. Extract PFN
6. Combine PFN + offset
7. Access physical memory

This extra lookup is expensive.

page-table base register(PTBR) contains the physical address of the starting location of the page table.

---

Example: Address Translation with Paging

Instruction:

movl 21, %eax

We focus only on the explicit memory access to virtual address 21 (ignore instruction fetch).

---

Step 1: Virtual Address Breakdown

Virtual Address = 21

Binary (6-bit VA for 64-byte space):

010101

Split into:

01 | 0101
VPN   Offset

• VPN (Virtual Page Number) = 01 → 1

• Offset = 0101 → 5

---

Step 2: Locate the Page Table

The hardware uses the:

Page Table Base Register (PTBR)

PTBR contains the physical address of the page table.

---

Step 3: Compute Page Table Entry Address

Extract VPN

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

Given:

• VPN_MASK = 0x30 (binary 110000)

• SHIFT = 4 (offset size = 4 bits)

For VA = 010101:

010101 & 110000 = 010000
010000 >> 4 = 01

So:

VPN = 1

---

Compute PTE Address

PTEAddr = PTBR + (VPN * sizeof(PTE))

This gives the physical location of the correct page table entry.

---

Step 4: Fetch the Page Table Entry

PTE = AccessMemory(PTEAddr)

Now hardware checks:

if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)

If valid and permitted → continue.

---

Step 5: Form Physical Address

Extract offset:

offset = VirtualAddress & OFFSET_MASK

Then compute:

PhysAddr = (PTE.PFN << SHIFT) | offset

---

Example Values

Assume:

VPN 1 → PFN 7

Binary:

PFN = 111
Offset = 0101

Physical Address:

111 | 0101

Binary: 1110101
Decimal: 117

---

 Step 6: Final Memory Access

Register = AccessMemory(PhysAddr)

So:

AccessMemory(117)

The value at physical address 117 is loaded into %eax.

---

Major Problems of Paging

Even though paging solves fragmentation:

❌ Problem 1: Large Page Tables

Huge memory usage.

❌ Problem 2: Slower Execution

Extra memory reference per access.

These must be optimized.

---

OS Responsibilities in Paging

The OS must:

• Allocate page tables

• Manage free frame list

• Handle page faults

• Maintain protection bits

• Swap pages to disk

• Save/restore PTBR on context switch

---

Why Paging Is Powerful

Paging enables:

✔ Sparse address spaces
✔ Efficient memory allocation
✔ Protection
✔ Isolation
✔ Sharing (shared pages)
✔ Virtual memory (swap to disk)

---

Final Summary

Paging works by:

1. Dividing memory into fixed-size pages.

2. Mapping VPN → PFN via page table.

3. Translating every virtual address.

4. Using hardware + OS cooperation.

It solves segmentation’s fragmentation issues but introduces:

• Large page tables

• Extra memory overhead

Later optimizations (like TLBs and multi-level page tables) solve these performance problems.