October 28, 2023
October 28, 2023
October 28, 2023
###### GATE 2021 CS-Set-2
October 28, 2023
 Question 53
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

The page size is 4KB (1KB = 210bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2GB (1GB = 230bytes) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of P across all levels is ________ KB.

 A 8.01
Question 53 Explanation:

A system can support upto 2^39 bytes of Virtual address space. Three level paging is used with Level 1 (9 bits), Level 2 (9 bits) and Level 3 (9 bits) and page offset of 12 bits.

Page table entry is 8 bytes at every level. Therefore,

Level 3 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 2 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 1 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame).

However, the process P has a virtual address space of 2^31 bytes. Thus, it is clear that the last level page table does not occupy the frame completely. Let x be the number of bits indexed in the last level.

Therefore, we can  have (2^x) * (2^9) * (2^9)* (2^12) = 2^31 => x =1. Thus, the minimum size of page table for process P would be,

Page table size at level-1 + Page table size at level-2 + Page table size at level-3 =

2^1 * 8bytes +  2^9 * 8bytes +  2^9 * 8bytes = (1026)*8 bytes = 8.01 KB

Question 53 Explanation:

A system can support upto 2^39 bytes of Virtual address space. Three level paging is used with Level 1 (9 bits), Level 2 (9 bits) and Level 3 (9 bits) and page offset of 12 bits.

Page table entry is 8 bytes at every level. Therefore,

Level 3 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 2 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 1 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame).

However, the process P has a virtual address space of 2^31 bytes. Thus, it is clear that the last level page table does not occupy the frame completely. Let x be the number of bits indexed in the last level.

Therefore, we can  have (2^x) * (2^9) * (2^9)* (2^12) = 2^31 => x =1. Thus, the minimum size of page table for process P would be,

Page table size at level-1 + Page table size at level-2 + Page table size at level-3 =

2^1 * 8bytes +  2^9 * 8bytes +  2^9 * 8bytes = (1026)*8 bytes = 8.01 KB