CS162, Spring 2004 UC Berkeley Topics: Inverted Page Tables, TLBs
Discussion #10
Amir Kamil 4/1/04
1
1.1
Inverted Page Tables
Introduction
Consider a system in which the virtual address space is 64 bits, the page size is 4KB, and the amount of physical memory is 512MB. How much space would a simple single-level page table take Such a table contains one entry per virtual page, or 26412 = 252 entries. Each entry would require about 4 bytes, so the total page table size is 254 bytes, or 16 petabytes (peta- > tera- > giga-)! And this is for each process! Of course, a process is unlikely to use all 64 bits of address space, so how about using multilevel page tables How many levels would be required to ensure that each page table require only a single page Assuming an entry takes a constant 4 bytes of space, each page table can store 1024 entries, or 10 bits of address space. Thus 52/10 = 6 levels are required. But this results in 6 memory accesses for each address translation! But notice that there are only 512MB of memory in the system, or 22912 = 217 = 128K physical pages. If we can somehow manage to store only a single page table entry per physical page, the page table size decreases considerably, to 2MB assuming each entry takes 16 bytes. And since processes share physical memory, we need only have a single global page table. This is the concept of an inverted page table.
1.2
Linear Inverted Page Tables
The simplest form of an inverted page table contains one entry per physical page in a linear array. Since the table is shared, each entry must contain the process ID of the page owner. And since physical pages are now mapped to virtual, each entry contains a virtual page number instead of a physical. The physical page number is not stored, since the index in the table corresponds to it. As usual, information bits are kept around for protection and accounting purposes. Assuming 16 bits for a process ID, 52 bits for a virtual page number, and 12 bits of information, each entry takes 80 bits or 10 bytes, so the total page table size is 10 128KB = 1.3MB. In order to translate a virtual address, the virtual page number and current process ID are compared against each entry, traversing the array sequentially. When a match is found, the index of the match replaces the virtual page number in the address to obtain a physical address. If no match is found, a page fault occurs. This translation procedure is shown in gure 1. While the table size is small, the lookup time for a simple inverted page table can be very large. Finding a match may require searching the entire table, or 128K memory accesses! On average, we expect to take 64K accesses in order to translate an address. This is far too inecient, so in order to reduce the amount of required searching, hashing is used.

下一页