Paging, page tables and the TLB

Difficulty: Intermediate

Question

Explain paging and address translation. What is a page table, what is the TLB, and how do you compute the effective memory access time?

Answer

Paging is the memory management scheme that changed everything about how modern operating systems use RAM, so let's start with why it exists. Early systems allocated each process one contiguous block of memory. That caused external fragmentation, the memory ended up like a parking lot with cars randomly scattered and no space for a bus. Paging removes the need for contiguity: divide the process's logical address space into fixed-size blocks called pages, divide physical memory into blocks of the same size called frames, and allow any page to be placed in any frame. Think of a book whose pages are shuffled in a filing cabinet, together with an index that says where each page currently is.

A logical address generated by the CPU is split into two parts: a page number p (the high bits) and an offset d within the page (the low bits). With a 32-bit address and 4 KB pages (2^12 bytes), the offset uses 12 bits and the page number uses 20 bits. The page table, kept in memory and one per process, maps each page number to a frame number. The hardware computes the physical address as frame number times page size plus the offset. Each page table entry (PTE) also carries control bits: valid or present, read, write and execute permissions, dirty (modified), and referenced.

Now the size problem. With 20-bit page numbers there are 2^20 entries; at 4 bytes each, that is 4 MB per process, which is significant, and 64-bit systems would be absurd. Solutions include hierarchical (multi-level) page tables, where the page table is itself paged and only used parts are allocated (x86-64 uses four or five levels), hashed page tables, and inverted page tables, which keep one entry per physical frame rather than per virtual page.

The next issue is speed. Every memory reference would need an extra memory access to read the PTE, doubling access time, or worse with multi-level tables. The fix is the Translation Lookaside Buffer, a small, very fast associative hardware cache of recent page-to-frame translations, typically with 64 to 1024 entries. On a TLB hit, translation costs almost nothing. On a miss, hardware or the OS walks the page table, then loads the entry into the TLB. On a context switch, the TLB must be flushed or its entries tagged with an address space identifier (ASID) so that stale translations for another process are not used.

Effective Access Time (EAT) is a classic calculation. Let the TLB lookup take 10 ns, memory access take 100 ns, and hit ratio 80 percent. A hit costs 10 + 100 = 110 ns (TLB then the data access). A miss costs 10 + 100 + 100 = 210 ns (TLB, page table access, data access). EAT = 0.8 x 110 + 0.2 x 210 = 88 + 42 = 130 ns. With a 98 percent hit ratio, EAT = 0.98 x 110 + 0.02 x 210 = 107.8 + 4.2 = 112 ns, which shows why locality of reference and the TLB make paging practical.

Finally, mention the trade-offs. Paging eliminates external fragmentation but causes internal fragmentation in the last page of each process, on average half a page. Larger pages reduce page table size and TLB pressure, but waste more memory internally; that is why systems support huge pages (2 MB, 1 GB) for databases. Paging also enables sharing, since two processes can map the same frame for shared libraries, and protection through PTE permission bits.

Code examples

Address translation and EAT worked numbers

Given: 32-bit logical address, page size 4 KB (2^12)
  offset bits = 12, page-number bits = 20
  page table entries = 2^20, entry size 4 B -> table size = 4 MB

Translate logical address 0x00003A7C
  page number p = 0x00003A7C >> 12 = 3
  offset      d = 0x00003A7C & 0xFFF = 0xA7C
  page table[3] = frame 9
  physical address = 9 * 4096 + 0xA7C = 0x9000 + 0xA7C = 0x9A7C

Effective access time (TLB 10 ns, memory 100 ns)
  hit  = 10 + 100       = 110 ns
  miss = 10 + 100 + 100 = 210 ns
  hit ratio 80%: EAT = 0.8*110 + 0.2*210 = 130 ns
  hit ratio 98%: EAT = 0.98*110 + 0.02*210 = 112 ns

Split the address into page number and offset, look up the frame, and recombine. The EAT formula weights the hit and miss paths.

Key points

• Logical address = page number + offset; physical = frame number + offset.
• Page tables are per process and stored in memory; PTEs hold valid, permission, dirty and referenced bits.
• Multi-level and inverted page tables reduce page table memory.
• TLB caches translations; flush or use ASIDs on context switch.
• Paging removes external fragmentation but has internal fragmentation.

Concepts covered

paging, page table, TLB, address translation, effective access time