134
`
`Virtual Memory
`
`20 Bits
`
`IO Bits
`
`Segment
`
`10 Bits
`
`Page
`
`IO Bits
`
`Displacement I MV'u-tual Address
`
`: ...... -. . . . .. . . . .. . .. .. . . . .. . . . ............................. :
`Page Table
`
`lM pages
`of
`lK enbies
`
`30Bit
`Real Memory
`Address
`
`Note:
`User/Supervisor
`E:..-tension
`Selected by
`mode
`
`'---------· {;~~
`
`.____,...~ i 20 Bits
`:
`' - -~ - - ' 20 Bits
`.... ................... 1:1. ~.~~~ ............... :
`FIGURE 3.14 MC88200 table structure.
`
`a pointer in the leaf tables that point not to the page in real memory
`but to another leaf table. This feature supports sharing of real pages but
`can significantly increase the number of references to memory that are
`required before a page fault is detected. I believe that there is a time(cid:173)
`out feature to stop endless looping around indirect addresses.
`MC88200. It is interesting to note that Motorola eliminated the
`programmability of the MC68851 in the MMU of the MC88200
`[MOTO90a]. The table structure of the MC88200 is shown in Figure
`3.14. This device supports a fixed page size of 4 Kbytes. The 32-bit
`effective address is extended by 20 bits using two registers found in the
`MMU that are loaded by the processor. Depending upon the mode of
`operation, the user of supervisor extension is concatenated to the effec(cid:173)
`tive address, providing a 52-bit virtual address. There are two levels
`of translation. The first level, called the segment table, has 2 30 entries
`of 20 bits that are concatenated with the 10-bit page field that address
`the page table. Motorola calls their system a segmented system; segment(cid:173)
`ation is provided by software that determines the values to be used in
`the extension registers. The balance of the system is a hardware-paged
`system.
`As with the i386, i486 page name translation systems, the MC88200
`is a partial implementation of a direct map. There are 23 0 entries in the
`page table rather than 240 as required for a full implementation. The
`number of entries is greater than that of the i386, i486, thus requiring
`fewer allocations of translation information to the page table.
`
`Control Bits
`
`The use of control bits in a multilevel page table system is illustrated
`with the MC88200, which has an extensive control bit repertoire to
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 151
`
`

`

`3.3 Virtual Memory Organizations
`
`135
`
`provide flexible support of differing operating. systems. The first level of
`control bits is contained in the two area descriptors that are selected by
`mode to extend the processor effective address, as shown in Figure 3.14.
`These bits, noted as C in the figure, consist of
`
`WT Write Through: controls the write policy of the cache;
`G
`Global: controls the scope of snoopy coherency measures
`(Chapter 5);
`Cache Inhibit: inhibits caching of local instructions;
`Translation Enable: if not set, no page name translation.
`
`CI
`TE
`
`The first-level table, known as the segment table, has entries called
`segment descriptors , with the following control bits:
`
`WT
`G
`CI
`SP
`WP
`V
`
`Write Through;
`Global;
`Cache Inhibit;
`Supervisor Protection: controls translation of supervisor;
`Write Protect: controls write protection;
`Valid: if not valid, translation fault (table not present).
`
`The second level, known as the page table, has entries called page
`descriptors , with the following control bits:
`
`WT
`G
`CI
`SP
`WP
`V
`M
`U
`
`Write Through;
`Global;
`Cache Inhibit;
`Supervisor Protection;
`Write P r otect;
`Valid (Page is valid);
`Modified: indicates that the page has been modified;
`Used: indicates that a page has been accessed.
`
`Note that some of the levels have control bits for the same function.
`An example is the WT, Write Through bit. These bits are ORed together,
`and if any one is set the resulting action is taken based on this test of
`the control bits.
`
`Inverted Page Table Translation
`Direct multilevel table translation has served well for processors with
`virtual addresses limited to 32 bits. With virtual address extensions,
`partial page table implementations have been required. In the early
`1980s designers at IBM contemplated very large virtual addresses and
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 152
`
`

`

