Question

Question: As described in Section 5.7, virtual memory uses a page table to track the mapping of virtual addresses to physical addresses. This exercise shoes 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. If pages must be brought in from disk, increment the next largest page number.

4669, 2227, 13916, 34587, 48870, 12608, 49225

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.11.1) 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.

(5.11.2) Repeat 5.11.1, 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?

(5.11.3) 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 handles if there were no TLB?

There are several parameters that impact the overall size of the page table. Listed below are key page parameters.

Virtual Address Size	Page Size	Page Table Entry Size
32 bits	8 KiB	4 bytes

(5.11.4) Given the parameters shown above, calculate the total page table size for a system running 5 applications that utilize half of the memory available.

(5.11.5) Given the parameters shown above, calculate the total page table size for a system running 5 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 amount of memory required.

(5.11.6) A cache designer wants to increase the size of a 4 KiB virtually indexed, physically tagged cache. Given the page size shown above, is it possible to make a 16 KiB direct-mapped cache, assuming 2 words per block? How would the designer increase the data size of the cache?

Short answer

(5.11.1)

The final state of the system is:

Valid	Tag	Physical Page Number
1	12	15
1	8	14
1	3	6
1	11	12

(5.11.2)

The final state of the system is:

Valid	Tag	Physical Page Number
1	2	13
1	7	4
1	3	6
1	0	5

The advantage is a decrease in TLB miss and the disadvantage is more fragmentation.

(5.11.3)

The content of TLB for 2-way set associative:

Valid	Tag	Index	Physical Page Number
1	6	0	15
1	1	1	6
1	4	0	14
1	5	1	11

The final content for direct-mapped TLB is:

Valid	Tag	Index	Physical Page Number
1	3	0	15
1	0	1	13
1	3	2	6
1	0	3	6

(5.11.4)

The total page table size is 5 MB.

(5.11.5)

The minimum amount of memory for the two-level page table approach is 5MB + 3840 bytes. The maximum amount of memory for the two-level page table approach is 10MB + 7680 bytes.

(5.11.6)

The size of the cache can be increased using a 2-way set associative. It is not possible to use direct-mapped.

Step-by-step solution

Identify the formula to calculate virtual page, how TLB and page table hit or miss or a page fault are identified, and LRU replacement

The page size is 4 KiB. It means each page contains 4096 entries. For each reference, the page number can be calculated using the following:

If the page reference is available in TLB, then it is a TLB hit. Otherwise, it’s a TLB miss. Then check If it is available in Page Table. If so, it is a page table hit. And if the page is on disk, then it is a page fault.

In the LRU replacement, if the page needs to be replaced, then the least recently used page is replaced.

Find the final state of the system for given page references and identify if the reference is TLB and the page table hit or miss or a page fault

(5.11.1)

The first reference is 4663. The virtual page of this page number is 1. In the TLB table, under the “Tag” column, 1 is not available. So, it is a TLB miss. Now check row 1 of a page table. The valid bit is 0 means the page is on disk. So, it is a page table miss and page fault. The TLB changes as below:

Valid	Tag	Physical Page Number
1	11	12
1	7	4
1	3	6
1	1(recently used 1)	13

The entry with valid bit 0 is changed. The recently used tag is entered and the physical number is set to the next largest page number (as described in question).

The second reference is 2227. The virtual page number is 0. It is not available in TLB. So, it’s a TLB miss. In the page table, row 0 has a valid bit 1. The physical page is 5. So, it’s a page table hit. The TLB changes as below:

Valid	Tag	Physical Page Number
1	0(recently used 2)	5
1	7	4
1	3	6
1	1(recently used 1)	13

The third reference is 13916. The virtual page number is 3. It is available in TLB. So, it’s a TLB hit. There is no need to check the page table.

Valid	Tag	Physical Page Number
1	0(recently used 2)	5
1	7	4
1	3(recently used 3)	6
1	1(recently used 1)	13

The fourth reference is 34587. The virtual page number is 8. It is not available in TLB. So, it is a TLB miss. In row 8 of the page table, the valid bit is 0. So, it’s a page table miss and page fault. The TLB changes as below:

Valid	Tag	Physical Page Number
1	0(recently used 2)	5
1	8(recently used 4)	14
1	3(recently used 3)	6
1	1(recently used 1)	13

The fifth reference is 48870. The virtual page number is 11. The page number is not in TLB. So, it’s a TLB miss. Row 11 of the page table has valid bit 1. The physical page number is 12. The TLB is updated as:

