Review of Memory Hierarchy - Computer Architecture: A Quantitative Approach - page 595

ing both traditional pages tables and inverted page tables, leaving the choice of mechanism to
the operating system programmer.
To reduce address translation time, computers use a cache dedicated to these address trans-
lations, called a translation lookaside buffer, , or simply translation buffer, , described in more detail
shortly.
Q3: Which Block Should Be Replaced on a Virtual Memory Miss?
As mentioned earlier, the overriding operating system guideline is minimizing page faults.
Consistent with this guideline, almost all operating systems try to replace the least recently
used (LRU) block because if the past predicts the future, that is the one less likely to be needed.
To help the operating system estimate LRU, many processors provide a use bit or reference
bit , which is logically set whenever a page is accessed. (To reduce work, it is actually set only
on a translation buffer miss, which is described shortly.) The operating system periodically
clears the use bits and later records them so it can determine which pages were touched dur-
ing a particular time period. By keeping track in this way, the operating system can select a
page that is among the least recently referenced.
Q4: What Happens on a Write?
The level below main memory contains rotating magnetic disks that take millions of clock
cycles to access. Because of the great discrepancy in access time, no one has yet built a virtual
memory operating system that writes through main memory to disk on every store by the pro-
cessor. (This remark should not be interpreted as an opportunity to become famous by being
the first to build one!) Thus, the write strategy is always write-back.
Since the cost of an unnecessary access to the next-lower level is so high, virtual memory
systems usually include a dirty bit. It allows blocks to be writen to disk only if they have been
altered since being read from the disk.
Techniques For Fast Address Translation
Page tables are usually so large that they are stored in main memory and are sometimes paged
themselves. Paging means that every memory access logically takes at least twice as long, with
one memory access to obtain the physical address and a second access to get the data. As men-
tioned in Chapter 2 , we use locality to avoid the extra memory access. By keeping address
translations in a special cache, a memory access rarely requires a second access to translate the
data. This special address translation cache is referred to as a translation look aside buffer (TLB),
also called a translation buffer, (TB).
A TLB entry is like a cache entry where the tag holds portions of the virtual address and the
data portion holds a physical page frame number, protection field, valid bit, and usually a use
bit and dirty bit. To change the physical page frame number or protection of an entry in the
page table, the operating system must make sure the old entry is not in the TLB; otherwise, the
system won't behave properly. Note that this dirty bit means the corresponding page is dirty,
not that the address translation in the TLB is dirty nor that a particular block in the data cache
is dirty. The operating system resets these bits by changing the value in the page table and
then invalidates the corresponding TLB entry. When the entry is reloaded from the page table,
the TLB gets an accurate copy of the bits.
Figure B.24 shows the Opteron data TLB organization, with each step of the translation
labeled. This TLB uses fully associative placement; thus, the translation begins (steps 1 and 2)
by sending the virtual address to all tags. Of course, the tag must be marked valid to allow a