`136
`
`Virtual Memory
`
`determined t~at a different translation method would be required. For
`a system with a 1-Kbyte page and a 52-bit virtual address, the leaf
`nodes would require approximately 6 x 242 bytes. Systems that followed
`this study are the IBM System 38 with a virtual address of 48 bits
`[HOUDB0. HOUD81] and the IBM RS/6000 with a 52-bit virtual address
`[OEHL90]. A direct page table for a large virtual address would not only
`be very large but also sparsely populated and inefficient. The inverted
`page translation systems described in this section are both small and
`densely populated.
`To reduce the size of the translation table, an inverted page table
`that contains only the virtual pages that are currently resident in real
`memory can be used [CHANS ] to translate long virtual addresses. An
`inverted page table can provide a substantial reduction in the size of
`the page tables and reduce the number of memory accesses required for
`a page name translation. The page name can be translated into the real
`address by either an associative search of the translation table, an n(cid:173)
`wise set associative search, or by hashing into a linked list. Current
`design practice does not use n-wise set associative searching, thus associ(cid:173)
`ative search and hashing are discussed in the following paragraphs.
`All known contemporary implementations of inverted page table
`virtual memory have been designed by either IBM, Hewlett-Packard.
`or the IBM/Motorola/Apple group (Sumerset). These systems will be
`described in the following sections.
`
`Inverted Associative Page Table Search
`An inverted associative page table (APT) has one entry for each of the
`pages in real memory. This page table is accessed by an associative
`search from the page name in the virtual address. As with all known
`virtual memory systems, an APT system is early select and congruent
`mapped.
`The Atlas [KILB62, MATI77] is an example of an inverted API'.
`This memory system has a page size of 512 words, a virtual address of
`2048 pages, and a real memory of 32 pages (16K words). A block diagram
`of the map is shown in Figure 3.15. The dotted arrow with A at its head
`signifies an associative search. The page table contains the page frame
`address and the page name of the pages in real memory, called tags. A
`page name is the key for an associative search of the tags. Note the one(cid:173)
`to-one correspondence in the number of entries in the page table and the
`number of page frames in real memory.
`A hit on the tags produces a 5-bit page frame address that is concat·
`enated with the 9-bit displacement from the virtual address. The result•
`ing 14-bit address is presented to the real memory. If the addressed page
`is not in real memory and therefore not in the page table, a miss occurs
`and the page is fetched from a drum memory in virtual address space.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 153
`
`

`

`3.3 Virtual Memory Organizations
`
`137
`
`Drum Virtual Memory
`
`PO 512Words
`
`. .
`.
`.
`.
`
`. . . . . . . .
`
`Virtual Address
`11 Bits
`9 Bits
`
`I Page Name I Displacement I
`'---y--1 ----·---
`
`Page Table
`
`0
`
`'fag
`
`: .
`
`31
`
`5 Bits
`
`Real Memory
`
`PO
`
`512Words
`
`.
`.
`.
`.
`
`P31
`
`' A
`
`*Page Frame Address
`
`P2047
`
`FIGURE 3.15 Atlas page name translation.
`
`The drum address is found by sequentially searching a table holding the
`11-bit virtual page number and the corresponding drum address (a pro(cid:173)
`cess described in Section 3.5.9).
`The designers of Atlas considered using a direct table method with
`the table in real memory. However, this form of translation requires
`that at least one real memory reference must be processed to see if there
`is a page fault and to generate the real memory address. This design
`would make every reference to real memory cost (at a minimum) two
`memory cycles. The APT method provides a faster associative search of
`a hardware table, adding only a small increment of time to the real
`memory access latency. Because it is faster, the associative method is
`superior and is used on the Atlas even though there was a significant
`circuit cost for the associative translation table.
`For very large virtual addresses and large real memory, the size of
`an inverted APT is too large and costly for consideration. The small
`virtual address of the Atlas will never be used again. However, the APT
`is used in systems in the form of translation lookaside buffers (discussed
`in Section 3.4).
`
`APT Control Bits
`
`Systems using APT control the page name translation process by an
`associative search mechanism and require no control bits. Recall that
`there is one table entry for each real page frame . The entries in the
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 154
`
`

