Paging: memory that is not contiguous

Split memory into fixed-size frames. Split each program into pages of the same size. Now any page can go in any frame, and contiguity stops mattering at all.

The translation

Every address a program uses is virtual, and split in two:

   virtual address
   +----------------+--------+
   |  page number   | offset |
   +----------------+--------+
           |             |
           v             |
     page table          |
           |             |
           v             v
   +----------------+--------+
   | frame number   | offset |   physical address
   +----------------+--------+

With 4 KB pages, the offset is 12 bits and the rest is the page number. The page table maps page numbers to frame numbers. The offset passes through untouched.

Worked example

A 32-bit address space with 4 KB pages:

• Offset: 12 bits, because 2^12 = 4096.
• Page number: 32 - 12 = 20 bits.
• Pages: 2^20 = about a million.
• A page table with 4-byte entries: 4 MB. Per process.

That is why page tables are themselves paged, and why multi-level page tables exist.

The TLB

Every memory access now needs two: one to read the page table, one for the data. That would halve the speed of every program ever written.

The translation lookaside buffer is a small fast cache of recent translations, typically 64 to 1024 entries, with a hit rate above 99 percent.

Effective access time with a 100 ns memory and a 20 ns TLB, at 99 percent hits:

0.99 x (20 + 100)  +  0.01 x (20 + 100 + 100)  =  119.8 + 2.2  =  122 ns

Against 100 ns unpaged. About 22 percent overhead for the whole illusion.