Paging OS

Question

Consider a byte addressable virtual memory system with 34-bit addresses where the first 23 bits are used as a page number, and the last 11 bits is the offset. Suppose the system using two-level paging, with first n bits (n>11) of the address used as an index into the first-level page table. Assume that a typical program uses 16MB memory. An expression in terms of n that gives the number of second level page-tables used by the typical program is given by

(I'm confused with the language used by this question) Thanks in advance

Options

1.  2²⁴ / 2^(34-n)  
2.  2^(34-n-11) x 2¹¹
3.  2²⁴ /2^(34-n-11)
4.  2^(n-11) x 2¹¹

Comments

program size= 16MB = 2²⁴B

page offset = 11 bits

therefore program consists of 2²⁴/2¹¹ = 2¹³ pages.

now each second level page table contain 2^(23-n) data page entries, 

therefore total page tables at second level = 2¹³/2^(23-n)=2¹³/2^(23-n)

multiplying numerator and denominator by 2¹¹,

we will get 2²⁴/2^(34-n)

---

Yes I got almost part but still total page tables at 2nd level means ?
Isn't there will be one page table which fits in one Page?

---

by second level, it means to say inner level.

---

No of pages is 2^13

So no of 2nd level page table is 2^13/(2^(34-n-11))=it comes out as 2^24/2^(34-n)  (2^11 goes to numerator)

n | 34-n-11 |11

Answer 1

16 MB is program size and 2KB is frame/page size

Number of frames in Physical memory will be $\frac{2^{24}}{2^{11}}=2^{13}$

so we require $2^{13}$ entries in last level of page table

Possible breakup

12|11|11

13|10|11

14|9|11 and so on

let us take 12|11|11 so if we have only 11 bits for second level then we require $\frac{2^{13}}{2^{11}}=2^{2}$ 2nd level page table

let us take 13|10|11 so if we have only 10 bits for second level then we require $\frac{2^{13}}{2^{10}}=2^{3}$ 2nd level page table

let us take 14|9|11 so if we have only 9 bits for second level then we require $\frac{2^{13}}{2^{9}}=2^{4}$ 2nd level page table

 

so consider option 1

for 12|11|11 n=12 $\frac{2^{24}}{2^{34-12}}=2^{2}$ matches with our result

for 13|10|11 n=13 $\frac{2^{24}}{2^{34-13}}=2^{3}$ matches with our result

for 14|9|11 n=14 $\frac{2^{24}}{2^{34-14}}=2^{4}$ matches with our result

option 1 is correct

Comments

Program uses 16MB means it is size of program, isn't it?

then $2^{13}$ will be program pages... correct ?

---

Yes $2^{13}$ frames of program

Answer 2

Consider the division |n|23-n|11|(Keep this in mind.)

The number of bits that have been used in second level page table for indexing pages of the program = 23-n

The size of the program covered by one frame of second level page table = 2^(23-n) * 2^11Bytes

The number of frames required to cover 16 MB of the program = 16MB / 2^(23-n)*2^11

=2^24/2^(34-n).