So how big is the gap in most programs?
It is huge.
How many 4kb pages are being used in the above process?
14 MB / 4 Kb = 14 * 2^20 / 4 * 2^10 = 3.5 * 2 ^10 (approx 4*2^10 = 4MB)
What does that say about most of the 220 page table entries for this process?
They will be empty.
So do we need to keep the empty page table entries in memory?
No, they will never be used so why keep them in memory. Lets just keep the one's we need.
Multi-Level Page Table Implementation:
A multi-level page table system (on a 20 bit system with 4kb pages) works as follows:
The Virtual address is now divided slightly differently.
There are two page table indexes
The first page index is used to index the outer page table.
Each entry in the outer page table can possibly point to a second level page table.
The present bit in the outer page table is used to indicate if there is a second level page table for this entry.
The second page index is used to index the second level page table pointed to by the outer page table.
The entry of the second level page table might contain the page frame number of the desired page.
If the present bit of the second level page table indicates the presence or absence of a page in the physical memory.
If the present bit is a 1 then the page frame number is contained in the entry.
If the present bit is a 0 then a page fault occurs and the virtual page must be brought into the physical memory.
In a 32 bit system the virtual address might be broken up as follows:
What size are the pages in this system?
They would be 4Kb because the offset has 12 bits.
What is the size of each second level page table?
Each second level page table will have 1024 entries because the second Index is 10 bits. If each entry is 4 bytes as we assumed previously that makes each table 4kb.
interesting that the second level page tables are exactly the same size as a page.
is it a coincidence or was it done on purpose?