P&H 7.22
Address references:
1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17 m m m h m m h m m h m m h h h mFinal contents of cache:
index address 0 40,41,42,43 1 8,9,10,11 2 16,17,18,19 3 4,5,6,7
P&H 7.32
What is the size of the page table?
16 Kb page = 2^14 bytes which means 14 bits for the offset in the address. Which means that if we have a 36 bit physical address and 40 bit VPN, we will have a translation from a 26 bit VPN to a 22 bit PPN. This means that the page table must have 2^26 rows in it and that each row will have 26 bits (22 from the PPN and 4 for the valid, protection, dirty, and use bits). So then that means that the size of the table is 2^26 rows * 26 bits per row = 218,103,808 bytes (208 MBytes).
P&H 7.35
multilevel page tables
PTE = page table entry
VPN = virtual page number
PFN = physical frame number
VA = virtual address
PA = physical address
PT = page table
1) 4KB pages => 2^12 B per page
=> 12-bit offset to index each byte in a page
2) # bits in VPN + # bits in offset = # bits in VA
? + 12 = 32
=> 20-bit VPN => 2^20 = 1M PTEs total in all 2nd level PTs
3) Each 2nd level PT is 1 page in size => each 2nd level PT is 4KB
4) #PTEs in each L2 PT x size of one PTE = size of each L2 PT
? 4B 4KB
=> 1K PTEs per L2 PT
5) 1M PTEs total, 1K PTEs per L2 PT => 1K L2 PTs total
6) L1 PT has a physical address for each L2 PT. 1K L2 PTs => 1K physical
addresses in L1 PT. So, how many bits are in a PA?
7) But wait, we don't need to store 1K PAs in the L1 PT. These are PAs of the
L2 PTs. Each L2 PT is a page, and should be page-aligned. Thus, lowest 12
bits are always zero (remember beq, bne, j?) => only need to store highest
bits in L1 PT. These highest bits are just the PFN part of the PA.
=> 1K PFNs in the L1 PT. So, how many bits are in a PFN?
8) Before that, we can verify we're on the right track b/c 1K PTEs per L2 PT
=> 2^10 PTEs per L2 PT => 10-bit page table offset
#bits in page table # + #bits in page table offset = #bits in VPN
? 10 20
=> 10 bits in page table # => 2^10 = 1K elements in L1 PT, which is same
as above
9) Just to let you know where we are,
(#bits in a PFN + extra bits) x #elements in L1 PT = L1 PT size (in bits)
( #bits in a PTE ) x 1K = L1 PT size (in bits)
#bytes in a PTE x 1K = L1 PT size (in bytes)
4B x 1K = 4KB.
Nothing like this will ever show up on an exam I grade--"The Network Question"
was horror enough!
+----------------------+------------------------------+---------------------+
| 10-bit page table # | 10-bit page table offset | 12 bit page offset |
+----------------------+------------------------------+---------------------+
| __________________________ | |
| | First level page table | | |
| |________________________| | |
| | | | |
| |________________________| | ______________________ |
`--->| address of page table |-+->| 2nd level page tbl | |
|________________________| | |____________________| |
| | | | | |
|________________________| | |____________________| |
| | | |
| |____________________| |
`->| Physical page # | |
|____________________| |
| | | |
|_________|__________| |
| | | |
|_________|__________| |
V V
+-----------------------------+---------------------+
| ?-bit physical page number | 12 bit page offset |
+-----------------------------+---------------------+
If you got the wrong answer, but have correct reasoning, you can get up to full credit
on this problem. If you got the right answer, but have incorrect reasoning, you won't
get full credit.
