Paging

Introduction

Imagine a large book that does not fit on a single shelf. Instead of finding one contiguous shelf space, you could split the book into chapters and place each chapter wherever there is an empty spot. You maintain an index card that records which chapter is on which shelf. When someone wants to read the book, they check the index to find each chapter. This is exactly how paging works.

Paging is a memory management scheme that eliminates the need for contiguous memory allocation. It divides both physical memory and logical memory into fixed-size blocks. Physical memory blocks are called frames; logical memory blocks are called pages. When a process needs memory, the OS finds free frames anywhere in memory and maps the process pages to them through a page table.

How Paging Works

Basic Concept

Address Translation

A logical address in a paging system has two parts:

Page Table

Each process has its own page table mapping its logical pages to physical frames:

Address Translation Hardware

Translation Lookaside Buffer (TLB)

Every memory access requires a page table lookup — but the page table itself is in memory. This means every memory access requires TWO memory accesses (one for the table, one for the data). This is unacceptable.

The solution is the TLB — a small, fast hardware cache that stores recent page-to-frame mappings.

Effective Access Time (EAT)

Multi-Level Page Tables

For a 64-bit address space with 4KB pages, a single-level page table would need 2^52 entries — impossibly large. Multi-level page tables solve this by only allocating table space for pages actually in use.

Internal Fragmentation

Paging eliminates external fragmentation (no need for contiguous memory) but introduces internal fragmentation. Since pages are fixed-size, the last page of a process may not be completely filled.

Smaller page sizes reduce internal fragmentation but require larger page tables (more entries). Typical modern page size: 4 KB (balance between table size and fragmentation).

Page Table Entry Structure

Each entry in the page table contains more than just the frame number:

• Valid bit: Is this page currently in memory?
• Dirty bit: Has this page been modified since loading? (Needed for page replacement)
• Referenced bit: Has this page been accessed recently? (Used by replacement algorithms)
• Protection bits: Read/Write/Execute permissions

Real-World Analogy

Paging is like a library with numbered shelves (frames). When a new book (process) arrives, the librarian does not need a single long empty shelf. They split the book into chapters (pages) and put each chapter on any available shelf. The card catalog (page table) records where each chapter is. To read chapter 5, you check the catalog: "Chapter 5 is on Shelf 23." The shelf number is the frame, and the position within the shelf is the offset.

Key Takeaways

• Paging divides memory into fixed-size pages (logical) and frames (physical)
• Eliminates external fragmentation by allowing non-contiguous allocation
• Page table maps logical pages to physical frames for each process
• TLB caches recent translations to avoid double memory access penalty
• Multi-level page tables save space by only allocating tables for used regions
• Internal fragmentation averages half a page per process (typically ~2 KB)
• Every memory access goes through address translation (page number → frame number + offset)