Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 66 ยท Memory Management

Paging and Page Tables

Learn how paging removes external fragmentation, how a logical address splits into page number and offset, how the page table maps pages to frames, and the page-size trade-off.

Contiguous allocation forces a process to occupy one block of memory, which leads to external fragmentation. Paging removes that requirement. A process's memory can be scattered across any free frames of physical memory, and the hardware stitches them together so that the program still sees one continuous address space.

Pages and frames

  • Physical memory is divided into fixed-size blocks called frames.
  • A process's logical address space is divided into blocks of the same size called pages.
  • To run a process that needs n pages, the OS finds n free frames (any of them) and loads the pages there.
  • A per-process page table records which frame holds each page.

A page size is always a power of two (commonly 4 KB, i.e. 2^12 bytes). That makes address translation a simple matter of splitting bits.

Address translation

A logical address of m bits is split into two parts:

Part Bits Meaning
Page number (p) the high bits Index into the page table
Page offset (d) the low n bits, where page size = 2^n Position inside the page

The hardware takes p, looks up the frame number f in the page table, and builds the physical address as f followed by d (that is, f * page_size + d). The offset is never changed.

flowchart LR
    CPU["CPU: logical address = (p, d)"] --> PT["Page table: entry p gives frame f"]
    PT --> PA["Physical address = (f, d)"]
    PA --> MEM["Physical memory"]

Only the page number is translated; the offset passes straight through.

Python Translating addresses with a page table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pages 0..3 are contiguous in the program, yet they live in frames 5, 2, 7 and 0. The program cannot tell. Contiguous logical addresses are not contiguous in RAM, and that freedom is what ends external fragmentation: any free frame will do, wherever it is.

Fragmentation in paging

Paging has no external fragmentation: every free frame is usable. It does have internal fragmentation: the last page of a process is rarely full. A process of 72,766 bytes with 2,048-byte pages needs 36 pages: 35 full ones and 1,086 bytes in the last, wasting 962 bytes. On average, waste is about half a page per process. Small pages waste less, but give bigger page tables and more disk-transfer overhead per byte.

Python Choosing a page size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The total is smallest where the table and waste costs balance: the theoretical optimum is sqrt(2 * s * e), which for a 1 MB process and 8-byte entries is about 4 KB. Real systems choose sizes of 4 KB (x86, ARM), with optional huge pages (2 MB, 1 GB) for programs that use huge memory.

What is in a page-table entry?

An entry holds much more than the frame number:

Bit Purpose
Valid / present Is the page in memory and part of the address space? An access to an invalid page traps.
Read / write / execute Protection: writing to a read-only page (such as code) traps.
User / supervisor Only kernel code may touch kernel pages.
Referenced (accessed) Set by hardware when the page is used (helps page replacement).
Dirty (modified) Set when written; a dirty page must be saved before its frame is reused.

The OS also keeps a frame table: one entry per physical frame saying whether it is free or which process and page owns it.

Sharing pages

Because the mapping is per page, two processes can map the same frame into their page tables. That gives:

  • Shared code: all processes running the same program (or using the same shared library) point to one copy of read-only code pages.
  • Shared memory between processes for fast communication.
  • Protection per page: each process can map the shared frame with different permissions.
Python Two processes sharing a library page

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four mappings use only three frames, and an attempt to write to the shared read-only page triggers a protection trap.

Where does the page table live?

For a process with a 32-bit address space and 4 KB pages, the page table has 2^20 (about one million) entries, 4 MB if each entry is 4 bytes, for every process. That is too large for CPU registers, so the table is kept in main memory and the MMU has a page-table base register (PTBR) pointing to it. But then every memory access takes two memory accesses (one for the entry, one for the data). The next lesson solves that with the TLB and shows how multilevel tables shrink the table.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A system has 4 KB pages. For logical address 10000, what are the page number and offset?

    10000 / 4096 = 2 remainder 1808 (2 x 4096 = 8192; 10000 - 8192 = 1808).
  2. 2. Which kind of fragmentation does paging eliminate, and which one remains?

    Any free frame can be used, so no external fragmentation; the last page of a process may be partly empty.
  3. 3. What does the dirty bit in a page-table entry tell the OS?

    Clean pages can simply be discarded if a copy exists on disk; dirty pages must be written back first.
  4. 4. How can two processes share a library in paging?

    Each page table maps its page to the same frame, usually read-only, so one copy serves all.
  5. 5. Why is a very small page size not always better?

    Smaller pages waste less internal space but need more page-table entries and more disk operations.

Summary

  • Paging splits memory into fixed-size frames and processes into pages; any page can go in any frame, so there is no external fragmentation.
  • A logical address is (page number, offset); the page table maps page to frame and the offset is unchanged.
  • Internal fragmentation averages half a page per process; the best page size balances table size against waste (about 4 KB on typical systems).
  • Page-table entries carry valid, protection, referenced and dirty bits; frames can be shared between processes.
  • Table lookups in memory cost an extra access, which TLBs and multilevel tables address.

Next: The TLB and Multilevel Page Tables