CODEWITHSUNDEEP
x86pagingcpu-architecturepage-tables
Jacob Garby
Jacob Garby

Reputation: 855

What's the advantage of x86's multi stage paging over a single page table?

Consider x86's 32-bit paging scheme for a concrete example. From the Intel developer's manual I found the following figure, which described how 32-bit paging can convert a linear address to a physical address.

Paging diagram

I don't understand the advantage of this three-stage process over, for example, most of the linear address being used to index a page, and then the lower 12 bits being used to index that page.

The reason I don't understand the need for the three-stage process is that, surely it can't somehow be able to access any more pages than 2^20, since it only has that amount of bits in the linear address (excluding the page offset). As well as not being able to access any more pages, I can't imagine that it would have better performance.

Upvotes: 2

Views: 520

Answers (1)

Nate Eldredge
Nate Eldredge

Reputation: 58132

Keep in mind that this design came from the Intel 80386, released in 1985, and is essentially unchanged since then.

A page table entry is 4 bytes. If you need 2^20 page table entries, that's 4 MiB of memory for your page table alone. That might seem reasonable to you today, but by 1985 standards that's outrageous. Memory in those days cost something like $1000 per megabyte, and most people were used to having 640K or less.

Furthermore, if you're going to use multitasking, which was the major advance of the 386, you need a separate page table for every task. So multiply that $4000 times another big number; Unix users would already have been used to being able to run dozens of processes at a time.

Most processes wouldn't have needed anywhere near 4 GiB of virtual memory: again, hardly anyone had anywhere near that much physical memory, or even disk space. A real memory hog (Emacs, maybe?) might have needed a megabyte or two. With the two-level structure, you only need about as many page table entries as the number of pages of memory you're actually using, plus a bit more for the page directory. Most of the page directory entries won't be needed and can be marked unused, without needing a page table page to point to. So your memory hog now only needs a few KiB for paging overhead.

Sure, it takes a few more cycles to walk the extra level, but it's a reasonable tradeoff for thousands of dollars worth of memory savings. Anyway, the CPU cached page table entries, so it didn't have to walk them in memory very often.

Upvotes: 3

Related Questions