`

`138
`
`Virtual Memory
`
`inverted page table contain the page base address in real memory and
`the page name. If there is a hit on the search, the translation is complete.
`If there is a miss, then there is a page fault.
`Protection bits should be required with the APT as with the other
`page name translation systems. However, as protection was not a re(cid:173)
`quirement for APT systems that were implemented , such as the Atlas,
`there are no examples to cite of protection bits. Protection bits are used
`in TLBs (described in Section 3.4), which are similar to APTs. For exam(cid:173)
`ple, valid bits are required to indicate the presence of valid translation
`information in the page table.
`
`Hashed Inverted Page Table Search
`
`The inverted translation scheme of the Atlas is costly to implement if
`the size of the real memory and the virtual address become very large.
`This is now the case with many virtual memory systems. Hashing is the
`translation technique of choice today for IBM systems with large virtual
`addresses. The index into an inverted page table is found by hashing
`the page name (the displacement bits are not hashed). The hash number
`is then used as an index into the page table, which provides the page
`frame address. This technique is properly known as key transformatwn
`[PRIC71]. The key transformation technique reduces the large number
`of virtual page addresses into one of a number of noncongruent classes
`in which the real page addresses are linked together.
`Hashed access into large address spaces or data structures was
`developed in the 1960s for access to symbol tables and the like [JOHN61,
`MORR68]. These techniques were then applied to the accessing of large
`files and have been, since the late 1970s, applied to virtual memory
`page name translation. A good hash transformation is one that "spreads
`the calculated address (sometimes known as hash addresses) uniformly
`across the available addresses" [MORR68]. The design of hashing func(cid:173)
`tions is beyond the scope of this book, however, a tutorial on hashing(cid:173)
`can be found in [LEWI88].
`It is possible to have a one level translation table that is accessed
`by hashing the virtual page name as illustrated in Figure 3.16. This
`method for translating virtual addresses into real memory addresses
`divides the virtual address into the page name field and the displace(cid:173)
`ment field. The page name field is hashed for an index that accesses the
`page frame table. The table contains entries for all of the pages that are
`resident in real memory-an inverted translation system. The page
`frame table entry carries the page name tag and the page frame address
`of the page in real memory. When the page table is accessed the tag is
`compared to the page name and, if the comparison is true, the page
`frame address is gated out and concatenated with the displacement to
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 155
`
`

`

`3.3 Virtual Memory Organizations
`
`139
`
`Virtual Address
`
`----c)-4------. Page Frame Table
`
`YIN
`
`Tag
`
`PFA*
`
`Real Memory
`Address
`
`Hash
`Generator
`
`Index
`
`FIGURE 3.16 Hashed page name translation.
`
`*Page Frame Address
`
`form the real memory address. If the comparison is false , the addressed
`page is not in real memory and a page fault is signaled.
`A problem with this simple hashed translation is that two or more
`virtual addresses can hash into the same value, creating a collision into
`the same page frame table entry. These collisions increase the page name
`translation fault rate, significantly increasing the average page name
`translation time. A number of techniques for managing collisions and
`reducing their performance impact have been developed and im(cid:173)
`plemented in real systems [MORR68]; a list of these techniques is given
`in Table 3.2 with examples noted. These examples will be described in
`the following paragraphs.
`
`One-Level Large Page Frame Table
`HP Precision Architecture. A system that uses a one-level page frame
`is the Hewlett-Packard Precision Architecture as shown in Figure 3.17
`
`Technique
`
`Example
`
`One-level large page frame table
`One-level linked list
`Two-level linked list
`One-level sequentially indexed list
`One-level disjoint collision table
`n-way set associative
`
`HP Precision Architecture
`None
`IBM S/38-RS/6000
`PowerPC 601
`Proposed [HUCK93]
`IBM S/360/168 TLB
`
`TABLE 3.2 Collision handling techniques.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 156
`
`

`

`140
`
`Virtual Memory
`
`46 Bits
`
`16Bits
`Space ID
`
`11 Bits
`
`26 Bits
`
`19 Bits
`
`V. Page No.
`
`11 Bits
`Displacement IVu-tual Address
`
`9Bits
`
`0
`
`Tag
`
`C
`
`PHA
`
`Real Memory
`Address
`
`Index
`Hash
`Generator 11 Bits
`
`20:17 _______ _.__.__ __ ~
`
`16 Bits
`
`FIGURE 3.17 HP PA page name translation.
`
`[MA.HO86, LEE89]. This sy tern depends on reducing the probability
`of a collision by implementing a large page frame table. Because the
`translation time through this system is quite fast, a translation look.aside
`buffer is not used. However, Hewlett-Packard describes this system as
`a translation look.aside buffer without another table structure for hand(cid:173)
`ling TLB misses.
`The virtual address is composed of an 11-bit displacement, a virtual
`page number (either 19, 35, or 51 bits), and a 16-bit space ID. Nine bits
`of the virtual page number and 11 bits of the space ID are hashed int.o
`an 11-bit index. This index references a one-level, direct page frame
`table, called a translation lookaside buffer by HP. An entry contains a
`26-bit tag that is compared to 26 bits in the virtual page name. The
`table produces a 16-bit page frame address that is concatenated with the
`11-bit page displacement. A collision (no match on the tag but with a
`true valid bit) requires a full virtual software page name translation.
`
`One-Level Linked List Page Frame Table
`The approach to collision management discussed in this section is com(cid:173)
`monly used today because it provides a good balance between speed and
`cost. A one level system that mitigates the problem of hashing into the
`same page table entry by using a linked list is shown in Figure 3.18.
`Each entry of the page frame table ( the name used in the IBM RS/6000)
`contains three fields: a page name tag, a page frame address, and a link
`field (chain). When a page is loaded into a page frame in real memory,
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 157
`
`

`

