The virtual address space of a process is 1 GB large. Assume that the size of a
ID: 3762491 • Letter: T
Question
The virtual address space of a process is 1 GB large. Assume that the size of a page size is 4KB. What is the maximum size of a page table in memory if each page table entry requires 4 bytes? Assume a 4KB large page and frame size. Consider the following page table associated with a process:
Page# Frame# Valid/Invalid
0 1 v
1 4 v
2 3 v
3 5 i
4 10 v
The table shows the page and frame number as well as the valid and invalid bit per page table entry. What is the physical addresses for the virtual address 0x500?
Enter information in hexadecimal (must start with 0x). Enter the string "PF" if a virtual address resolution triggers a page fault.
Explanation / Answer
We need to analyze memory and time requirements of paging schemes in order to make a decision. Average process size is considered in the calculations below.
1 Level Paging
Since we have 2^23 pages in each virtual address space, and we use 4 bytes per page table entry, the size of the page table will be 2^23 * 2^2 = 2^25. This is 1/256 of the process' own memory space, so it is quite costly. (32 MB)
2 Level Paging
The address would be divided up as 12 | 11 | 13 since we want page table pages to fit into one page and we also want to divide the bits roughly equally.
Since the process' size is 8GB = 2^33 B, I assume what this means is that the total size of all the distinct pages that the process accesses is 2^33 B. Hence, this process accesses 2^33 / 2^13 = 2^20 pages. The bottom level of the page table then holds 2^20 references. We know the size of each bottom level chunk of the page table is 2^11 entries. So we need 2^20 / 2^11 = 2^9 of those bottom level chunks.
The total size of the page table is then:
3 Level Paging
For 3 level paging we can divide up the address as follows:
8 | 8 | 7 | 13
Again using the same reasoning as above we need 2^20/2^7 = 2^13 level 3 page table chunks. Each level 2 page table chunk references 2^8 level 3 page table chunks. So we need 2^13/2^8 = 2^5 level-2 tables. And, of course, one level-1 table.
The total size of the page table is then:
As easily seen, 2-level and 3-level paging require much less space then level 1 paging scheme. And since our address space is not large enough, 3-level paging does not perform any better than 2 level paging. Due to the cost of memory accesses, choosing a 2 level paging scheme for this process is much more logical.
//size of the outer page table //total size of the inner pages 1 * 2^12 * 4 + 2^9 * 2^11 * 4 = 2^20 * ( 2^-6 + 4) ~4MBRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.