8
$\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$
1
  • $\begingroup$ Sure, sorry. I edit my main message. $\endgroup$ Nov 30, 2016 at 11:43

1 Answer 1

7
$\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.

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.)

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$
1
  • $\begingroup$ Where are the info about where on the external storage a swapped page has been saved, stored? I have heard that each process keeps another page table in addition to the global inverted page table, but I can’t find more info. $\endgroup$
    – HappyFace
    Apr 18, 2022 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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