Hierarchical page tables vs. Inverted tables

Question

I read about a page structure of the memory and can't get some points:

• Page table: As I understood the process (like Intel i5) has the page table and TLB that integrated in its crystal, it isn't? But this table doesn't contain addresses of virtual pages, so OS must have yet one page table in the operative memory. So?

• Inverted tables: I understood that it has the page table but this table contains addresses of real blocks of the memory. And I got a nothing more. Where does this table located in the process or OS provides it in the operative memory. What's a hash-function for?
  
  From the picture. PID - Process ID (What's it for), p - page number (physical page or virtual page? If it's a physical page, what's this table for?).

Pls, do not refer me to Wiki and etc. I read it already and I couldn't get. Can a someone explain it clearer?

Answer 1

For learning purposes you should start with plain vanilla page tables. Ignore inverted page tables to get started because they are an oddball used in a very few processors.

The simplest case is a single level page table. In that case, the logical address consists of a logical page number and an offset within that page. To translate from logical pages to physical page frames, you take the page number, use that as an index into the page table. The page table then specifies the physical page frame (if there is one) the page is mapped to.

The next level of complexity is a multi level page table. In that case, the logical page number is broken down into bit fields, where each field represents a level in the table. The most significant bit field is in index into the top level page table. The corresponding page table entry references another page table. The next most significant bit field is an index into that page table. The process repeats until you get to the last page table level where the entries specify physical page frames.

Note that in this system the page table maps from logical address to physical page frames. There is no direct mapping between physical page frames and logical addresses.

For inverted page tables you have to relearn everything. There is a single page table with an entry for each physical page frame. The page table indicates the corresponding virtual page (if any) mapped to it.

In the inverted page table system, the processor can map from physical page frames to logical pages directly. In order to map from logical page frames to physical pages, the processor has to scan the page table (relying heavily on caching).

The mechanics of normal page tables are pretty much the same among systems (the major difference being the number of levels). However, there is no such similarity in systems that use inverted page tables.

If the system using inverted page tables uses a single, system wide table (as opposed to one table per process) there must be a PID field in the table to resolve the ambiguity of processes having the same logical pages mapped to different physical page frames.

One way to do the lookup of logical page/PID combinations in the inverted page table is to use a separate hash table. That's the PID in your diagram. You "p" appear to be logical page numbers.

To get around in the real world, you just need to know that inverted page tables exist and their basic operation.