Consider a virtual memory system that uses a single-level page map
to translate virtual addresses into physical addresses. Each of the
questions below asks you to consider what happens when one of the
design parameters of the original system is changed.
If the physical memory size (in bytes) is doubled, how does the
number of bits in each entry of the page table change?
increases by 1 bit. Assuming the page size remains the same, there are
now twice as many physical pages, so the physical page number needs to
expand by 1 bit.
If the physical memory size (in bytes) is doubled, how does the
number of entries in the page map change?
no change. The number of entries in the page table is determined by
the size of the virtual address and the size of a page -- it's not
affected by the size of physical memory.
If the virtual memory size (in bytes) is doubled, how does the
number of bits in each entry of the page table change?
no change. The number of bits in a page table entry is determined
by the number of control bits (usually 2: dirty and resident) and
the number of physical pages -- the size of each entry is not affected
by the size of virtual memory.
If the virtual memory size (in bytes) is doubled, how does the
number of entries in the page map change?
the number of entries doubles. Assuming the page size remains the same,
there are now twice as many virtual pages and so there needs to be twice
as many entries in the page map.
If the page size (in bytes) is doubled, how does the number of
bits in each entry of the page table change?
each entry is one bit smaller. Doubling the page size while maintaining
the size of physical memory means there are half as many physical pages
as before. So the size of the physical page number field decreases by
one bit.
If the page size (in bytes) is doubled, how does the number of
entries in the page map change?
there are half as many entries. Doubling the page size while maintaining
the size of virtual memory means there are half as many virtual pages
as before. So the number of page table entries is also cut in half.
The following table shows the first 8 entries in the page map.
Recall that the valid bit is 1 if the page is resident in physical
memory and 0 if the page is on disk or hasn't been allocated.
Virtual page | Valid bit | Physical page |
0 | 0 | 7 |
1 | 1 | 9 |
2 | 0 | 3 |
3 | 1 | 2 |
4 | 1 | 5 |
5 | 0 | 5 |
6 | 0 | 4 |
7 | 1 | 1 |
If there are 1024 (210) bytes per page, what is the
physical address corresponding to the decimal virtual address 3956?
3956 = 0xF74. So the virtual page number is 3 with a page offset
of 0x374. Looking up page table entry for virtual page 3, we see
that the page is resident in memory (valid bit = 1) and lives in
physical page 2. So the corresponding physical address is (2<<10)+0x374
= 0xB74 = 2932.
A particular 32-bit microprocessor includes support for paged virtual
memory addressing with 212 byte pages. The mapping of virtual to
physical addresses requires two translation steps:
- The most significant 10 bits of the virtual address (the Dir
field) are multiplied by 4 and appended to the 20 most significant
bits of the dirbase (directory base) register to get the address in
main memory of a page directory entry. Each entry in the page
directory is a 32-bit record composed of a 20-bit PTBL field and
various control bits (Present, Dirty, Read-only, etc.).
- The bits of the Page field (virtual address bits 21 to 12) are
multiplied by 4 and appended to the PTBL field to form the page-table
address. This page table address references a 32-bit page table entry.
Each page table entry is composed of a 20-bit physical page number
(PPN) and a series of control bits.
All page-table entries and the page directory are stored in main
memory. The results of these translations are cached in a 4-way
set-associative translation look-aside buffer (TLB) with a total of 64
entries, and a LRU replacement strategy is used on TLB misses.
Given a computer system with 227 bytes of physical memory that
uses the virtual-to-physical address translation scheme described, how
many pages of physical memory are there?
215 = 227/212 = the size of physical memory
divided by the size of each page.
How many memory pages does the Page Directory occupy?
We are told that the Page Directory index is 10 bits, implying 210
= 1024 entries. Each entry occupies 4 bytes, so the total size of the of
the Page Directory is 4*210 = 212 bytes, or exactly
one page.
What is the approximate maximum size for a process's working
set that still achieves a 100% TLB hit rate?
The TLB has 64 entries, so to achieve 100% hit rate in the TLB we can access
only 64 different pages as part of our working set. 64 pages = 64*212
= 218 bytes.
Which virtual address bits would most likely be used to select
which set to access in the TLB cache?
We would like adjacent virtual pages to be able to mapped by the TLB,
so we'd like them to occupy different sets in the cache. This is achieved
by using the low-order 4 bits of the virtual page number as the TLB index,
i.e., bits 12 through 15 of the address. Remember that the TLB is
4-way associative, so each subcache has 64/4 = 16 entries.
How large must the tag field of the TLB be?
The tag field should contain all the bits of the virtual page number
not used to form the index, i.e., bits 16 through 31, a total of 16 bits.
A control bit, C, in each page table entry determines if memory
references to that page are cacheable. In order to support this
feature, which of the following statements concerning the interaction
between virtual-to-physical address translations and caching must be
true?
- The cache tags must contain physical addresses
- Each memory access requires a virtual-address translation to take
place in parallel with the cache access
- The status of the cacheable bit, C, needs only to be considered on a
cache miss
- Page table entries with their dirty bit set should clear their cacheable bit
- All of the above
C. We only need to worry if a page is cacheable if we're considering
bringing some of its entries into the cache, and we only do this if
the access can't be satisfied from current contents of the cache.
Consider two possible page-replacement strategies: LRU (the least
recently used page is replaced) and FIFO (the page that has been in
the memory longest is replaced). The merit of a page-replacement
strategy is judged by its hit ratio.
Assume that, after space has been reserved for the page table, the
interrupt service routines, and the operating-system kernel, there is
only sufficient room left in the main memory for four
user-program pages. Assume also that initially virtual pages 1, 2, 3,
and 4 of the user program are brought into physical memory in that
order.
For each of the two strategies, what pages will be in the memory
at the end of the following sequence of virtual page accesses? Read
the sequence from left to right: (6, 3, 2, 8, 4).
LRU:
start: 1 2 3 4
access 6: replace 1 => 2 3 4 6
access 3: reorder list => 2 4 6 3
access 2: reorder list => 4 6 3 2
access 8: replace 4 => 6 3 2 8
access 4: replace 6 => 3 2 8 4
FIFO:
start: 1 2 3 4
access 6: replace 1 =gt; 2 3 4 6
access 3: no change =gt; 2 3 4 6
access 2: no change =gt; 2 3 4 6
access 8: replace 2 =gt; 3 4 6 8
access 4: no change => 3 4 6 8
Which (if either) replacement strategy will work best when the
machine accesses pages in the following (stack) order: (3, 4, 5, 6,
7, 6, 5, 4, 3, 4, 5, 6, 7, 6, ...)?
LRU misses on pages 3 & 7 => 2/8 miss rate.
FIFO doesn't work well on stack accesses => 5/8 miss rate.
Which (if either) replacement strategy will work best when the
machine accesses pages in the following (repeated sequence) order: (3,
4, 5, 6, 7, 3, 4, 5, 6, 7, ...).
Both strategies have a 100% miss rate in the steady state.
Which (if either) replacement strategy will work best when the
machine accesses pages in a randomly selected order, such as (3, 4,
2, 8, 7, 2, 5, 6, 3, 4, 8, ...).
Neither FIFO nor LRU is guaranteed to be the better strategy
in dealing with random accesses since there is no locality to
the reference stream.
A paged memory with a one-level page table has the following
parameters: The pages are 2P bytes long; virtual addresses
are V bits long, organized as follows:
virtual page number | offset in page |
The page-table starts at physical address PTBL; and each page-table
entry is a 4-byte longword, so that, given a virtual address, the
relevant page-table entry can be found at PTBL + (page number)*4.
Answer the following in terms of the parameters P and V:
How many bits long is the "offset in page" field?
It takes log2(2P) = P address bits to select a single byte
from a page with 2P bytes.
How many bits long is the "virtual page number" field?
Since there a P bits in the offset field, the remaining V-P bits are
part of the virtual page number.
How many entries does the page table have, and what is the
highest address occupied by a page-table entry?
Since the virtual page number field has V-P bits, there are 2V-P
virtual pages and each has its own entry in the page table. Each entry
is 4 bytes longs, so the highest address occupied by a page table entry
is PTBL + 4*(2(V-P)-1).
How many pages long is the page table?
There are 2P/4 page table entries per page and 2V-P
pages, so the page table is 2V-P/2P-2 = 2V-2P+2
pages long.
What is the smallest value of P such that the
page table fits into one page?
Using the formula from the previous question, to make the page table fit in
one page, we want V-2P+2 = 0. Solving for P we get
P = V/2 + 1.
What relationships, if any, must hold between P, V, and the
size of physical memory?
Suppose physical memory contained 2M bytes. Then
- The physical page number must fit in 30 bits since we reserve 2 bits of the
32-bits page table entry for the dirty and resident control bits. So
30 >= M - P.
- It useful to have room in memory for at least one page other than those
occupied by the page map. So M > V-P+2.
If virtual addresses are V bits long, physical addresses are
A bits long, the page size is 2P bytes, and a one-level page
table is used, give an expression for the size of the page table.
There are 2V-P pages and the page table entry for each page
contains a physical page number (A-P bits), a dirty bit (1 bit) and a
resident bit (1 bit). So the page table occupies 2V-P(A-P+2) bits.
Adverbs Unlimited has recently added a new product, the VIRTUALLY
to the product line introduced in an earlier tutorial problem. The
VIRTUALLY has a 210-byte, two-way set-associative cache,
220 bytes of physical memory, 16-bit virtual addresses, and
a 26-entry page map. The VIRTUALLY will be used to support
multiuser time-sharing. The page map holds the address translation for
a single (current) process and must be reloaded (by the kernel) at
each process switch. The cache is located between the page map and
main memory.
What is the page size?
page size in bytes = size of virtual address divided by number of
entries in the page map = 216/26 = 210
bytes per page.
Which virtual address lines are used to form the index to the
page map?
The virtual page number is used as the index to the page map. The
virtual page number includes all virtual address bits that aren't part
of the page offset. Since there 210 bytes per page, the
page offset requires 10 bits, i.e., address bits 0 through 9. The
remaining six bits (bits 10 through 15) form the virtual page number.
Can the cache and page-map be read simultaneously?
Explain in a single sentence.
Yes since the virtual page number (bits 10 through 15) doesn't overlap
with the cache index/block index (bits 0 through 8 remembering that the
cache is 2-way set associative).
Under what circumstances, if any, must the cache be invalidated
(that is, its entries marked as invalid)?
Since the cache is located after the page map, it caches physical
addresses. So it must be invalidated when there is a page replacement
due to a page fault, since this operation changes the contents of physical
memory.
Program A consists of 1000 consecutive ADD instructions, while
program B consists of a loop that executes a single ADD instruction
1000 times. You run both programs on a certain machine and find that
program B consistently executes faster. Give two plausible
explanations.
Explanation #1: one would expect the loop to achieve a higher hit
rate in the cache since it involves many fewer instruction words.
Explanation #2: the loop, occupying many fewer instruction words,
should all fit onto a single page. The 1000 instructions might
span several pages and hence their execution may involve some
page faults.
If a TLB is implemented as a set-associative cache, how would you
recommend determining the TLB slots examined when mapping the
virtual address VA[31:0]? Why?
We should use the low-order bits of the virtual page number as
the index into the TLB so that adjacent pages can be mapped by
the TLB without collisions.