Page Tables for Large Memories

Page Tables for Large Memories

TLBs can be used to speed up virtual address to physical address translation over the original page-table-in-memory scheme. But that is not the only problem we have to deal with. Another problem is how to deal with very large virtual address spaces. Below we will discuss two ways of dealing with them.

Multilevel Page Tables

As a first approach, look at the use of a multilevel page table. A simple example is illustrated in Figure 1. In Figure 1(a) we have a 32-bit virtual address that is partitioned into a 10-bit PT1 field, a 10-bit PT2 field, and a 12-bit Offset field. Since offsets are 12 bits, pages are 4 KB, and there are a total of 220 of them.

The secret to the multilevel page table method is to avoid keeping all the page tables in memory all the time. Particularly, those that are not required should not be kept around. Assume, for instance, that a process needs 12 megabytes, the bottom 4 megabytes of memory for program text, the next 4 megabytes for data, and the top 4 megabytes for the stack. In between the top of the data and the bottom of the stack is a huge hole that is not used.

In Figure 1(b) we see how the two-level page table works in this example. On the left we have the top-level page table, with 1024 entries, corresponding to the 10-bit PT1 field. When a virtual address is presented to the MMU, it first extracts the PT1 field and uses this value as an index into the top-level page table. Each of these 1024 entries represents 4M because the entire 4-gigabyte (i.e., 32-bit) virtual address space has been chopped into chunks of 4096 bytes.
A 32-bit address with two page table fields

The entry located by indexing into the top-level page table yields the address or the page frame number of a second-level page table. Entry 0 of the top-level page table points to the page table for the program text, entry 1 points to the page table for the data, and entry 1023 points to the page table for the stack. The other (shaded) entries are not used. The PT2 field is now used as an index into the selected second-level page table to find the page frame number for the page itself.

As an instance, consider the 32-bit virtual address 0x00403004 (4,206,596 decimal), which is 12,292 bytes into the data. This virtual address corresponds to PT 1 = 1, PT2 =  2, and Offset =  4. The MMU first uses PT1 to index into the top-level page table and get entry 1, which corresponds to addresses 4M to 8M. It then uses PT2 to index into the second-level page table just found and extract entry 3, which corresponds to addresses 12288 to 16383 within its 4M chunk (i.e., absolute addresses 4,206,592 to 4,210,687). This entry includes the page frame number of the page containing virtual address 0x00403004. If that page is not in memory, the Present/absent bit in the page table entry will be zero, causing a page fault. If the page is in memory, the page frame number taken from the second-level page table is combined with the offset (4) to construct the physical address. This address is put on the bus and sent to memory.

The interesting thing to note about Figure 1 is that although the address space includes over a million pages, only four page  tables are really required: the top-level table, and the second-level tables for 0 to 4M (for the program text), 4M to 8M (for the  data), and the top 4M (for the stack). The Present/absent bits in 1021 entries of the top-level page table are set to 0, forcing a page fault if they are ever accessed. Should this happen, the operating system will notice that the process is trying to reference memory that it is not supposed to and will take appropriate action, such as sending it a signal or killing it. In this instance we have chosen round numbers for the various sizes and have picked PT1 equal to PT2, but in actual practice other values are also possible, of course.

The two-level page table system of Figure 1 can be expanded to three, four, or more levels. Additional levels give more flexibility, but it is uncertain that the additional complexity is worth it beyond three levels.

Inverted Page Tables

For 32-bit virtual address spaces, the multilevel page table works reasonably well. On the other hand, as 64-bit computers become more common, the situation changes significantly. If the address space is now 264 bytes, with 4-KB pages, we need a page table with 252 entries. If each entry is 8 bytes, the table is over 30 million gigabytes (30 PB). Tying up 30 million gigabytes just for the page table is not a good idea, not now and probably not next year either. As a result, a different solution is required for 64-bit paged virtual address spaces.

One such solution is the inverted page table. In this design, there is one entry per page frame in real memory, rather than one entry per page of virtual address space. For instance, with 64-bit virtual addresses, a 4-KB page, and 1 GB of RAM, an inverted page table only requires 262,144 entries. The entry keeps track of which (process, virtual page) is located in the page frame.

Although inverted page tables save vast amounts of space, at least when the virtual address space is much larger than the physical memory, they have a serious negative aspect: virtual-to-physical translation becomes much harder. When process n references virtual page p, the hardware can no longer find the physical page by using p as an index into the page table. Instead, it must search the entire inverted page table for an entry (n, p). Moreover, this search must be done on every memory reference, not just on page faults. Searching a 256K table on every memory reference is not the way to make your machine blindingly fast.

The way out of this difficult situation is to use the TLB. If the TLB can hold all of the heavily used pages, translation can happen just as fast as with regular page tables. On a TLB miss, however, the inverted page table has to be searched in software. One possible way to complete this search is to have a hash table hashed on the virtual address. All the virtual pages currently in memory that  have the same hash value are  chained together, as shown in Figure 2. If the hash table has as many slots as the machine has physical pages, the average chain will be only one entry long, greatly speeding up the mapping. Once the page frame number has been found, the new (virtual, physical) pair is entered into the TLB.

Comparison of a traditional page table with an inverted page table
Inverted page tables are common on 64-bit machines because even with a very large page size, the number of page table entries is extremely large. For instance, with 4-MB pages and 64-bit virtual addresses, 242 page table entries are required. Other approaches to handling large virtual memories can be found in Talluri et al. (1995).


multilevel page table, virtual address, inverted page table, hash table