Outline
- Homework on virtual memory
We discussed the solutions to the homework #6.
1. In a multi-level page table system, a virtual address is divided into
multiple parts -- a,b,c,d -- where d represents offset bits and the other
parts are used to index into page tables.
knowing the size of offset gives the size of the page (or vice versa).
pagesize = 2^d
there is a single top-level page table. the size of that page table is
determined by the part 'a' of the virtual address.
total number of page tables at 1st-level = 1
number of entries in the top-level page table = 2^a
each entry in the top-level page table stores an address of a page table
in the next level (2nd-level page table).
size of the top-level page table determines the total number of page tables
in the 2nd-level. the size of a page table at the 2nd level is determined
by the part 'b' of the virtual address space.
total number of page tables at the 2nd-level = 2^a
number of entries in the 2nd-level page table = 2^b
total number of page tables at the 3rd level is determined by the size of
the page table at the 2nd level and the total number of page tables at the
2nd level. the size of a page table at the 3rd level is determined by the
part 'c' of the virtual address space.
total number of page tables at the 3rd level = 2^a * 2^b = 2^(a+b)
number of entries in the 3rd-level page table = 2^c
Now, you were given a range of the valid virtual addresses (0 - 2^18).
You can calculate the number of valid pages in the address space. Given
that number you know that you need that many entries in the 3rd level
page tables to reference all these pages in the valid address space.
Number of valid PTEs at the 3rd level = number of valid pages in the
address space
number of valid page tables at the 3rd level = number of valid PTEs at
the 3rd level / size of a page table at the 3rd level
Number of valid page tables at the 3rd level will tell you how many valid
PTEs are at the 2nd level. Then, you can calculate the number of valid
page tables by dividing the valid PTEs at the 2nd level by the size of a
page table at the 2nd level.
Number of valid page tables at the 2nd level will tell you how many valid
PTEs are at the 1st(top) level.
2. In this problem we asked you to calculate specific values for offsets
into page tables for a 3-level page table system and a specific address.
In general to solve this kind of problem, write out a given address in
a binary form (eg., 0110 0000 1010 1001 1011 1011 0000 0000)
Then take each part of the virtual address (eg., say the slipts were 10bits,
8bits, 6bits, 8bits) and translate the bits back into a decimal or hex number
(eg., calculate what 01 1000 0010 is (top 10bits of the example)). That
will give you a value of the offset in the corresponding page table for a
level and the last part will give you the offset.
3. We discussed how to estimate effective instruction time.
4. We demonstrated how a the program structure can effect system performance
5. You learned about adding big numbers.. ;)