edited by
14,106 views
37 votes
37 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. 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?
edited by

3 Answers

Best answer
53 votes
53 votes
  • $VA = 32\; bits$
  • $PA = 32\; bits$
  • $\text{Page size} = 4\;KB = 2^{12} B$
  • $\text{PTE} = 4 \ B$

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

(A) 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\lceil \frac{2^{32}}{2^{10} \times 4}\right \rceil$

$=\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.$

edited by
14 votes
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
3 votes
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.

edited by

Related questions

16 votes
16 votes
2 answers
3