# What is inverted table ?

66 views
What is inverted table ?
posted Sep 1, 2014

+1 vote

I am try to elaborate inverted Page Table with example:

Lets have a system in which the virtual address space is 64 bits, the page size is 4KB, and the amount of
physical memory is 512MB.

How much space would a simple single-level page table take?
Such a table contains one entry per virtual page, or 264−12 = 252 entries. Each entry would require about 4 bytes, so the total page table size is 254 bytes, or 16 petabytes (peta- > tera- > giga-)! And this is for each process! Of course, a process is unlikely to use all 64 bits of address space, so how about using multilevel page tables? How many levels would be required to ensure that each page table require only a single page? Assuming an entry takes a constant 4 bytes of space, each page table can store 1024 entries, or 10 bits of address space. Thus d52/10e = 6 levels are required. But this results in 6 memory accesses for each address translation!

But notice that there are only 512MB of memory in the system, or 229−12 = 217 = 128K physical pages.
If we can somehow manage to store only a single page table entry per physical page, the page table size
decreases considerably, to 2MB assuming each entry takes 16 bytes. And since processes share physical
memory, we need only have a single global page table.

This is the concept of an `inverted page table`.