OS Book written by Galvin et all states that if page size is 4KB and size of virtual space is 32 bits then 2^(32-12) page entries would be required which is too huge to store in memory!!

Therefore it recommends to break it down by paging the inner page table as well. Now my question is how does that reduce memory requirements? Shouldn't inner page table and outer page table both be in memory and just the computational requirements reduce because inner page table can now be indexed quickly with the help of outer page table??


Have you read Wikipedia's article on page tables?

There are two ways that a multi-level page table saves memory. First, you don't need to create parts of the page table for memory that isn't being used by the process: you only create the subtables for the parts of the virtual address space that are in use. Second, if you want to really live by the seat of your pants, you can use your virtual memory system to swap parts of the page table out of physical memory.

  • $\begingroup$ This doesn't really answer my question. I was interested in memory requirements and you are telling me about demand paging. And if we consider your first point then imagine occurrence of worst case that process nearly occupies each frame of physical memory at once then memory requirements aren't being reduced. Hierarchical paging just pages the inner page table which means they are not allocated contiguously but divided into pages in main memory which doesn't reduce memory requirements. $\endgroup$
    – Mohit Jain
    Feb 6 '14 at 9:58
  • $\begingroup$ @MohitJain By not creating subtables for unused regions, 4 KiB of PTEs is replaced by 32 bits of a single (invalid) Page Directory Entry. For every region beyond the first (the top level table has 4 KiB overhead) that is unmapped, 4KiB are saved relative to a flat table. In the worst case--1024 mapped pages each in a different 4 MiB region--this uses 4KiB more memory. In the common case, multiple regions are unoccupied, saving 4 KiB each (after the first). Swapping out subtables also saves memory. $\endgroup$ Feb 6 '14 at 14:09

For an example take a scenario like this .

[2].                   [7]
[3].                   [8]
[4].                   [9]
[5].                   [10]

Inner              Second page table’
Page table’

So we can have 4 different addresses which starts with 2. (Ex:2,7/2,8/2,9/2,10). So like that there are 4 entries in the inner page table. So altogether there are 16 entries. But in the address space there are only 8. If we did not use multiple pages there would be 16. So this method reduces memory requirement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.