Valid	Tag	Physical Page Number
1	0(recently used 2)	5
1	8(recently used 4)	14
1	3(recently used 3)	6
1	11(recently used 5)	12

The next reference is 12608. The virtual page number is 3. The page is available in TLB. So, it’s a TLB hit. There is no need to check the page table.

Valid	Tag	Physical Page Number
1	0(recently used 2)	5
1	8(recently used 4)	14
1	3(recently used 6)	6
1	11(recently used 5)	12

The last reference is 49225. The virtual page number is 12. The page is not available in TLB. So, it’s a TLB miss. Page 12 is not available on the page table too. So, it’s a page table miss and page fault.

The final state of the system is:

Valid	Tag	Physical Page Number
1	12	15
1	8	14
1	3	6
1	11	12

Find the final state of the system for given page references and identify if the reference is TLB and the page table hit or miss or a page fault with page size 16 KiB

(5.11.2)

The first-page reference is 4669. The virtual page number is 0. It is not available in TLB. So, it’s a TLB miss. The page table for virtual page number 1 has a 1 valid bit. The physical page number is 5. The TLB changes as:

Valid	Tag	Physical Page Number
1	11	12
1	7	4
1	3	6
1	0(recently used 1)	5

The next reference is 2227. The virtual page number is 0. It’s available in TLB. So, it’s a TLB hit.

The next reference is 13916. The virtual page number is 0. It’s available in TLB. So, it’s a TLB hit.

The next reference is 34587. The virtual page number is 2. It’s not available in TLB. It’s a TLB miss. Row 2 has a valid bit 0. So, it’s a TLB miss and page fault. The TLB is updated as:

Valid	Tag	Physical Page Number
1	2(recently used 2)	13
1	7	4
1	3	6
1	0(recently used 1)	5

The next page reference is 48870. The virtual page number is 2. It’s available in TLB. It’s a TLB hit.

The next reference is 12608. The virtual page number is 0. It’s also available in TLB. It’s a TLB hit.

The next reference is 49225. The virtual page number is 3. It’s also available in TLB. It’s a TLB hit.

The final state of the system is:

Valid	Tag	Physical Page Number
1	2	13
1	7	4
1	3	6
1	0	5

Advantages and disadvantages of having a larger page size

The advantage of using a larger page size is the increase in the number of TLB hits. With 16 KiB page size, there are more TLB hits as compared to 4KiB. So, there is no need to check the page table most of the time.

But with large page sizes, the drawback is higher fragmentation. It has the disadvantage of less efficient utilization of physical memory.

Identify the final content of the TLB using a 2-way set associative

(5.11.3)

With a 2-way set associative, the LSB is used for the index and the next three bits are used for the tag. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	11	0	12
1	7	0	4
1	3	0	6
0	4	0	9

The first reference is 4669. The virtual address is 1. The tag is 0 and the index is 1. It’s TLB miss. In the page table, the valid bit for this is 0. So, it’s a page table miss and page fault. The TLB content is updated as:

Valid	Tag	Index	Physical Page Number
1	11	0	12
1	7	0	4
1	3	0	6
1	0(recently used 1)	1	13

The second reference is 2227. The virtual address is 0. The tag is 0 and the index is 0. It’s TLB miss. The page table provides a physical address 5. So, it’s a page table hit. The TLB content is updated as:

Valid	Tag	Index	Physical Page Number
1	0(recently used 2)	0	5
1	7	0	4
1	3	0	6
1	0(recently used 1)	1	13

The third reference is 13916. The virtual address is 3. The tag is 1 and the index is 1. It’s TLB miss. The page table provides a physical address for 3. So, it’s a page table hit. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	0(recently used 2)	0	5
1	1(recently used 3)	1	6
1	3	0	6
1	0(recently used 1)	1	13

The fourth reference is 34587. The virtual address is 8. The tag is 4 and the index is 0. It’s TLB miss. The page table provides has no physical address. So, it’s a page table miss and page fault. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	0(recently used 2)	0	5
1	1(recently used 3)	1	6
1	4(recently used 4)	0	14
1	0(recently used 1)	1	13

The fifth reference is 48870. The virtual page number is 11. The tag is 5 the and index is 1. It’s a TLB miss. The page table provides physical addresses. It’s a page table miss. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	0(recently used 2)	0	5
1	1(recently used 3)	1	6
1	4(recently used 4)	0	14
1	5(recently used 5)	1	11

