edited by
9,248 views
8 votes
8 votes
Consider a virtual memory system with 32-bit virtual addresses and 1 KB pages. Each page table entry requires 32- bits. It is desired to limit the page table size to one page. How many levels of page tables required? Also find the size memory required to store total page tables ?

Please give a detailed solution. I am weak in understanding these concepts. Answer for the first one is 3 and for the second one is  8208 bytes.
edited by

2 Answers

Best answer
13 votes
13 votes

Part 1 :

32-bit virtual addresses and 1 KB pages means virtual address space is 32 bit and each page size is 1KB .

virtual address space is 32 bit  so size of memory = 232 B = 4GB ..(i)

Each page table entry requires 32 bits =  4 B ..(ii)

page size is 1KB = 210 B  ..(iii)

Number of pages  = Number of entries in Innermost PageTable = 232   / 210  = 222   [ Divide (i) by (iii) ] 

Size of Innermost PageTable = 222 * 22  = 224 B  = 24 * 220 B = 16 MB ( as each page table entry =  4 B)

So, Page table has a size of 16MB ( 224 B ) , and thus it cannot fit in one page.

So, that's why we further divide page table into pages and form another page table for these pages (multilevel-paging). That means we keep on repeating above procedure till the size of page table ≤  Page Size

from (iii) we get page size is 210 B .

Number of pages by dividing  PT1 = 224 / 210 = 214  ,

 Page Table 2 ( PT2) size = no of pages * page table entry size = 214 * 22 = 216 = 64 KB

Number of pages by dividing  PT2 =  216   / 210  = 26

Page Table 3 ( PT3) size = 2* 22 = 28 = 256 B ( now 28 < 210 , where page size 210 )

we formed 3 page tables here so 3 levels of page table require .

page table 1 size 16 MB

page table 2 size 64 KB

page table 3 size 256 B

-------

Part 2 :

16 MB = (16*220 ) B = 16,777, 216 B

64 KB = ( 26 * 210 ) B =  65,536 B

so total page table size = ( 224 + 216 + 28 ) B = ( 16,777, 216 + 65,536 + 256 ) B   =  16, 843, 008 B

Then the size of memory required  is 16, 843, 008 B .

selected by
3 votes
3 votes
Offset =10bit
Page number = 22 bit
Page table size = page size
Page table size = 1Kb

If we do single Level paging :$\frac{2^{32}}{2^{10}}*2^{2}=2^{24}$ > page size

If we do 2 level paging: $\frac{2^{24}}{2^{10}}*2^{2}=2^{16}$ > page size

If we do 3 level paging: $\frac{2^{16}}{2^{10}}*2^{2}=2^{8}$ < page size

Hence 3 level paging is required

22 bit are partitioned as  6|8|8

1st page table = $2^{6}*2^{2}=2^{8}$ Bytes

2nd page table = $2^{14}*2^{2}=2^{16}$Bytes

3rd page table = $2^{22}*2^{2}=2^{24}$ Bytes
 Total Memory =16843008B
edited by
Answer:

Related questions

1 votes
1 votes
0 answers
1
rahul sharma 5 asked Dec 6, 2017
584 views
Does inverted page table takes less memory to store a processes as compared to single/multilevel paging?Please explain reason also
0 votes
0 votes
1 answer
2
aditi19 asked May 26, 2019
496 views
Which part of the process image forms the logical address space that is used in paging?
1 votes
1 votes
1 answer
3
Bishes asked Dec 3, 2022
949 views
Can anyone diagrammatically explain what is the difference between Page size vs Page table entry size in a page table?
2 votes
2 votes
1 answer
4
3lurryface asked Jan 9, 2019
1,052 views
If there is 2 or more level paging for processes, is it possible to have more than 1 page fault while accessing any single addressable unit(byte or word) ?