3. Paged address translation

Paging Overview

To address the issues of segmentation, we can instead try splitting memory into lots of ‘segments’ (we call these frames) each of the same size:

• All the same size, in this example $4\text{ kB}$.
• Divide all of memory, starting from zero, aligned to $4\text{ kB}$.
• A physical address, in binary, can be broken into:
  • A frame number, $f$ (upper bits)
  • An offset, $o$ (lower bits)

Each process gets its own virtual address space built as a mapping of physical frames.

Paging Definitions

Frame (Paging)

A frame is a division of physical address space.

Link to original

Page (Paging)

A page is a (“mapped frame”) frame-sized division of virtual address space.

Link to original

Fragmentation in Paging

In terms of fragmentation:

• We avoid external fragmentation as everything is aligned as $4\text{ kB}$ physical chunks, which means contiguous virtual areas do not need to be contiguous physically.
• We limit internal fragmentation but doesn’t eliminate it. If a program needs a single byte, it might still allocate $\text{4 kB}$ but at least the worst-case waste is limited to $4095$ bytes.

Implementation of Paging

Programs use only virtual addresses $(p,o)$ so our hardware MMU must translate from $p$ to $f$. They must be translated at run time:

We make a few modifications to our MMU by introducing:

• a PTBR: page table base register
• a TLB: translation lookaside buffer (used as a cache)

Each process’s mapping to physical frames must be stored somehow, we must create page tables for each process:

Address translation looks like this:

Problems with Paging

There are two main problems with paging:

• We now have two memory accesses: once to lookup the page table for address translation and then the actual access we want to do The solution is to add a hardware cache of page table entries to the MMU, this is called the TLB or translation lookaside buffer.
• Page tables use up a lot of memory: a 32-bit address space with $4\text{ kB}$, lets assume $o$ is a 12-bit number, $p$ is a 20-bit number, hence every process needs $2^{20}$ table entries. The solution is 4. Multi-level page tables.

Comparing pages and segments

segments	pages
any size (up to some max)	fixed size (4 kB)
start anywhere	aligned to a multiple of 4 kB
usually form a coherent unit	arbitrary division
external fragmentation	no external fragmentation
little or no internal fragmentation	internal fragmentation (up to page size)
fairly simple MMU	fairly complex MMU (needs TLB)
virtual address space is non-linear	virtual address space is linaer
sometimes addressed implicitly	always addresses explicitly