The sixth reference is 12608. The virtual page number is 3. The tag is 1 the and index is 1. It’s a TLB hit.

Valid	Tag	Index	Physical Page Number
1	0(recently used 2)	0	5
1	1(recently used 3)	1	6
1	4(recently used 6)	0	14
1	5(recently used 5)	1	11

The seventh reference is 49225. The virtual page number is 12. The tag is 6 and the index is 0. It’s a TLB miss. It’s also page table miss and page fault.

The final content of TLB is:

Valid	Tag	Index	Physical Page Number
1	6	0	15
1	1	1	6
1	4	0	14
1	5	1	11

Identify the final content of the TLB using direct-mapped

With direct-mapped, the two LSB are used for indexing and the rest for mapping. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	11	0	12
1	7	1	4
1	3	2	6
0	4	3	9

The first reference is 4669. The virtual address is 1. The tag is 0 and the index is 1. It’s TLB miss. It’s page table miss and page fault. With direct-mapped, entry 1 will be changed. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	11	0	12
1	0	1	13
1	3	2	6
0	4	3	9

The second reference is 2227. The virtual address is 0. The tag is 0 and the index is 0. It’s a TLB miss. It’s a page table hit. Entry 0 of the TLB is updated as:

Valid	Tag	Index	Physical Page Number
1	0	0	5
1	0	1	13
1	3	2	6
0	4	3	9

The third reference is 13916. The virtual address is 3. The tag is 0 and the index is 3. It’s a TLB miss. It’s a page table hit. The TLB content is updated as:

Valid	Tag	Index	Physical Page Number
1	0	0	5
1	0	1	13
1	3	2	6
1	0	3	6

The fourth reference is 34587. The virtual address is 8. The tag is 2 and the index is 0. It’s TLB miss. It’s also page table miss and page fault. The TLB content is updated as:

Valid	Tag	Index	Physical Page Number
1	2	0	14
1	0	1	13
1	3	2	6
1	0	3	6

The fifth reference is 48870. The virtual page number is 11. The tag is 2 and the index is 3. It’s TLB miss. Its page table hit and its physical address is 12. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	2	0	14
1	0	1	13
1	3	2	6
1	2	3	12

The sixth reference is 12608. The virtual page number is 3. The tag is 0 and the index is 3. It’s TLB miss. It’s also page table hit and the physical address is 6. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	2	0	14
1	0	1	13
1	3	2	6
1	0	3	6

The seventh reference is 49225. The virtual page number is 12. The tag is 3 and the index is 0. It’s TLB miss and page table miss. Also, a page fault. The TLB content is:

Valid	Tag	Index	Physical Page Number
1	3	0	15
1	0	1	13
1	3	2	6
1	0	3	6

Importance of TLB

TLBs avoid high access time for converting virtual addresses to physical addresses. For frequent memory access, instead of using a page table to look into for physical address, TLB can be used. It gives less access time.

Without using TLB, every virtual address is translated using a physical address. The virtual address is converted to a physical address using a page table only. It slows down the system.

Formula to calculate total page table size

The total page table size is calculated using the following formula:

Page table size = Number of entries * Page table entry size

Calculation of page table size

(5.11.4)

The size of the virtual address is 32 bits. The page size is 8KiB. This is equal to bytes. So, 13 bits are used for the offset. The size of the tag is 32-13 = 19 bits. The page table entry size is 4 bytes. For 5 applications, utilizing half of the memory available, the total page size is:

The total page size is 5 MB.

Calculation of the minimum amount of memory for the two-level page table approach:

(5.11.5)

The applications utilize half of the memory available. For 8KB page size, 19 are page number bits and 13 are offset bits. For the two-level page table,

The first level uses 8 bits for 256 entries. The number of entries in the second level is 2048 bits.

For 5 applications, the memory required for the second level application is:

For 5 applications, the memory required for the first level application is:

Calculation of the maximum amount of memory for the two-level page table approach:

For 5 applications, the memory required for the second level application is:

For 5 applications, the memory required for the first level application is:

Increasing the size of the cache

(5.11.6)

The size of the direct-mapped cache is 16KB. There is 2 word per block. The size of the block is 8 bytes. The total number of blocks is calculated as:

The 14-bit address is used. 11 bits are used for the index, 3 bits for offset). So, a 2-way associative cache should be used to increase the size of the 16 KB cache.