Difference between page table and inverted page table

Question

I do not understand the difference between page table and inverted page table. I know that both are used to translate the logical addresses into physical addresses produced by the processes necessary to store data in memory.

This is what I know on the page table.

Generally each page table contains an element for each virtual page and a table exists for each process. This can lead to huge tables (programs with many pages).

I can imagine a page table like this:

Instead, this is what I know on the inverted page table.

It has only one page table for all processes. This table has an entry for each real page (block of physical memory). Each element contains the virtual address of the page stored in that physical location, with information about the process that owns that page.

So I represent the inverted page table like this:

Am I doing it right? Did I get it right?

Thank you

---

I don't understand if the information I have learned theoretically then I understood well.

I do not think that is more efficient an interved page table than a normal page table, indeed I find it most confusing.

As I understand it, each frame of the physical memory has a corresponding entry in the inverted page table. I suppose that the memory has a large number of frames, then the inverted page table is huge and how do I keep it in RAM? While if you use the page tables "normal", I do not keep all of them in memory at the same time, you just keep those of the currently active processes, or not?

And it is reversed (the arrows are reversed), as I map a logical address into a physical?

Answer 1

An inverted page table is just a hash map. An inverted page table always fits in DRAM because it is proportional in size to the DRAM.

A DRAM total space is divided into $N$ page frames. If the size of a page frame is 4096 bytes, then the DRAM is of size 4096 $N$ bytes.
Assuming that an inverted page table entry is 16 bytes, and considering that there is an entry for each physical memory frame, then the page table is of size 16 $N$. This corresponds to 16/4096 = 1/256 $\approx$ 0.4% of the memory.

Your picture of the inverted page table is not correct. Here is the picture from the original paper about inverted page tables (Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993. doi:10.1145/165123.165128.)

It's a hash table. Each entry of the hash table needs to store both a virtual address and a physical address. The virtual address is there to check for hash conflicts.

The reason you can guarantee the total number of entries for the HPT (hash page table) plus the collision resolution table is just $N$ (the number of physical pages), is that there can be only one entry in the tables for each physical page.