How do I save space with inverted page tables?

Question

Why do we save memory if we use inverted page tables to map virtual addresses to physical ones? If we have for example two processes which both have 4 pages we would have 8 entries in two different tables pointing from virtual to physical address:

Process 1:
[0] = 1
[1] = 5
[2] = 63
[3] = 0

Process 2:
[20] = 14
[21] = 55
[22] = 11
[25] = 9

If we would use inverted page tables we would only have one big table pointing it the other way around. But in size they equal.

2) Inverted page table

[0] = <p1 | 3>
[1] = <p1 | 0>
[5] = <p1 | 1>
[9] = <p2 | 25>
[11]= <p2 | 22>
[14]= <p2 | 20>
[55]= <p2 | 21>
[63]= <p1 | 2>

Answer 1

The page table in the first case is a per process data structure.Every process has a pointer to its own page table ,this pointer gets loaded in the %CR3 register when the process is scheduled.Also it is saved when is it context switched along with other registers.

But an inverted hash table is a global data structure.The OS which uses this technique will use some locking mechanism to give access to only 1 process at a given point of time.(imagine 2 process on 2 cores accessing a global data simultaneously).

Assuming 4GB of per process ram and 4096 page size, In the first case each process has 4GB/4096 , (no of entries in its page table * size of each page table entry) and all this will eat up space, for every process that is created/forked.The total memory used for mapping virtual to physical is sum total of page table size of all process.This is simpler approach since on every context switch you will only change a pointer ,nothing complex.

In the second case you will have a single table with only 4GB/4096 entries,so space is saved,but the memory management becomes complicated, since this a global data , you will have to add more information in each entry telling how the current owner is (as you have shown)etc.The MMU/OS has to take care synchronization.

But the example you have given is not accurate , on a real system with per process page table the entire address can accessed, in your case process p1 has 4 pages and p2 has different set of pages. In reality both process can access same virtual address , mapped to different physical frame.So each table in your must have had 8 entries each.

Answer 2

The page table has to be on one block (you get the pages as in an array). You get 2 things from inverted table.

The dir table is getting smaller, for example, instead of 2^20 table size and offset of 2^12, you get, 2^10 dir table size.

Then instead of getting (2^20) * (2^2) Bytes memory for the page table, most of the pages would be mapped in the disk and you'll get it allocated only if a process needs them.

In your case, instead of all process will have a page table of the size of 2^20 * 2^2 Bytes, you'll have only 2^10 * 2^2 Bytes for the dir table and another one 2^10 * 2^2 Bytes for the page table. that is a big difference, instead of 2^22 Bytes, you have 2^13.

I hope it was clear.

Answer 3

The inverted page table is smaller because its size depends on the memory size instead of the virtual address space size. If the virtual address space is 2^48, you could have 2^36 page table entries per process.

With inverted page tables, the number of page table entries is only dependent on the size of memory. Say you have 4GB of memory, then your inverted page table would have 2^32 - 2^12 = 2^20 entries. This is for any amount of processes too.