Dark Mode

30,837 views

94 votes

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?

- $2$
- $4$
- $8$
- $16$

0

0

Other way of approaching this question:

https://www.geeksforgeeks.org/operating-systems-memory-management-question-9/

1

170 votes

Best answer

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$

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$

0

166 votes

I already put it as comment, in case if one skipped it.

One other method to find page size-

We know that all levels page tables must be completely full except outermost, the outermost page table may occupy whole page or less. But in question, it is given that Outermost page table occupies whole page.

Now let page size is $2^p$^{ }Bytes.

Given that PTE = 32 bits = 4 Bytes $= 2^2$^{ }Bytes.

Number of entries in any page of any pagetable =page size/PTE $=\frac{2^p}{2^2} = 2^{p-2}.$

Therefore Logical address split is

p-2 | p-2 | p-2 | p |

logical address space is $46$ bits as given. Hence. equation becomes,

$(p-2)+(p-2)+(p-2)+p = 46$

$⇒p=13.$

Therefore, page size is $2^{13}$^{ }Bytes = **8KB**.

why the PTE entry size for each of the page table same ?

My understanding:

As the inner page table (like T1 and T2) entry in each page table is used to store the base address of the page table in the next level.And the page tables are stored inside the frame in the physical memory.So each entry stores the physical frame address.Now the outer page table(T3) entry also stores the physical frame address.So logically the size of the page table entry(PTE) should be same in all the page tables.

Am I right ?

My understanding:

As the inner page table (like T1 and T2) entry in each page table is used to store the base address of the page table in the next level.And the page tables are stored inside the frame in the physical memory.So each entry stores the physical frame address.Now the outer page table(T3) entry also stores the physical frame address.So logically the size of the page table entry(PTE) should be same in all the page tables.

Am I right ?

0

As the inner page table (like T1 and T2) entry in each page table is used to store the base address of the page table in the next level.And the page tables are stored inside the frame in the physical memory.So each entry stores the physical frame address.Now the outer page table(T3) entry also stores the physical frame address.So logically the size of the page table entry(PTE) should be same in all the page tables.

0

19 votes

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

5 votes

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^{4} /64

2^{46} = P^{4} /64

P = 2^{13} B

= 8KB