GATE CSE 2013 | Question: 52

Question

A computer uses $46\text{-bit}$ virtual address, $32\text{-bit}$ physical address, and a three–level paged page table organization. The page table base register stores the base address of the first-level table $\text{(T1)}$, which occupies exactly one page. Each entry of $\text{T1}$ stores the base address of a page of the second-level table $\text{(T2)}$. Each entry of $\text{T2}$ stores the base address of a page of the third-level table $\text{(T3)}.$ Each entry of $\text{T3}$ stores a page table entry $\text{(PTE)}.$ The $\text{PTE}$ is $32$ bits in size. The processor used in the computer has a $1\;\textsf{MB}\; 16$ way set associative virtually indexed physically tagged cache. The cache block size is $64$ bytes.

What is the size of a page in $\textsf{KB}$ in this computer?

• A. $2$
• B. $4$
• C. $8$
• D. $16$

Comments

# Levels in the page table = Ceil{(46 - Page Offset Bit)/(Page Offset Bit - 2)} = 3 Just go by option elimination methods Say option C is 8KB so 2¹³ so put 13 there (46-13)/(13-2)= 3 so Page Size is 8KB

---

can you more eloborate that @naveendewangan ? i can't get your intution but found another approach... so tell me.

---

Actuallu cache information in this question is extra which is used by Cache Controller hardware while Paging is handled by Memory Management Unit hardware, so we don't need caching information while handling this paging question.

Answer 1

Let the page size be $x$.

Since virtual address is $46$ bits, we have total number of pages $ = \frac{2^{46}}{x}$

We should have an entry for each page in last level page table which here is $T3$. So,
Number of entries in $T3$ (sum of entries across all possible $T3$ tables) $ = \frac{2^{46}}{x}$

Each entry takes $32$ bits $= 4$ bytes. So, total size of $T3$ tables $= \frac{2^{46}}{x} \times 4 = \frac{2^{48}}{x}$ bytes

Now, no. of $T3$ tables will be Total size of $T3$ tables/page table size and for each of these page tables, we must have a $T2$ entry. Taking $T3$ size as page size, no. of entries across all $T2$ tables $= \frac{\frac{2^{48}}{x}}{x} = \frac{2^{48}}{x^2} $

Now, no. of $T2$ tables (assuming $T2$ size as page size) = $\frac{2^{48}}{x^2}  \times 4$ bytes = $\frac{\frac{2^{50}}{x^2}} {x}  = \frac{2^{50}}{x^3}$.

Now, for each of these page table, we must have an entry in $T1$.
So, number of entries in $T1$ $=\frac{2^{50}}{x^3}$

And size of $T1$ $=\frac{2^{50}}{x^3} \times 4  =\frac{2^{52}}{x^3} $

Given in question, size of $T1$ is page size which we took as $x$. So,
$x = \frac{2^{52}}{x^3}$
$\implies x^4 =2^{52}$
$\implies x = 2^{13}$
$\implies x = 8\;\textsf{KB}$

Correct Answer: $C$

Comments

In the question , the size of an entry in T2 and T1 page tables , has not been mentioned , neither have they told that PTE is same across all levels.Same for Page Table size , they have only said that T1 fits in one Page , but for T2 and T3  , nothing has been mentioned ,So how did you assume that size of T2 and T3 is equal to size of one Page

 

---

So basically in this question, assumption is that all page table pages have same size which is not always necessary! right?

---

here I don't understand the cache information given, if we try to find the tag, index, offset bits it comes out to be (30, 10, 6) respectively

but for VIPT, shouldn't the bits for index and cache offset (total 16 bits) be less than or equal to page offset bits? so that we can use the correct virtual index for the cache?

but acc to the answer page offset will be 13 bits, so we're okay with the VIPT constraint being violated?

EDIT: the answer for this was in the next question. the leftover 3 bits are used by OS to ensure that one cache set has all the pages with the same 3 bits, so that two synonym virtual addresses are not in different cache sets

Answer 2

I have already mentioned this in a comment, in case anyone missed it.

Alternate method to find page size:

It is known that all levels of the page table must be completely full, except for the outermost level. The outermost page table may occupy a full page or less. However, in this question, it is explicitly mentioned that the outermost page table occupies a full page.