`3.3 Virtual Memory Organizations
`
`141
`
`Virtual Address
`
`YIN
`
`Tag
`
`Real Memory
`Address
`
`Hash
`Generator
`
`Index
`
`FIGURE 3.18 One-level hash accessed inverted page table!.
`
`*Page Frame Address
`
`its page name and the page frame address are placed into the page frame
`table.
`A virtual memory page name translation is performed by hashing
`the page name to an index into the page frame table. The page name
`field of the addressed entry is compared to the page name of the virtual
`address. If they are the same, the correct page frame address is concat(cid:173)
`enated with the displacement to give the real memory address. If the
`page name is not the same, a hash collision has occurred and the link
`pointer accesses another entry, and so on, until there is a match on the
`tags or a terminator symbol is encountered in the last entry. If the last
`entry has been accessed without a match on the page names, the refer(cid:173)
`enced page is not in real memory and a page fault results.
`A one-level hash accessed translation suffers from a significant prob(cid:173)
`lem. For some update cases, the entries in the page frame table must be
`moved to make room for the allocation of a new entry in the page frame
`table. Moving entries in the page frame table consumes time and reduces
`the overall performance of the system. Allocation in a one-level system
`is illustrated in Figure 3.19, which shows the states of the page frame
`table before and after allocation. Before allocation we see three linked
`lists of page translation information. Note that the page names A and B
`both hash into "l", the page name D hashes into "8", and the page names
`P, Q, and R hash into "17". In this example, the page frame table
`entries have been allocated into consecutive locations following the hash
`address and are linked via the link fields. A valid bit is needed in
`each entry to identify the page frame table entries that are allocated or
`vacant.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 158
`
`

`

`142
`
`Virtual Memory
`
`Page Frame Table
`1~
`1 A
`1 B
`2
`
`-
`
`~
`
`Page Frame Table
`1~
`1 A
`1 B
`2
`
`--~
`
`1 D
`
`1 D
`
`Terminator
`
`17 ~
`
`p
`1
`1 Q
`1 R
`
`18
`19
`
`-
`
`-
`
`_)
`
`0
`
`Before Allocation
`
`IV! Tag I PFA
`Page Table Entry
`
`17~
`18~
`19
`
`p
`1
`1 z
`1 R
`
`25
`
`1 Q
`
`-
`
`-
`
`~
`~
`
`After Allocation
`
`FIGURE 3.19 Allocation with a one-level hash accessed inverted page table.
`
`Consider what happens if a new page is allocated and its page name
`"Z" hashes to the value "18". The entry "18" in the page frame table is
`already occupied by Q and must be moved in order to vacate location
`"18". This can be accomplished by moving the Q entry into location "25'
`and adjusting the link pointers. A vacant entry is found by scanning the
`PFT until a "O" is found, signifying a vacant table entry that can be
`allocated.
`If there is a second allocation of a page with a page name that hashes
`into "18", its translation information is allocated to a vacant page frame
`table entry and appended to the linked list that starts with "18". Another
`situation exists for a new allocation hashed to an unused entry in the
`page frame table (the valid bit is 0). For this case, the tag and address
`information are allocated and the link field is loaded with the terminator
`symbol. This is a simple case, and no entry movement is required.
`
`Two-Level Linked List Page Frame Table
`A solution to the problem of page frame table movement is to introduce
`another level in the translation process that, in effect, provides an
`indirect pointer to the translation information in the page frame table.
`With a level of indirection, allocating new entries to the page frame
`table does not require that other entries be moved. This first-level tabll!y
`named a scatter index table in the early literature, is known as a hllsh
`index table in the IBM System 38, a hash table in the IBM 801, and a
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 159
`
`

`

