The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.9k 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$ $\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.

  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?
asked in Operating System by Veteran (59.7k points)
edited by | 2.9k views

3 Answers

+29 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:

Multi level paging

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

answered by Boss (43.2k points)
edited by
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 ?
+1

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

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)?
0
Can anyone explain the logic behind C second part?
+1

@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

 log2 ( no.of frames ) =  no.of bits required for identifying a frame

+1
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?
+10 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
answered by Active (2.3k points)
0

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

0

@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 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.

answered by Active (4.3k points)
edited by

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,199 questions
49,669 answers
163,548 comments
65,818 users