Virtual Address Space: It is the range of virtual(logical) addresses for a particular process.
Now, we use paging in order to efficiently allocate memory for every process. But the problem comes when the page table itself is so large that it uses a large amount of physical memory.
Suppose a processor has 32-bit virtual address space and a 4KB page size. This means that,
- Top 20 bits represent -> page number
- Virtual address space may contain 220 pages.
- If each page table entry is 4B, then we need 220 * 4 = 4MB for its page table alone.
- With several processes running on a machine this is not an ideal situation. That's why we go for multi-level paging.
To solve this, what we can do is,
- Split the 20 bits into two(10 bit each).
- First 10 bit for page table 1 and the next 10 bits for page table 2.
- The first-page table now points into the second-page table instead of the frame number. And the second-page table now points to the corresponding frame number.
- Total number of entries in page table 1 = 210
- So we have 210 second-level page tables.
- Size of first-page table = 210 * 4 = 4KB
- In order to access the page from memory, we only need the first-page table and one of the second-page tables in main memory. So the total size is 4KB + 4KB = 8KB.