Why we need multiple levels of page tables?

Question

As we know, we use page table to transform virtual memory address to physical memory address, by this way, we can improve the efficiency of memory usage. When only populate the physical memory if needed.

My question is: We have page table to solve that problem, why we need multiple levels of page tables?

Vulpes · Answer

Well, the reason for having a multilevel page table in the first place, is to save memory so that there is more available to the process itself. Instead of having a single page table (which can be quite large for large processes), you split it up into smaller parts and load them as needed. Such a scheme will clearly make the procedure of mapping virtual addresses to physical addresses slower on average, though this will be mitigated to some extent by reducing the time taken to do a 'page walk' once the correct page table has been loaded. However, you can improve efficiency by always keeping those page tables which are most commonly used (usually those representing the top and bottom address blocks) in main memory. You only then need to load other page tables as needed.

steven · Answer

Hi Vulpes, i want to know the details how the efficiency be improved? Could you please explain to me more details? Thanks in advance.

Vulpes · Answer

A multilevel page table contains page tables for individual blocks of virtual memory, rather than for virtual memory as a whole. The rationale is that, for a given process, the top and bottom blocks of virtual memory tend to be the ones which are used most often and so efficiency can be improved by having separate page tables for these blocks. For more detail I'd check out this Wikipedia article: http://en.wikipedia.org/wiki/Page_table