2.) 15 points] (Exercise 5.11) Assume 4KiB pages, a 4-entry full associative TLB
ID: 3709499 • Letter: 2
Question
2.) 15 points] (Exercise 5.11) Assume 4KiB pages, a 4-entry full associative TLB and true LRU replacement. The LRU status at the beginning is shown in TLB table. O represents the Least Recently Used and 3 being the Most Recently Used. Page table contains 16 entries shown in Page Table. If pages must be brought in from disk, increment the next largest page number, i.e., when the page table is accessed, if that particular page is on disk, the page number would be 18 since the largest page number in the page table at the beginning is 17. Assume physical memory is large enough. TLB Tag Physical Page Number 8 Valid LRU 3 4 0 10 2 0 7Explanation / Answer
a) Size of page = 4KB = 212 B
Therefore number of bits in the offset of virtual address = 12 bits
Number of entries in the page table = 16 = 24
Therefore number of bits in the virtual address in the index field to index page number = 4 bits
Therefore total size of virtual address = 12 + 4 = 16 bits
b) Now the MSB 4 bits in the virtual address will be used as TAG in the TLB.
First address:
39401 = 1001 | 100111101001
TAG = 9
Therefore TLB Hit.
second address:
53332 = 1101 | 000001010100
TAG = 13
Therefore TLB Miss.
But it is page table hit .
Therefore as 0 is least recently used in the TLB it will be overwritten by (1,13,17,3)
and the LRU value of the first entry will become 2, second entry will become 0 and third entry will become 1.
third address:
4090 = 0000 | 111111111010
TAG = 0
Therefore TLB Hit.
So, LRU of 3rd entry will be 3 , fourth entry will be 2, first entry will be 1 and second entry will be 0.
fourth address:
15832 = 0011 | 110111011000
TAG = 3
Therefore TLB Miss,Similarly page table miss also.
Therefore this page will be brough from the disk to the corresponding frame in main memory.
The page table will be updated with a entry in the fourth row with valid bit 1 and physical page 18.
In the TLB also the second entry will be overwritten( as its LRU is 0 now) and will be updated with the entry (1,3,18,3)
So, LRU of 3rd entry will be 2 , fourth entry will be 1, first entry will be 0 and second entry will be 3.
fifth address:
25678 = 0110 | 010001001110
TAG = 6
Therefore TLB Miss,Similarly page table miss also.
Therefore this page will be brought from the disk to the corresponding frame in main memory.
The page table will be updated with a entry in the seventh row with valid bit 1 and physical page 19.
In the TLB also the first entry will be overwritten( as its LRU is 0 now) and will be updated with the entry (1,6,19,3)
So, LRU of 3rd entry will be 1 , fourth entry will be 0, first entry will be 3 and second entry will be 2.
sixth address:
7345 = 0001 | 110010110001
Therefore TLB Miss,Similarly page table miss also.
Therefore this page will be brought from the disk to the corresponding frame in main memory.
The page table will be updated with a entry in the second row with valid bit 1 and physical page 20.
In the TLB also the fourth entry will be overwritten( as its LRU is 0 now) and will be updated with the entry (1,1,20,3)
So, LRU of 3rd entry will be 0 , fourth entry will be 3, first entry will be 2 and second entry will be 1.
sixth address:
45155 = 1011 | 000001100011
TAG = 11
Therefore TLB Miss,Similarly page table miss also.
Therefore this page will be brought from the disk to the corresponding frame in main memory.
The page table will be updated with a entry in the twelfth row with valid bit 1 and physical page 21.
In the TLB also the third entry will be overwritten( as its LRU is 0 now) and will be updated with the entry (1,11,21,3)
So, LRU of 3rd entry will be 3 , fourth entry will be 2, first entry will be 1 and second entry will be 0.
c) TLB:
VALID TAG PHYSICAL PAGE NUMBER LRU
1 6 19 1
1 3 18 0
1 11 21 3
1 1 20 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.