1) virtual memory uses a page table to track the mapping of virtual addresses to
ID: 3815916 • Letter: 1
Question
1)virtual memory uses a page table to track the mapping of virtual addresses to physical addresses. This exercise shows how this table must be updated as addresses are accessed. The following data constitutes a stream of virtual addresses as seen on a system. Assume 4 KiB pages, a 4-entry fully associative TLB, and true LRU replacement. The LRU status at the beginning of the address sequence is show in the TLB table. 0 being the Least Recently Used and 3 being the Most Recently Used. 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 13 since the largest page number in the page table at the beginning is 12.
4669, 2227, 13916, 34587, 48870, 12608, 49225
TLB
Valid
Tag
Physical Page Number
LRU
1
11
12
1
1
7
4
2
1
3
6
3
0
4
9
0
Page Table
Valid
Physical Page or in Disk
1
5
0
Disk
0
Disk
1
6
1
9
1
11
0
Disk
1
4
0
Disk
0
Disk
1
3
1
12
a)Given the address stream shown, and the initial TLB and page table states provided above, show the final state of the system. Also list for each reference if it is a hit in the TLB, a hit in the page table, or a page fault.
b)Repeat a), but this time use 16 KiB pages instead of 4 KiB pages. What would be some of the advantages of having a larger page size? What are some of the disadvantages?
c)Show the final contents of the TLB if it is 2-way set associative. Also show the contents of the TLB if it is direct mapped. Discuss the importance of having a TLB to high performance. How would virtual memory accesses be handled if there were no TLB?
Valid
Tag
Physical Page Number
LRU
1
11
12
1
1
7
4
2
1
3
6
3
0
4
9
0
Explanation / Answer
a)
The initial Translation lookaside buffer (TLB) is as follows:
Valid
Tag
Physical Page Number
1
11
12
1
7
4
1
3
6
0
4
9
The initial page table is as follows:
Valid
Physical Page or in Disk
1
5
0
Disk
0
Disk
1
6
1
9
1
11
0
Disk
1
4
0
Disk
0
Disk
1
3
1
12
Valid
Physical Page or in Disk
1
5
0
Disk
0
Disk
1
6
1
9
1
11
0
Disk
1
4
0
Disk
0
Disk
1
3
1
12
b)
The given virtual addresses are:
4669, 2227, 13916, 34587, 48870, 12608, 49225
The question does not contain the LRU order for the existing three entries in the TLB, true LRU replacement cannot be used. Using either random replacement or selecting randomly from the three existing entries until they've all been override (an LRU approximation) were both valid options.
The Binary equivalent values of the virtual addresses should be divided as page number and page offset as shown in the below table:
virtual address (In Decimal)
virtual address (In Binary)
Page Number
Page Offset
Virtual page number
4669
1E+12
1
1E+09
1
2227
1E+11
0
1E+11
0
13916
1.1E+13
11
1.1E+10
3
34587
1E+15
1000
1.11E+10
8
48870
1.01E+15
1011
1.11E+11
11
12608
1.1E+13
11
1.01E+08
3
49225
1.1E+15
1100
1001001
12
Now, the virtual page number 1 is not in the TLB in page table is on Disk. This results a page fault.
Select an available physical page number = 3
Update index 1 of the page table as follows:
valid = 1 physical page number = 3
Update the TLB, since the final entry in the TLB has valid = 0, overwrite that line with the following:
valid = 1 tag = 1 physical page number = 3
Then the resultant TLB and the Page table is shown below:
c)
TLB
Valid
Tag
Physical Page Number
1
11
12
1
7
4
1
3
6
1
1
3
Page Table
Valid
Physical Page or in Disk
1
5
1
3
0
Disk
1
6
1
9
1
11
0
Disk
1
4
0
Disk
0
Disk
1
3
1
12
The virtual page number 0 is not in the TLB, but the index 0 in page table is valid.
Valid
Tag
Physical Page Number
1
11
12
1
7
4
1
3
6
0
4
9
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.