2.1k views

A computer uses 32-bit virtual address, and 32-bit physical address. The physical memory is byte addressable, and the page size is 4 kbytes. It is decided to use two level page tables to translate from virtual address to physical address. 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.

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

• $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.$

selected by
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 ?

diagram for part a as two-level page table is used.

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

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

@Arjun sir in the question ,

Equal number of bits should be used for indexing first level and second level page table,

so , the answer given by akash shouldn't split $20$ to $10$ and $10$?

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.