Considering only the virtual memory, and assuming no hits in the TLB,
how many memory accesses does it take to write four bytes starting
at virtual address 0x123fffff
on an Intel machine using only
small (4K) pages?
Following this question will be the contents of the PDBR, some of memory, some of cache, and the small page data TLB for an Intel Pentium Pro. All the numbers are in hexadecimal.
The L1 data cache on this machine was an 8KB, 4-way set-associative cache with a 32 byte line size.
Assume a program running in User mode attempts to write to each of the following virtual addresses. In each case, what happens? You may get page faults at either the directory entry or page table entry level, cache hits, cache misses, TLB hits, TLB misses.... However, you should never have reason to attempt a lookup in one of the tables and simply not find a table entry.
6141fac4
5eef358c
4ff2dfbc
6cc8e224
2153b858
4bf6af30
52b8525c
7559989c
TLB tag:Since the TLB has 2^3=8 sets and we need 12 bits to specify the address
of a page table, every tag in TLB consists of 32-(3+12) = 17 bits.Cache tag:a). Since the line size (the size of data in each block) is 32 bytes, so the
byte offset in a virtual address is 5 bits.
b). Since the cache is 4-way associative, so the total data within one set
is 4*32=2^7 bytes.
c). Since the cache size is 8KB, so the total number of sets
is 8KB / 2^7 = 2^13 / 2^7 = 2^6 and the set index takes 6 bits.
d). Therefore the higher 32-6-5=32-11=21 bits of a virtual address
is used as a tag to look up the cache.
e). The number of associativity does not directly take bits in the virtual
address. Given the cache size, more associativity, less set numbers.
Thus the number of associativity is indirectly reflected in virtual
address through the set index bits.
1. 6141fac4
Virtual address |
6 1 4 1 f a c 4 |
||||||||
binary format |
0110 0001 0100 0001 1111 1010 1100 0100 |
||||||||
TLB look-up |
tag: 0110 0001 0100 0001 1 Index: 111(binary) 0 1100 0010 1000 0011 111(binary) 0 c 2 8 3 7 (hex) TLB miss |
||||||||
break down |
page table #:1 8 5 |
page #: 0 1 f |
offset: ac4 |
||||||
VM steps
|
directory entry: |
can not continue until the directory and page table are updated |
|||||||
page table info: mem[27060614]=02397006 decode: |
Virtual address |
5 e e f 3 5 8 c |
||||||||
binary format |
0101 1110 1110 1111 0011 0101 1000 1100 |
||||||||
TLB look-up |
tag: 0101 1110 1110 1111 0 Index: 011 (binary) 0 1011 1101 1101 1110 011 (binary) 0 b d d e 3 (hex) TLB miss |
||||||||
break down |
page table #: 1 7 b |
page #: 2 f 3 |
offset: 58c |
||||||
VM steps
|
directory entry: |
page table entry: |
can not continue until the page fault is resolved |
||||||
page table info: |
page info: |
Virtual address |
4 f f 2 d f b c |
||||||||
binary format |
0100 1111 1111 0010 1101 1111 1011 1100 |
||||||||
TLB look-up |
tag: 0100 1111 1111 0010 1 Index: 101 (binary) 0 1001 1111 1110 0101 101 (binary) 0 9 f e 5 5 (hex) TLB miss |
||||||||
break down |
page table #: 1 3 f |
page #: 3 2 d |
offset: fbc |
||||||
VM steps
|
directory entry: |
No way to continue. Protection failure. |
|||||||
page table info: |
Virtual address |
6 c c 8 e 2 2 4 |
||||||||
binary format |
0110 1100 1100 1000 1110 0010 0010 0100 |
||||||||
TLB look-up |
tag: 0110 1100 1100 1000 1 Index: 110 (binary) 0 1101 1001 1001 0001 110 (binary) 0 d 9 9 1 6 (hex) |
||||||||
break down |
page table #: 1 b 3 |
page #: 0 8 e |
offset: 224 |
||||||
VM steps
|
physical addr: 3a951000 + 224 = 3a951224 |
||||||||
page table info: |
|
cache look-up: 3 a 9 5 1 2 2 4 cache hit |
Virtual address |
2 1 5 3 b 8 5 8 |
||||||||
binary format |
0010 0001 0101 0011 1011 1000 0101 1000 |
||||||||
TLB look-up |
tag: 0010 0001 0101 0011 1 Index: 011 (binary) 0 0100 0010 1010 0111 011 (binary) 0 4 2 a 7 3 (hex) TLB miss |
||||||||
break down |
page table #: 0 8 5 |
page #: 1 3 b |
offset: 858 |
||||||
VM steps
|
directory entry: |
page table entry: |
physical addr: |
||||||
page table info: |
page info: |
cache look-up: 5 b d d 1 8 5 8 |
6. 4bf6af30
Virtual address |
4 b f 6 a f 3 0 |
||||||||
binary format |
0100 1011 1111 0110 1010 1111 0011 0000 |
||||||||
TLB look-up |
tag: 0100 1011 1111 0110 1 Index: 010 (binary) 0 1001 0111 1110 1101 010 (binary) 0 9 7 e d 2 (hex) TLB hit: entry=09258027 |
||||||||
break down |
page table #: 1 2 f |
page #: 3 6 a |
offset: f30 |
||||||
VM steps
|
|
physical addr: |
|||||||
page table info: |
cache look-up: 0 9 2 5 8 f 3 0 |
Virtual address |
5 2 b 8 5 2 5 c |
||||||||
binary format |
0101 0010 1011 1000 0101 0010 0101 1100 |
||||||||
TLB look-up |
tag: 0101 0010 1011 1000 0 Index: 101 (binary) 0 1010 0101 0111 0000 101 (binary) 0 a 5 7 0 5 (hex) |
||||||||
break down |
page table #: 1 4 a |
page #: 3 8 5 |
offset: 25c |
||||||
VM steps
|
|
physical addr: |
|||||||
page table info: |
cache look-up: 4 6 9 8 e 2 5 c |
Virtual address |
7 5 5 9 9 8 9 c |
||||||||
binary format |
0111 0101 0101 1001 1001 1000 1001 1100 |
||||||||
TLB look-up |
tag: 0111 0101 0101 1001 1 Index: 001 (binary) 0 1110 1010 1011 0011 001 (binary) 0 e a b 3 1 (hex) TLB hit: entry=7bd5c025 |
||||||||
break down |
page table #: 1 d 5 |
page #: 1 9 9 |
offset: 89c |
||||||
VM steps
|
|
No way to continue. Protection failure. | |||||||
page table info: |