Page table structure (and especially page table structure for software managed page tables) was a hot area of research in the mid 1990s. At its root this is just the problem of creating a data structure to represent a map from one set of integers (the keys (virtual addresses)) to another set of integers (physical addresses). So you should expect the answer to have something to do with hash tables or search trees or both. The "best" choice depends on:
- how large your virtual address space is (e.g., 32 vs. 64 bit)
- how large your physical address space is
- how sparse or dense your mapping is (what fraction of the virtual address space you expect an individual process to use)
- how clustered your mapping is (you may only be using 1/10th of 1% of the address space, but all the virtual addresses cluster into one of a few dense regions/segments (the code segment, the stack segment, ...)
- the "natural" page sizes supported by your tlb
- whether you have address space identifiers (ASIDs), and how big they are (thus dictating how frequently they need to be reused.)
- whether you need to be able to use a shared memory abstraction to share data between different processes
- whether you have multiple tlbs that need to be kept coherent with some kind of tlb shootdown
- whether you have a single process and just need to virtualize that single process's address space over a backing store, or whether you are using paging to provide protection between multiple processes
- where and how you are going to store information about pages that have been moved to backing store
- (and more, like how you want to choose pages to replace)
Here are some good things to read:
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.
For machines with virtual address spaces that are much larger than the physical address space the inverted page table is the traditional solution. The inverted page table has exactly as many entries as there are physical pages. The entry records the virtual address mapped to that physical address, and also includes a link pointer. You look up a virtual address by hashing it to find a starting entry in the inverted table, then searching the linked list starting at that entry until you either find the virtual address in question, or find the end of the list.
There are a number of problems with inverted page tables. They don't handle having multiple virtual addresses mapped to the same physical address, it is expensive to find all of the physical pages that have been mapped for a particular process (you need to walk the entire table looking for entries with that process's ASID), and you need a different data structure to record information about virtual pages that have been moved to backing store. From a performance perspective the inverted page table does poorly at leveraging spatial locality because adjacent pages hash to disparate locations in the inverted page table. The Huck and Hays paper suggests variations on the inverted page table to address some of the inverted page table's shortcomings.
Talluri, Madhusudhan; Hill, Mark D; Khalidi, Yousef A: A new page table for 64-bit address spaces, ACM Symposium on Operating Systems Principles (SOSP-15):184-200, 1995. doi:10.1145/224056.224071.
This paper suggests a different approach to dealing with the locality problems of the inverted page table. Essentially the inverted page table is used for super-blocks made up of some number (16 in the paper) of normal pages. Thus you get the nice behavior of the inverted page table (proportional to the size of physical memory) but get some locality benefits because subsequent tlb misses tend to be for other pages in the same super-block.
Bala, Kavita; Kaashoek, M Frans; Weihl, William E: Software Prefetching and Caching for Translation Lookaside Buffers, USENIX confernce on Operating Systems Design and Implementation (OSDI-1):18, 1994.
This paper suggests that no matter what structure you use for the page table, you should augment the hardware TLB with a large, direct-mapped, software tlb. The hardware tlb usually needs to be quite small so suffers from capacity misses. You try to cover a large percentage of the capacity misses by finding the appropriate entry in the direct-mapped software tlb. The hope is that the software tlb is relatively quick and covers most accesses, and then you can use a more complicated structure (like a forward-mapped page table) for the few remaining misses.
So there are lots of choices, and there are lots of variables to consider. The best data structure choice really depends on the characteristics of your particular machine and your particular workload. You are trying to optimize for a sparse, but chunky, mapping function, trying to make sure you can handle operations beyond just lookup efficiently, and trying to leverage the spatial locality in the address stream to minimize cache misses while accessing the page table.
