Introduction to Advanced Page Tables

We now tackle the second problem that paging introduces: page tables are too big and thus consume too much memory.

Let’s start out with a linear page table. As you might recall, linear page tables get pretty big.Or indeed, you might not; this paging thing is getting out of control, no? That said, always make sure you understand the problem you are solving before moving onto the solution; indeed, if you understand the problem, you can often derive the solution yourself. Here, the problem should be clear: simple linear (array-based) page tables are too big. Assume again a 32-bit address space ($2^{32}$ bytes), with 4KB ($2^{12}$ byte) pages and a 4-byte page-table entry. An address space thus has roughly 32 one million virtual pages in it ( $\frac {2^{32}} {2^{12}}$); multiply by the page-table entry size 212 and you see that our page table is 4MB in size. Recall also: we usually have one page table for every process in the system! With a hundred active processes (not uncommon on a modern system), we will be allocating hundreds of megabytes of memory just for page tables! As a result, we are in search of some techniques to reduce this heavy burden.

There are a lot of them, so let’s get going. But not before our crux:

CRUX: HOW TO MAKE PAGE TABLES SMALLER?

Simple array-based page tables (usually called linear page tables) are too big, taking up far too much memory on typical systems. How can we make page tables smaller? What are the key ideas? What inefficiencies arise as a result of these new data structures?