`3.3 Virtual Memory Organizations
`
`143
`
`Virtual Address
`
`I Page Name I Displacement I
`
`Hash Anchor Table
`
`YIN
`
`Page Frame Table
`
`Real Memory
`Address
`
`Hash
`Generator
`
`Index
`
`FIGURE 3.20 Two-level hash accessed inverted page table.
`
`•Page Frame Address
`
`hash anchor table with the IBM RT PC and RS/6000, which is the term
`used in this text.
`A two-level system is shown in Figure 3.20 [JOHN61, MORR68].
`With this system, the page name is hashed for an index into the hash
`anchor table, which contains an index into the page frame table. The
`page frame table contains the page name (that is compared to the virtual
`address page name), the page frame address, and a link. The page frame
`address is concatenated with the displacement to form the real memory
`address.
`The allocation example in Figure 3.18 used for the one-level system
`is illustrated in Figure 3.21 with the before and after cases shown. Here,
`the hash anchor table contains a pointer into the page frame table. For
`this example, the linked list A, B is located starting at location 100 of
`the page frame table, D is located at 200, and the linked list P, Q, R
`starts at 300. A memory reference to pages P, Q, or R, for example,
`hashes into address "17" and the p9inter 300 is found that indexes to
`location 300 of the page frame table. The proper page frame address is
`found by compa•ring the tags to the virtu~l page name and traversing
`the linked list if necessary.
`When page "Z" is allocated, location "18" in the hash anchor table
`is vacant and the page frame table entry is placed in a vacant location,
`250 for example, of the page frame table. No movement of page frame
`table entries is required to effect the allocation of the new page. If a page
`is allocated with a page name that hashes into an already used hash
`anchor table address, the allocation can be to any vacant location in the
`page frame table. It is only necessary to append the entry to the linked
`list. The more successful the hashing function is in providing a uniform
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 160
`
`

`

`Hash Anchor Table
`
`Page Frame Tab lo
`100 1 A
`1 B
`
`-~
`
`Hash Anchor Table
`
`Page Frame Table
`1 A
`1 B
`
`-0
`
`100
`
`1 D
`
`1 p
`1 Q
`1 R
`
`-
`
`_)
`
`-:)
`
`200
`
`1 D
`
`250
`
`1 Z
`
`300
`
`1 p
`1 Q
`1 R
`
`Before Allocation
`
`Terminator
`
`IVI Tag I PFA
`Page Table Entry
`
`FIGURE 3.21 Allocation with a two-level hash accessed inverted page table.
`
`.,
`
`)
`
`-:)
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 161
`
`

