If 10 bits for level 1 index it is 2^10 entries and same for level 2.If indexing requires 10 bits 2^10 enteries.What did you calculate 2^20 ?

26 votes

A computer uses $32-bit$ virtual address, and $32-bit$ physical address. The physical memory is byte addressable, and the page size is $4$ $\text{kbytes}$ . It is decided to use two level page tables to translate from virtual address to physical address. An equal number of bits should be used for indexing first level and second level page table, and the size of each table entry is $4$ bytes.

- Give a diagram showing how a virtual address would be translated to a physical address.
- What is the number of page table entries that can be contained in each page?
- How many bits are available for storing protection and other information in each page table entry?

38 votes

Best answer

- $VA = 32\; bits$
- $PA = 32\; bits$
- $\text{Page size} = 4\;KB = 2^{12} B$
- $PTE = 4 \ B$

Since page size is $4$ KB we need $\lg 4K = 12 $ bits as offset bits.

It is given that Equal number of bits should be used for indexing first level and second level page table. So, out of the remaining $32-12 = 20$ bits $10$ bits each must be used for indexing into first level and second level page tables as follows:

**B**) Since $10$ bits are used for indexing to a page table, number of page table entries possible $=2^{10} = 1024.$ This is same for both first level as well as second level page tables. ^{ }

C)

Frame no $= 32$ bit (Physical Address) $- 12$ (Offset) $= 20$

No. of bits available for Storing Protection and other information in second level page table

$= 4 \times 8 - 20$

$= 32-20 = 12\;Bits$

No. of bits in first level page table to address a second level page table is $\log_2$ of

$\frac{\text{Physical memory size}}{\text{#Entries in a Second level page table $\times$ PTE size}}$

$=\log_2 \left[\frac{2^{32}}{2^{10} \times 4}\right]$

$=\log_2 \left(2^{20}\right)$

$=20\; bits.$

So here also, the no. of bits available for Storing Protection and other information $=32-20 =12\; bits.$

0

Whats the answer for 2nd part? Is is $2^{20}$ or $2^{10}$

If 10 bits for level 1 index it is 2^10 entries and same for level 2.If indexing requires 10 bits 2^10 enteries.What did you calculate 2^20 ?

If 10 bits for level 1 index it is 2^10 entries and same for level 2.If indexing requires 10 bits 2^10 enteries.What did you calculate 2^20 ?

0

Shouldn't be the no. of entries per page in each level equal to (Page Size/PTE = $2^{12}/2^{2} = 2^{10}$) (10 bits)?

3

@Shubhgupta, yes we can calculate with using that formula also... but in last-level ( outer level ) may our page doesn't full with entries, at that time we can't use, in this example outer page table also full,so you can use that formula.

@vinay chauhan, it is

in-direct formula for finding no.of bits required for identifying a frame

How?

(#Entries in a Second level page table × PTE size) = page size

Physical memory size/ page size = no.of frames

log_{2} ( no.of frames ) = no.of bits required for identifying a frame

4

For part c you can think what is size of page table entry?? It's 32 bits now each page table entry contains frame nos + other bits. Now how many frames you can have? Simple physical address space / page size. Is 2^32/2^12 = 2^20 means out of 32 bits available for each page table entry 20 bits needed for frame nos and remaining 12 bits for other information.

0

@Shaik Masthan can you please provide the theory part from where you have studied about multilevel paging?

0

@Shaik Masthan @Arjun Can we simple do like this -

No. of $2nd$ level page tables $= 2^{10}*2^{10} = 2^{20}$, therefore $32-20=12$ bits required?

0

In "**B. What is the number of page table entries that can be contained in each page?**", we are asked no. of page table entries that can be contained in each page for both the **first level** **(innermost)** and **second level (outermost)** page table. We calculated the **page table size** for **second level** page table which is equal to **page size** and therefore, **we need not to divide this second level page table into pages**.

My doubt is that this Part B. is specifically for first level page table and not for second level page table coz we don't require second level page table to be broken down into pages.

**Edit:** My bad. I got my answer. **Second level** page table is going to be divided into a **single page only.**

1

Tell me one thing

Here according to the question

No. of bits in first level page table to address a second level page table is log2 of $2^{20}$

i.e. 20 bit and frame size 12 bit

So, virtual address space is 32 bit as given in question.

But, how do we getting this 12 bit

Storing Protection and other information =32−20=12bits.

Already we have 32 bit information, then from where getting this 12 bit??

14 votes

B) Since page size is 4KB. And one page entry size is 4B So no of entries in 1 page=1K C) Since each page entry size =4B=32bits And since physical address is of 32bits And frame offset=page offset=12 bits So frame no bits will be=32-12=20 So bits for other purpose=page entry size-frame no bits=32-20=12 bits

0

the significance of "Equal number of bits should be used for indexing first level and second level page table" is?

3 votes

2^(i+j)=2^32/2^12=2^20. and here i=j(where 2^i is the no of PTE in ist level table and 2^j is the no of PTE in 2nd level table), so no of page table entry in a table(for both ist level and 2nd level are same)=2^10

the no of bits in ist level page table to address 2nd level page table =physical address space/2nd level page table size=2^32/2^12=2^20 ..but page table entry is of size 4B ie. 32 bits. so 32-20=12 can be used for other purpose.. no of bits in 2nd level page table to address a page=no of pages =physical address space/page size=2^32/2^12=2^20.so here also remaining 12 bits can be used for other purpose. Here the page table size=page size. so, for both ist level and 2nd level page table the answer is same that is 12.