Hardware Reference
In-Depth Information
Four Memory Hierarchy Questions Revisited
We are now ready to answer the four memory hierarchy questions for virtual memory.
Q1: Where Can a Block Be Placed in Main Memory?
The miss penalty for virtual memory involves access to a rotating magnetic storage device
and is therefore quite high. Given the choice of lower miss rates or a simpler placement al-
gorithm, operating systems designers normally pick lower miss rates because of the exorbitant
miss penalty. Thus, operating systems allow blocks to be placed anywhere in main memory.
According to the terminology in
Figure B.2
on page B-8, this strategy would be labeled fully
associative.
Q2: How Is a Block Found If It Is in Main Memory?
Both paging and segmentation rely on a data structure that is indexed by the page or segment
number. This data structure contains the physical address of the block. For segmentation, the
offset is added to the segment's physical address to obtain the final physical address. For pa-
ging, the offset is simply concatenated to this physical page address (see
Figure B.23
)
.
FIGURE B.23
The mapping of a virtual address to a physical address via a page table
.
This data structure, containing the physical page addresses, usually takes the form of a
page
table
. Indexed by the virtual page number, the size of the table is the number of pages in the
virtual address space. Given a 32-bit virtual address, 4 KB pages, and 4 bytes per page table
entry (PTE), the size of the page table would be (2
32
/2
12
) × 2
2
= 2
22
or 4 MB.
To reduce the size of this data structure, some computers apply a hashing function to the
virtual address. The hash allows the data structure to be the length of the number of
physical
pages in main memory. This number could be much smaller than the number of virtual pages.
Such a structure is called an
inverted page table
. Using the previous example, a 512 MB physical
memory would only need 1 MB (8 × 512 MB/4 KB) for an inverted page table; the extra 4 bytes
per page table entry are for the virtual address. The HP/Intel IA-64 covers both bases by offer-
Search WWH ::
Custom Search