`

`3.3 Virtual Memory Organizations
`
`145
`
`distribution of transformed keys, the more balanced will be the length
`of the linked lists.
`How many entries should there be in the page frame table and the
`hash anchor table? First consider the page frame table. Because an
`inverted page translation system has one entry for each page frame of
`real memory, the minimum number of entries is the number of real
`page frames . A large page frame table will have more vacant positions,
`reducing the length of the linked lists and the time required to find a
`page frame address.
`The size of the hash anchor table is determined by the desired
`performance. A large hash anchor table has a larger hashed address,
`reducing the frequency of collisions in the page frame table. Johnson
`[JOHN61] determined that the average number of probes (reference
`attempts) into the page frame table is a function of the size of the page
`frame table and the hash anchor table:
`
`p = 1 +
`
`no. of entries in page frame table
`2 x no. of entries in hash anchor table
`
`where P is the average number of probes into the page frame table to
`translate a page name.
`For example, if the hash anchor table has the same number of entries
`as the page frame table, 1.5 probes are required, on average, into the
`page frame table plus th~ access of the hash anchor table to translate a
`page name. If the hash anchor table has only 10% of the entries of the
`page frame table, six probes are required on average. An explanation of
`this model is found in the following consideration. If there is only one
`entry in the hash anchor table, every page name hashes into the same
`entry and all of the entries of the page frame table are linked together
`in one linked list. In this situation, the average number of probes ap(cid:173)
`proaches half the number of entries in the page frame table. This be(cid:173)
`havior is as expected from the time required to search a linked list
`sequentially. On the other hand, if the hash access table is very large,
`there are no collisions and each entry in the page frame table is unique
`(not linked). In this case only one probe is required.
`Four IBM systems (S/38, 801, PC RT, and RS/6000) use a two-level
`hash access technique and are discussed in the following paragraphs.
`IBM S/38. The virtual memory of the S/38 resulted from research
`at IBM in the late 1960s and early 1970s on the so-called Future System,
`which was abandoned due to lack of compatibility with S/370 [LEVY84].
`The _S/38 virtualized a segmentation system on top of the hardware(cid:173)
`paged system [HOUD79, HOUD81]. The S/38 has a 48-bit virtual
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 162
`
`

`

`146
`
`Virtual Memory
`
`40 Bit Vinual Address
`Seg. ID
`
`Page Name I Displacement I
`
`Page Frame Table
`:··iiasiiAnciior·tahie··················· ····························
`
`Page
`
`Seg. ID. Page Nnmr C PFA-LNK
`
`Real Memory
`Addreu
`
`Index
`: ...................... !J?.~~···································
`
`FIGURE 3.22
`
`IBM 801 page name translation.
`
`address, with a 512-byte page. The 39-bit virtual page name is hashed
`by logical XORing three fields (two of which are bit reversed) in the
`virtual page name in order to generate a 7-bit index into the hash anchor
`table. A page frame table index that indexes into the 128-entry page
`frame table is produced, and the entries in the page frame table are
`linked together with pointers. Approximately 2.5 memory accesses are
`required to translate a page name in the page frame table; the total
`translation time is 3.5 accesses.
`IBM 801. The inverted page table system of the S/38 evolved into
`the virtual memory system of the experimental IBM 801; its page name
`translation tables are shown in Figure 3.22 [CHAN88]. The IBM 801
`generates a 32-bit effective address that is expanded to a 40-bit virtual
`address using a map that is similar to that adopted by the RS/6000
`shown in Figure 3.5. Page name translation is via a hash anchor table
`and a page frame table stored in real main memory. Unfortunately the
`published literature does not give the sizes of the three fields of the
`virtual address.
`The IBM 801 design combined the page frame address and link into
`one field of the page frame table. This field is noted in Figure 3.22 as
`the PFA-LNK field and is large enough to address any page frame in
`real memory (at the page level) or to address the next entry in the page
`frame table [CHAN88]. The operation of this combined field is described
`below.
`A page name extended with a segment ID is hashed for an index
`into the hash anchor table, which then provides an index into the page
`frame table. If there is not a match on the page name, the link field
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 163
`
`

`

`3.3 Virtual Memory Organizations
`
`14 7
`
`indexes into another entry. If there is a match, the link field is the page
`frame address in real memory and is concatenated with the displacement
`field from the virtual address. In other words, the link field is multiplied
`by 2 to the power of the displacement bits (left shifted the number of
`bits of the displacement). When there is not a match, the link field has
`its MSBs set to zero and the resulting value becomes the index into the
`page frame table. This process assumes that the page tables are allocated
`in the low address page frames of real memory.
`Both the hash anchor table and the page frame table are stored in
`real memory. Therefore, a translation requires a minimum of two mem(cid:173)
`ory accesses to translate a page name. The size of the hash anchor table
`and page frame table are set when the system is g~nerated depending
`upon the amount of installed real memory in the system. The hash
`anchor table can be set to be either equal to or twice the size of the page
`frame table.
`IBM PC RT. The IBM PC RT also stores both the hash anchor table
`and the page frame table in memory [SIMP86, HEST86], as shown in
`Figure 3.23. The 32-bit effective address is expanded to a 40-bit virtual
`address by means of a 16-entry segment register. The page size can be
`set at either 2 Kbytes or 4 Kbytes, leaving either 28 or 29 bits that are
`hashed by an XOR operation for an index into the hash anchor table.
`Experience with the IBM RT PC [CHAN88] shows that 2.5 storage
`accesses, or 1.5 probes to the page frame table, are required per page
`name translation. From this result we would assume that the hash
`anchor table has the same number of entries as the page frame table(cid:173)
`a conclusion based on the Johnson [JOHN61] model. As with the IBM
`801, setting the size of these tables is done when the system is generated.
`
`40 Bit Virtual Address
`28 or29 Bits
`11 or 12 Bits
`
`Displacement !
`
`Page Name
`
`Index
`
`Page Frame Table
`
`Page Name
`
`Real
`Memory
`Address
`
`FtGURE 3.23
`
`. _ . . ..... __ . __ . . ... J!I. M~!1)9!'Y . .. ... . ..... .. . . .. ... .. . -. •• . .•• -•••. --
`IBM PC RT page name translation.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 164
`
`

`

