Exercise 5.10 As described in Section 5.4, 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 table is a stream of virtual addresses as seen on a system. Assume 4 KB pages, a four-entry fully associative TLB, and true LRU replacement. If pages must be brought in from disk, increment the next largest page number.

a. 4095, 31272, 15789, 15000, 7193, 4096, 8912

b. 9452, 30964, 19136, 46502, 38110, 16653, 48480 TLB Valid Tag Physical Page Number 1 11 12 1 7 4 1 3 6 0 4 9 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 5.10.1 [10] <5.4> Given the address stream in the table, and the shown initial state of the TLB and page table, show the fi nal 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.
5.10.2 [15] <5.4> Repeat Exercise 5.10.1, but this time use 16 KB pages instead of 4 KB pages. What would be some of the advantages of having a larger page size?
What are some of the disadvantages?
5.10.3 [15] <5.3, 5.4> Show the fi nal contents of the TLB if it is two-way setassociative.
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?
There are several parameters that impact the overall size of the page table. Listed below are several key page table parameters.
Virtual address size Page size Page table entry size

a. 32 bits 4 KB 4 bytes

b. 64 bits 16 KB 8 bytes 5.10.4 [5] <5.4> Given the parameters in the table above, calculate the total page table size for a system running fi ve applications that utilize half of the memory available.

5.10.5 [10] <5.4> Given the parameters in the table above, calculate the total page table size for a system running fi ve applications that utilize half of the memory available, given a two-level page table approach with 256 entries. Assume each entry of the main page table is 6 bytes. Calculate the minimum and maximum amount of memory required.
5.10.6 [10] <5.4> A cache designer wants to increase the size of a 4 KB virtually indexed, physically tagged cache. Given the page size listed in the table above, is it possible to make a 16 KB direct-mapped cache, assuming two words per block?
How would the designer increase the data size of the cache?