Many systems, such as the System/370, use this page-table structure. Suppose we have a computer system with a 32-bit virtual address and a 4K page. The VPN size for this address is 20 bits. If we further assume 4 bytes per page-table entry, the size of the page table would be 4 MB. A memory table that occupies 4 MB is fairly large, but it is still workable for a system with large memory sizes. This is not the case when the virtual address is larger than 32 bits. The size of a conventional page table is prohibitively large when the virtual address is 48 bits or 64 bits long.
The System/38 was the first major computer system in the industry to use an inverted page table. An inverted page table has one entry for every real page (page frame) in memory, rather than one entry for every virtual page on disk. The total size of this table is directly related to the memory size. The bigger the memory, the larger the page table, but the percent of memory the table uses is always the same.
The difficult part of an inverted page table is determining how to locate the correct page-table entry. You no longer can use the VPN to directly index into the page table, because there is no longer a one-to-one mapping of the VPN to a page-table entry. So you must use some other method. The technique used in the AS/400 is to apply a hashing function to the VPN to identify a page-table entry.
Hashing
Hashing always has been a difficult concept to explain. The hash function on an AS/400 takes some high-order bits out of the VPN and XORs them with some low-order bits from the VPN. This value is ANDed with mask bits from a special register that contains the size of the page table. Finally, this result is ORed with the real address of the page table. The result of this is a 52-bit real address into the page table. Only a handful of people really understands (or cares) about this hashing function and how it works, yet many people want to understand why it works.
Several years ago, while pondering how to explain hashing to System/38 developers, I was walking through a Sears store in Rochester. A few days earlier, I had placed an order with the catalog sales department and was curious about whether my order had been received. When I inquired about my order at the catalog sales desk, I was asked for the last two digits of my telephone number. I said it was 83. On the wall behind the desk were 100 pockets numbered from 00 to 99. The person behind the desk pulled a stack of orders out of the pocket numbered 83 and began searching for my order. When the paperwork for my order was not found, I was told my order had not been received. I immediately blurted out, “You just had a page fault.” The somewhat surprised Sears employee had no idea what I was talking about, but I suddenly realized how to explain hashing. Sears was using a hashing function to track the orders that had been received, similar to the way we track which pages are in memory.
Sears had determined it could uniquely identify a customer by name and telephone number. Rather than keep a record on every customer who could place an order with its catalog sales department, the company decided to keep records on only those customers whose order had been received but not yet picked up. To speed the search for an order, the employee would select a portion of the total identity — the last two digits of the telephone number. So all orders received were sorted according to these two digits. When an inquiry about an order was made, only one of the 100 pockets had to be searched to find a match for the name of the person who placed the order.
The hash function Sears used (selecting the last two digits of the telephone number) ensured a relatively uniform distribution of orders across the 100 pockets, which meant it would take about the same amount of time to search through any of the pockets. If, for example, Sears had selected the first two digits of the phone number, a few of the pockets would be very full and others would be empty (most communities use only a few telephone prefixes, so selecting the first two digits would give a poor distribution). Similarly, the combination of XORs, ANDs, and ORs to create the hash code in an AS/400 ensures a uniform distribution of accesses across the “pockets” in the page table.
On the AS/400, the equivalent of the Sears pocket is called the page table entry group (PTEG). Each PTEG contains eight page table entries (PTEs). The hash algorithm identifies one of the PTEGs. The eight entries in this group must then be searched to find the one with a VPN that matches the VPN of the virtual address being translated. This search is necessary because many virtual addresses map to the same PTEG. This is analogous to the Sears example — more than one customer can have the same last two digits of a telephone number. The pocket identification just says all the orders in that pocket belong to people with telephone numbers having the same last digits. The orders must be individually searched to find a particular customer’s.
Because the number of orders received but not picked up by the customer could fluctuate during the day, Sears needed to accommodate this variability. Sears used a fixed number of pockets with a variable number of entries per pocket. The AS/400 also uses a fixed number of pockets, but as we just saw, it also has a fixed number of entries per pocket. The particular VPN we are looking for may or may not be in one of the eight PTEs. If there are more entries than can fit into a PTEG, a secondary page table is used and this table can have a variable number of entries.
In most AS/400 implementations, the number of PTEGs is at least one-half the number of real pages in the memory. With eight entries per PTEG, this means a table this size can map four times the number of pages that can be held in memory. Put another way, the average number of PTEs used per PTEG is only two. This average assumes the hashing function provides a uniform distribution across all PTEGs. There are situations when this will not be true, and one or more PTEGs will have more than eight entries. In those cases, the extra entries will have to be kept in the secondary page table. Suppose one of the pockets used by Sears got too full to hold all the paperwork. Some of the orders would have to be removed from the pocket and put somewhere else. This would be equivalent to having a secondary page table.