`148
`
`Virtual Memory
`
`24 Bits
`
`16 Bits
`
`! Seg. ID. !Transaction ID. j Displacement I 62 Bil Virtual Addresa
`
`12 Bits
`
`Hash An
`Pa
`
`ex
`
`Page Frame Table
`
`Index
`Hash
`Generator r+ l Bits j
`
`r=lg 2 page frames
`
`lf-1
`
`40
`
`..__ ____ __.___._ ___ _,,
`
`ss
`
`20
`
`20 Bits
`
`FIGURE 3.24
`
`IBM RS/6000 page name translation.
`
`IBM RS/6000. The IBM RS/6000 continues the approach started
`with the IBM Future System development [IBM90]. Because the
`RS/6000 is a recently introduced computer, its virtual memory system
`is described in more detail than the other IBM systems described above.
`The RS/6000 can be viewed as a paged-segmented system with the
`segments defined by the address map of Figure 3.5; the balance of the
`system is pure paged. A block diagram of the RS/6000 page name
`translation is shown in Figure 3.24.
`The 52-bit virtual address is divided into three fields: a 24-bit seg(cid:173)
`ment ID, a 16-bit transaction page ID, and a 12-bit byte displacement
`[IBM90]. The hash generator XORs the 24-bit SID and the 16-bit TID
`extended with zeros to 24 bits. The low-order r + l bits of the result
`index the hash anchor table.
`The size of the hash anchor table is set to be twice the number of
`real pages installed on the system, while the number of entries in the
`page frame table is set equal to the number of pages in installed real
`memory, which can reach a maximum of 220 pages. These table size
`selections are made by the operating system.
`Each entry in the page frame table consists of 16 bytes (4 words). A
`20-bit link field (PFA-LNK) links to the next entry if the comparison
`fails. If the comparison succeeds, the link value of the entry point to the
`succeeding comparison is the page frame address and is concatenated
`with the 12-bit displacement, providing a 32-bit real memory address.
`In other words, on a hit the link field is multiplied by 2 12
`, while on a
`miss the link is used as the address into the page frame table in the low
`addresses of real memory.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2142, p. 165
`
`

`

`3.3 Virtual Memory Organizations
`
`149
`
`S/38
`
`801
`
`PC-RT
`
`RS/6OOO
`
`Names
`
`Level 1
`
`Level 2
`
`Sizes
`
`Level 1
`
`Hash
`Index
`Table
`Page
`Directory
`Table
`128
`
`Hash
`Hash
`Table Anchor
`Table
`Inverted
`Page
`Table
`r
`
`Page
`Table
`
`Level 2
`
`64
`
`r
`
`Hash
`Anchor
`Table
`Page
`Frame
`Table
`2r+l Up
`to 221
`2r up to
`220
`up to 220
`
`4 Kbytes
`
`52 bits
`232 bytes
`
`No. of Real Memory Page
`Frames
`Page Size
`
`512 bytes
`
`2 Kor 4
`Kbytes
`40 bits
`222 bytes
`Max Real Memory Size
`Note. r = lg2 (Number of page frames in real memory).
`
`Virtual Address
`
`48 bits
`
`TABLE 3.3
`
`IBM hash accessed inverted page tables.
`
`A linked list presents the danger of an infinite translation loop due
`to a programming error. That is, the links can create a circular list and,
`if there is no hit on tag comparisons, the translation can run forever.
`To prevent this from happening, a maximum of 127 probes are permitted
`before a search is declared a failure. The number of probes for the other
`systems described above is not known.
`The IBM systems have evolved over a period of time. In order to
`illustrate this evolution, Table 3.3 contains a summary of the relevant
`parameters of the IBM systems discussed above.
`As noted previously, the· hash anchor tables and page frame tables
`are too large to be stored in fast hardware registers. Consequently, it
`is necessary to enhance the performance of these systems by using a
`translation lookaside buffer [HOUD81, CHAN88, OEHL90]. After a page
`miss, the requested page is loaded into the real memory. In addition, the
`TLB, the hash anchor table, and page frame tables are updated. A
`subsequent reference to this page will find the page name translation
`information in