Question

Question: In this exercise, we will examine space/time optimizations for page tables. The following list provides parameters of a virtual memory system.

Virtual Address (bits)	Physical DRAM Installed	Page Size	PTE Size (byte)
43	16 GiB	4KiB	4

(5.12.1) For a single-level page table, how many page table entries (PTEs) are needed? How much physical memory is needed for storing the page table?

(5.12.2) Using a multilevel page table can reduce the physical memory consumption of page tables, by keeping active PTEs in physical memory. How many levels of page tables will be needed in this case? And how many memory references are needed for address translation if missing in TLB?

(5.12.3) An inverted page table can be used to further optimize space and time. How many PTEs are needed to store the page table? Assuming a hash table implementation, what are the common case and worst case numbers of memory references needed for servicing a TLB miss?

The following table shows the contents of a 4-entry TLB.

Entry-ID	Valid	VA Page	Modified	Protection	PA Page
1	1	140	1	RW	30
2	0	40	0	RX	34
3	1	200	1	RO	32
4	1	280	0	RW	31

(5.12.4) Under what scenarios would entry 2’s valid bit be set to zero?

(5.12.5) What happens when an instruction writes to VA page 30? When would software managed TLB be faster than hardware managed TLB?

(5.12.6) What happens when an instruction writes to VA page 200?

Short answer

(5.12.1)

The page table entries are and the page table size is .

(5.12.2)

The number of levels needed is four. On TLB miss, the references needed for address translation is also four.

(5.12.3)

The page table entries needed to store the page table are . With hash table implementation, the best-case scenario requires one memory reference and the worst-case scenario requires memory references equal to the number of page table entries.

(5.12.4)

Entry 2’s valid bit is set to zero if there is a context switch of processes and it is no longer a valid translation.

(5.12.5)

When an instruction writes to a VA page 30, it is a TLB miss. The software managed TLB is faster than hardware managed TLB in case of TLB miss available in the processor’s cache.

(5.12.6)

When an instruction writes to VA page 200, an interrupt is generated.

Step-by-step solution

Formula to calculate the number of page table entries (PTEs) and memory to store page table

(5.12.1)

The number of entries in the page table is calculated using the following formula:

……… (1)

The memory required to store the page table is given as:

Calculation of PTEs and page table size

The virtual address uses 43 bits. So, the virtual address space is 2⁴³ bits. The size of the page is 4 KiB. This is equal to 2¹² byte. So, the number of PTEs is:

The size of each PTE is 4 bytes. Thus, the page table size is:

The page table size is equal to 8GB.

Formula to calculate the number of levels required in the multilevel page table

(5.12.2)

Multilevel page tables have tree-like structures to hold the page tables. The required number of levels is calculated using the following formula:

Calculation of number of levels and memory references required in case of TLB miss

The number of bits required to represent virtual address space is 43. The size of the page is 4 KiB. Each page table entry is of size 4 bytes. Therefore, the number of entries on each page is:

Therefore, 10 bits are required to represent one entry on a page. As the number of page table entries is 2³¹, 31 bits are required to represent a page.

The number of levels are equal to:

If there is a TLB miss, then memory references are equal to the number of levels in a multilevel page table. In this case, the number of levels is four. So, the number of memory references is four.

Calculation of PTEs needed to store the inverted page table

(5.12.3)

The number of entries in the Inverted page table is given as:

The physical address space is 16 GiB. It is equal to 2³⁴ bytes. The page size is 4 KiB. It is equal to 2¹² byte. The number of entries is equal to:

Number of memory references in hash table implementation

In the best or common case, the is no hash conflict. So, only one memory reference is required to translate the address. In the worst case, the number of memory references is equal to the number of entries. Because the number of entries is 2²². So, if there is a TLB miss then in a worst-case scenario, the number of memory references is 2²².

Identify the meaning of the valid bit set to 0 in TLB

(5.12.4)

TLB contains the translation of virtual page numbers to physical page numbers. The valid bit in TLB refers to whether the entry in TLB is valid or not. If the value of the valid bit is 1, then it’s a valid translation otherwise it’s an invalid translation.

Entry 2’s valid bit is 0 in case there is a context switch of processes. It means that the page is removed from the memory. It is no longer available at the mentioned physical address.

Analyze the scenario of writing to a VA page 30

(5.12.5)

TLB contains a translation of virtual pages to physical pages. Writing to a VA page 30 searches in the TLB whether the translation of this page is available. The given TLB doesn’t contain any VA 30. The four entries of the TLB contain VA 140, 49, 200, and 280. So, it will generate a TLB miss.

The software TLBs are faster than hardware TLBs when the missed TLBs are found in the processor’s cache.

Analyze the scenario of writing to a VA page 200

(5.12.6)

Writing to a VA page 200 searches for the physical address in TLB. TLB contains an entry for VA page 200. The valid bit for this entry is 1. So, the translation is valid too. But this page is Read-only, that is, there are no write permissions for this page. The page cannot be written to. So, it generates an interrupt.