Let the page size be \( 2^p \) Bytes.

Given:
Page Table Entry (PTE) size = 32 bits = 4 Bytes = \( 2^2 \) Bytes.

Number of entries in any page of any page table is:

\[ \frac{\text{Page size}}{\text{PTE size}} = \frac{2^p}{2^2} = 2^{p - 2} \]

Hence, the logical address is split as:

\( p - 2 \)

\( p - 2 \)

\( p - 2 \)

\( p \)

Given that the logical address space is 46 bits, we get:

\[ (p - 2) + (p - 2) + (p - 2) + p = 46 \] \[ \Rightarrow 4p - 6 = 46 \Rightarrow p = 13 \]

Therefore, the page size is:

\[ 2^{13} \text{ Bytes} = \boxed{8\ \text{KB}} \]

Comments

@Sachin Mittal 1 Sir here is why we have considered that at each level chunk size is equal to the page size is this because of this info "The page table register stores the base address of the first-level table (T1),which occupies exactly one page." (OR) is it because that they had not mentioned about the chunk size at each level except first we are free to assume that at each level chunk size is equal to the page size...??

---

@Karthik07 They should give it but since it is not given, we have no choice left but to consider chunk sizes as page sizes only.

---

Thanks @Sachin Mittal 1 sir

Answer 3

I feel this is simpler approach,

(C)

Let size of the page be x.

Total number of entries in T1 = x/4.

Total number of entries in T2 = x/4 * x/4

Total number of entries in T3 = x/4 * x/4 * x/4 which is also total number of pages

Total virtual address space = (x/4 * x/4 * x/4) * x = 2^46

∴ x4/2^6 = 2^46

∴ x = 2^13 bytes = 8Kb

 

Comments

nice approach.

---

Plz explain how  take t1=x/4.

---

Why are we taking page table size as same as page size ?

Can you please elaborate

Answer 4

let page size is P bytes. Page table entry size  = 4byte.

PA = 32 bits   VA = 46 bits

it is given that outermost page table is completly full.

∴ no. of entries in outer page table = (P/4).

∴ total no. of entries in 2nd level page table = (P/4)*(P/4)

∴ total no. of entries in  3rd level page table = (P/4)*(P/4)*(P/4)

virtual address space = total pages * size of each pge

                                    = (P/4)*(P/4)*(P/4) * P 

                                     = P⁴ /64

    2⁴⁶ = P⁴ /64

  P  = 2¹³ B

      = 8KB

Comments

@arjun sir is this a correct solution?

---

 

suvasish pal This is correct !!

Answer 5

Let page size  = 2^p   bytes (p is page offset )

now, number of page entries in 1st level = 2^p / 4 = 2^p-2 bytes (as it uses 32 bit = 4 byte Physical address) 

Similarly in 2nd level -> 2^2(p-2) and considering 3rd level it would be 2^3(p-2) 

so, 2^3(p-2) * 2^p = 46, p=13 

so page size = 2¹³ byte = 8KB (c)

Number of pages in cache = 1MB/8KB = 128 pages 

Number of set in cache = 128/16 = 8 

For any two synonym to map with same set they should be colored with

same color of that respective set. So minimum we need 8 colors for this mapping. (C)

Comments

"32–bit physical address"
if this is "16-bit" what would be the answer for pagesize? 
 

---

A couple of questions..
1. "4 byte physical address" or 4 B PTE? 
2. What does this mean? 2^3(p-2) * 2^p = 46
3. "No. of set in cache" or No. of set per page? 

4. 128/16 not clear.. can you please explain this? 
 

---

@Shree :Could you please elaborate the concept of these color bits needed ?? And  also explain how did you solve this .Solution you provided is a bit tricky to understand  .

Please explain .

Thank You

Answer 6

We know from the question that a page table can retain in a single page.

Assume size of page is 2^x .

No. of entries that can be cotained in a page is 2^x/4 that is 2^x-2. So at a particular level no. of entries can be addressable in x-2 bits.

So,

We can consider bit distribution of virutal address as bit required for 1^st level + 2^nd level + 3^rd level + page 

That is                       x-2 + x-2 + x-2 + x = 46

Solving this we get x = 13

That is       2¹³ byte size of a page.