TLB caching and page table structure design

Translation Look-Aside Buffer (TLB)

Typically, every data or instruction fetch requires two memory accesses: one for the page table lookup and one for the actual data or instruction fetch.

The TLB is a hardware cache that stores recently used virtual-to-physical address translation results. This exploits the tendency of programs to reuse the same data items repeatedly during execution.

TLBs also store protection bits and Address-Space IDentifiers (ASIDs) that uniquely identify each process, providing address space protection. This avoids the need to flush the cache at every context switch.

The OS can decide which policy to use in case of a TLB miss. Some stable entries can be wired down for permanent fast access.

Structure of the page table

If we aren’t careful, memory structures for paging can become prohibitively large.

On a 32-bit system with a 4 KB page size, there would be approximately 1 million pages. If each entry is 4 bytes, then each process could require up to 4 MB of physical address space for the page table alone.

Hierarchical page tables

This technique divides the logical address space across multiple page tables. Each section of bits corresponds to an index into the appropriate table in memory.

This allows lower-level page tables (based on the least significant bits) to be allocated only when the corresponding region of the address space is actually used.

This approach does not fully solve the problem on 64-bit systems, where a proper subdivision would require at least 4-5 levels of paging, resulting in 4-5 memory accesses just to resolve a physical address.

Hashed page tables

In hashed page tables, virtual page numbers are hashed to locate entries in a hash table. Each bucket contains a linked list of entries (to handle collisions), and each element stores the virtual page number, physical frame number, and a pointer to the next element.

This approach creates mappings only for pages that are actually in use. While this is space-efficient, it becomes computationally expensive for processes with a large number of allocated pages.

Inverted page table

Rather than having each process track all possible logical pages, we track all physical frames.

The page table has one entry for each physical page of memory, consisting of a virtual page number (VPN), process identifier, and other control bits.

This structure reduces the memory required to store each page table but increases lookup time, since it requires searching. To avoid a full table scan, a hash table is typically placed in front.

For shared memory, a physical frame entry can point to multiple PID/VPN pairs.

Modern systems

Modern systems such as x86-64 use multi-level hierarchical page tables, typically with 4 or 5 levels. Page tables are allocated on demand when the corresponding region of the address space is accessed.

The TLB caches recent translations, eliminating the need for multiple lookups.

Huge pages reduce the number of entries in the TLB, thereby increasing its efficiency.