# GATE2002-19

4.8k 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?

edited

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

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 ?
2

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

log2 ( 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??

0
i think  size of each entry 4B=total 2^32 entry possible

so out of this frames(2^20)  left storing information  and protection
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?

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

0

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

## Related questions

1
1.1k views
The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function int TEST-AND-SET (int *x) { int y; A1: y=*x; A2: *x=1; A3: return y; } Complete the following C functions for implementing code for entering and ... and starvation-free? For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic?
The following solution to the single producer single consumer problem uses semaphores for synchronization. #define BUFFSIZE 100 buffer buf[BUFFSIZE]; int first = last = 0; semaphore b_full = 0; semaphore b_empty = BUFFSIZE void producer() { while(1) { produce an ... $p2$, immediately after $c1$ and immediately before $c2$ so that the program works correctly for multiple producers and consumers.
Relation $R$ with an associated set of functional dependencies, $F$, is decomposed into $\text{BCNF}$. The redundancy (arising out of functional dependencies) in the resulting set of relations is Zero More than zero but less than that of an equivalent $3NF$ decomposition Proportional to the size of F+ Indeterminate