3
$\begingroup$

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:

enter image description here

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ Sure, sorry. I edit my main message. $\endgroup$ – Buster Nov 30 '16 at 11:43
5
$\begingroup$

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. If a DRAM has $N$ pages of size 4096 bytes, and each inverted page table entry is 16 bytes, then the DRAM is of size 4096 $N$ bytes, while the page table is size 16 $N$, which is always 16/4096 = 1/256 $\approx$ 0.5% 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.)

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.