How does multi-level page table save memory space?
- In singlelevel pagetable you need the whole table to access even a small amount of data(less memory references). i.e 2^20 pages each PTE occupying 4bytes as you assumed.
Space required to access any data is 2^20 * 4bytes = 4MB
- Paging pages is multi-level paging.In multilevel paging it is more specific, you can with the help of multi-level organization decide which specific page among the 2^20 pages your data exists, and select it . So here you need only that specific page to be in the memory while you run the process.
In the 2 level case that you discussed you need 1st level pagetable and then 1 of the 2^10 pagetables in second level. So, 1st level size = 2^10 * 4bytes = 4KB 2nd level we need only 1 among the 2^10 pagetables = so size is 2^10 * 4bytes = 4KB
Total size required is now : 4KB + 4KB = 8KB.
Final comparision is 4MB vs 8KB .
Here is a primary advantage of multilevel page tables:
First, chop up the page table into page-sized units; then, if an entire page of page-table entries (PTEs) is invalid, don’t allocate that page of the page table at all.
Source. (Section 20.3)
Thus the amount of memory needed for the page table is not dictated by the size of the address space, but by the amount of memory that the process is using.
In addition, the page of page table entries can itself be paged if physical memory gets full - only the page directory needs be always present in memory.