CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Other layouts

In plain words: Multi-level tables are good for 32-bit and 48-bit spaces. For address spaces of 64 bits, with a very sparse use, other layouts have been used.

Hashed page table. The virtual page number is put through a hash function, and the result is an index into a table. Each slot holds a chain of entries, each with a page number and a frame number, since different pages can hash to the same slot. The lookup goes to the slot and walks the chain until the page number matches. The size of the table depends on the number of pages in use, and not on the size of the address space.

Inverted page table. The ordinary table has one entry for each page of each process. An inverted table has one entry for each frame of the physical memory. Each entry records which page of which process lives in that frame. There is one table for the whole machine. A lookup must search the table for the entry with the given process and page number, which would be slow if done by scanning, so a hash table is added to find the entry fast.

Compare the sizes. A machine with 16 GiB of memory and 4 KiB pages has 16 GiB / 4 KiB = 4,194,304 frames. If each entry takes 16 bytes, the inverted table takes 4,194,304 × 16 = 64 MiB, whatever the number of processes. With ordinary tables, the memory used grows with the number of processes.

The price is a slower lookup and difficulty with sharing. If two processes share a frame, the inverted table holds only one process id and page number for that frame, so sharing needs extra structures. According to OSC, architectures such as the 64-bit UltraSPARC and the PowerPC have used inverted or hashed tables. General-purpose x86-64 systems use the four-level tree.

Inverted page table

An inverted page table is a single table for the whole system with one entry for each physical frame, recording the process and page that occupy the frame; a translation searches it, usually through a hash, for the entry that matches.

Example: a machine with 4,194,304 frames has an inverted table of 4,194,304 entries, however many processes run.

Check yourself: 1. What decides the size of an inverted page table? 2. Why does an inverted table need a hash for fast lookup? 3. Why is sharing a frame between processes harder with an inverted table?