On the AS/400, if a PTE is not found in either the primary or the secondary page tables, we have a page fault. Remember: We have a PTE in one of these tables for every page in memory. Not finding the PTE means the page is not in memory, which we define as a page fault. The memory-management component of SLIC must go to the disk and bring in the requested page. As part of this operation, it also must update the page table to reflect the fact that the new page is in memory. Of course, to make room for the new page, the memory-management component may have to bump some other page.

The following three sections are really hot, so we are giving them three peppers. The first of these sections deals with the virtual-to-real address-translation process, which uses the page-table entries. I have included this section for completeness and for those readers who love to play with bits. The next section describes how either the SLIC or the translator can control the memory access to every page. This type of control is needed in a multipipelined, multilevel memory RISC processor because the memory operations can be performed in a different order by the processor than they appear in the instruction stream. The PowerPC architecture provides four mode-control bits for the software to use, and I briefly describe them here. This can become a very complex topic. Finally, the last of these sections describes how an access to a page is protected. Each page can be treated as a read/write, read only, or no-access page, depending on the settings of the processor state and the protection keys in both the segment table and the page table. This, too, can be a very complex topic. If you need something with more spice than the previous few sections, try one or all of the next three.

Page Table Entry

Each PTE is 16 bytes long, as shown in Figure 8.6. The first field in each entry is 57 bits long and is called the abbreviated virtual page number (AVPN). Astute readers will remember from Figure 8.4 that the full VPN has only 52 bits. So how can an abbreviated form be longer? The PowerPC architecture is designed to support virtual addresses up to 80 bits long. The VPN for an 80-bit virtual address is 68 bits long, so 57 bits is indeed an abbreviated form. The AVPN can be used rather than the complete VPN, because at least 11 low-order bits of the VPN are used in the hash function and do not need to be repeated. Similarly, Sears would not have to include the last two digits of the customer’s telephone number on the order form, because these digits are used in the hash function and do not need to be repeated in the search process. The AVPN for the 64-bit virtual address used in the AS/400 is only 41 bits long. The high-order 16 bits of the AVPN are set to 0.

Figure 8.6  Page Table Entry Format

Each of the PTEs in the PTEG are searched in turn for a match with the VPN of the virtual address. If the AVPN matches during the search of a PTE and the valid bit is on (V = 1), then the 40-bit RPN in the entry is passed to the memory-addressing hardware where it is joined with the 12-bit byte offset to form the real address.

The other bits in the PTE provide additional information about the page. The SW bits are reserved for use by the memory-management component of SLIC. The H bit identifies whether this entry is in the primary or secondary page table, each of which uses a slightly different hash function. The TS bit tells whether this page contains pointers and therefore has some tag bits set to 1. The AC bit, if it is on, invokes the data address compare mechanism, which provides a means to detect loads and stores to a block of memory. The hardware sets the R and C bits to a value of 1 every time this page is referenced (R bit) or changed (C bit). The remaining bits deal with access modes and page protection. We discuss these topics shortly.

A few more words are in order about the R and C bits. Memory management uses the settings of the R and C bits to determine which page to bump from the memory when a page fault occurs and a new page must be fetched into memory. Memory management also uses these bits whenever another SLIC component or a translated MI program requests a bring, clear, or purge operation.

To speed the search for a page frame to replace, memory management maintains a “search list” of all the page frames that are eligible to be replaced. On a page fault (or a bring or a clear), memory management first searches this list for a page frame that has both the R and C bits set to 0. This combination means the page in the frame has not been recently accessed and has not been changed — it is the best candidate to replace. After a page replacement, all the R bits are reset to a value of 0. In this way, the R bits identify which page frames have been referenced since the last page replacement. The least recently used pages have R values set to 0.

While the page-replacement algorithm is looking for a page to replace on the search list, if it encounters a page frame that has been changed but not recently referenced (R = 0, C = 1), it places the page on the “change list.” When the change list accumulates a sufficient number of pages, one or more page-out tasks are started. The pages are written to disk and then returned to the search list (with C = 0), where they are eligible for replacement, assuming they are not referenced or changed again. The reason for these page-out tasks is to prevent memory from being filled with changed pages that have not recently been referenced.

From our discussion so far, it should be obvious that searching the page tables takes a long time — so long that it would be intolerable if we had to do it for every memory access. Fortunately, once a page has been accessed for the first time, there is a very high likelihood that page will be referenced again in the near future. This is the principle behind using lookaside buffers — if you are likely to reuse the page table entry again, keep it around in a register that can be accessed quickly. For performance reasons, the hardware keeps a translation lookaside buffer (TLB) that holds PTEs that have been recently used. The TLB is searched before the page table is searched. The time required to search the TLB is very short compared to that needed to search the page table. The size of the TLB is usually selected to be large enough to have 95 percent or more of the translations performed in the TLB without having to go to the page table.