How does multi-level page table save memory space?
I am trying to understand how multi-level page table saves memory. As per my understanding, Multi-level page table in total consumes more memory than single-level page table.
Example : Consider a memory system with page size 64KB and 32-bit processor. Each entry in the page table is 4 Bytes.
Single-level Page Table : 16 (2^16 = 64KB) bits are required to represent page offset. So rest 16-bits are used to index into page table. So
*Size of page table = 2^16(# of pages) * 4 Bytes(Size of each page table entry) = 2^18 Bytes*
Multi-level Page Table : In case of two-level page table, lets use first 10-most significant bits to index into first level page table. Next 10-bits to index into second level page table, which has the page number to frame number mappings. Rest 12-bits represents the page offset.
Size of a second-level page table = 2^10 (# of entries) * 4 bytes(size of each entry) = 4 KB
Total size of all the second-level page tables = 2^10 (# of second-level page tables) * 4KB (Size of each second-level page table) = 4 MB
Size of first-level page table = 2^10(# of entries) * (10/8) Bytes (Size of each entry) = 1.25 KB
Total memory required to store first and second level page tables = 4 MB + 1.25 KB
So we need more memory to store multi-level page tables.
If this is the case, How does multi-level page tables save memory space ?
Answer
- 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 .