1. Introduction

In a paging system, processes are divided into pages and stored in physical memory frames. Since pages can be placed in any available frame, the operating system requires a mechanism to track the location of every page.

This tracking mechanism is called the Page Table.

The page table is one of the most important data structures in memory management because it enables the translation of logical addresses into physical addresses.

2. What is a Page Table?

A Page Table is a data structure maintained by the operating system that maps logical page numbers to physical frame numbers.

Key Idea

Page Number → Frame Number

The page table tells the operating system exactly where each page of a process is stored in physical memory.

3. Why is a Page Table Needed?

In paging, pages are stored non-contiguously in memory.

For example:

Page 0 → Frame 5
Page 1 → Frame 2
Page 2 → Frame 8
Page 3 → Frame 1

Since pages are scattered across memory, the CPU cannot directly determine where a page resides.

The page table solves this problem.

Core Problem Solved

Given a page number,
find the corresponding frame number.

Without page tables:

• Address translation would be impossible

• Paging would not work

• Virtual memory could not exist

4. Conceptual View of a Page Table

Suppose a process has four pages.

Page Table

This means:

Page 0 stored in Frame 5
Page 1 stored in Frame 2
Page 2 stored in Frame 8
Page 3 stored in Frame 1

5. Structure of a Page Table Entry (PTE)

Each row of the page table is called a Page Table Entry (PTE).

A PTE contains much more than just the frame number.

5.1 Frame Number

Indicates the physical frame containing the page.

Example:

Page 2 → Frame 8

Frame Number:

8

5.2 Valid / Invalid Bit

Indicates whether the page is currently present in memory.

Valid

Page is present in RAM

Invalid

Page not present

Accessing an invalid page may generate a page fault.

5.3 Protection Bits

Specify allowed operations.

Examples:

Read Only
Read + Write
Read + Execute
Read + Write + Execute

Used for memory protection.

5.4 Dirty Bit (Modified Bit)

Indicates whether the page has been modified after being loaded.

Dirty = 1

Page changed

Must be written back to disk before removal.

Dirty = 0

Page unchanged

Can be discarded safely.

5.5 Reference Bit

Indicates whether the page has been recently accessed.

Used by page replacement algorithms such as:

• Clock Algorithm

• Second Chance Algorithm

6. Logical Address Structure

In paging, every logical address is divided into two fields:

Logical Address
=
Page Number + Offset

Page Number (p)

Identifies the page.

Offset (d)

Identifies the location within that page.

7. Address Translation Using a Page Table

Suppose the CPU generates:

Logical Address
=
(Page 2, Offset 50)

Step 1

Extract page number.

Page Number = 2

Step 2

Look up page table.

Page 2 → Frame 8

Step 3

Replace page number with frame number.

Frame 8 + Offset 50

Result

Physical Address
=
(Frame 8, Offset 50)

8. Address Translation Flow

CPU
 ↓
Logical Address
(Page Number, Offset)
 ↓
Page Table Lookup
 ↓
Frame Number
 ↓
Physical Address
(Frame Number, Offset)
 ↓
RAM Access

This process occurs for every memory reference.

9. Numerical Example

Assume:

Page Size = 1024 Bytes

Logical Address:

2500

Step 1: Calculate Page Number

2500 ÷ 1024 = 2

Page Number:

2

Step 2: Calculate Offset

2500 mod 1024 = 452

Offset:

452

Logical Address:

(Page 2, Offset 452)

Step 3: Page Table Lookup

Suppose:

Page 2 → Frame 8

Step 4: Physical Address

Physical Address
=
(8 × 1024) + 452
=
8644

10. Where is the Page Table Stored?

The page table is typically stored in main memory (RAM).

Problem

Every memory access now requires:

Access 1

Read page table entry.

Access 2

Read actual data.

Thus:

One logical access
=
Two memory accesses

This increases memory access time.

11. Solution: Translation Lookaside Buffer (TLB)

To speed up translation, modern systems use a Translation Lookaside Buffer (TLB).

A TLB is a small, fast cache that stores recently used page table entries.

Working

Logical Address
       ↓
      TLB
   Hit / Miss
       ↓
Page Table
       ↓
Physical Address

Benefit

Reduces the need for frequent page table lookups.

12. Page Table Registers

The CPU uses special registers to locate the page table.

12.1 PTBR (Page Table Base Register)

Stores the starting address of the page table.

PTBR
↓
Beginning of Page Table

12.2 PTLR (Page Table Length Register)

Stores the number of entries in the page table.

Used for:

• Bounds checking

• Protection

13. Page Table Overhead

A major disadvantage of paging is the memory required for page tables.

Example

Suppose:

Logical Address Space = 32 bits
Page Size = 4 KB

Number of pages:

2^32 / 2^12
=
2^20 pages
=
1,048,576 pages

If each page table entry requires:

4 Bytes

Then page table size becomes:

1,048,576 × 4
=
4 MB

For just one process.

This can become very large.

14. Techniques to Reduce Page Table Size

Multilevel Paging

Break page table into multiple levels.

Reduces memory usage.

Hashed Page Tables

Use hash functions for lookup.

Useful for large address spaces.

Inverted Page Tables

Maintain one entry per frame instead of per page.

Reduces table size significantly.

15. Advantages of Page Tables

Enable Paging

Without page tables, paging cannot function.

Support Virtual Memory

Allow processes to use large virtual address spaces.

Flexible Allocation

Pages can be placed anywhere in memory.

Memory Protection

Protection bits prevent illegal access.

Process Isolation

Each process has its own page table.

16. Disadvantages of Page Tables

Memory Overhead

Large page tables consume RAM.

Extra Memory Access

Translation requires lookup before data access.

Increased Complexity

Requires hardware support.

TLB Dependency

Performance heavily relies on TLB efficiency.

17. Page Table vs Frame Table

18. Real-World Analogy

Think of a book stored across multiple shelves.

The book's pages are scattered:

Page 1 → Shelf 5
Page 2 → Shelf 2
Page 3 → Shelf 8

To find a page quickly, you use an index.

The index tells you where each page is located.

Book Index
=
Page Table

Most Important Point

The page table is the core data structure of paging that enables logical-to-physical address translation by mapping page numbers to frame numbers.