GATE Overflow Test Series | Operating Systems | Test 2 | Question: 19

Question

A computer uses $\text{42-bit}$ virtual address, $\text{32-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 $(T_1)$, which occupies exactly one page. Each entry of $T_1$ stores the base address of a page of the second-level table $(T_2)$. Each entry of $T_2$ stores the base address of a page of the third-level table $(T_3).$ Each entry of $T_3$ stores a page table entry $(PTE).$ The $PTE$ is $\text{32 bits}$ in size.
The size of a page in $\text{KB}$ in this computer is ________

Answer 1

A computer uses virtual address of 42 bits. Let page size bits be x. Hence Page size is $2^{_{x}}$B

THIRD LEVEL

Number of page table entries in last page table = $2^{_{42-x}}$

Page table size of Last level page table = $2^{_{42-x}}$ * 4B

Number of pages required to fit last level page table = Page table size of Last level page table/page size =

$2^{_{42-x}}$ * 4B/$2^{_{x}}$B = $2^{_{44-2x}}$

SECOND LEVEL

Number of page table entries in second level page table = Number of pages required to fit last level page table = $2^{_{44-2x}}$

Page table size of second level page table = $2^{_{44-2x}}$ * 4B

Number of pages required to fit last level page table = $2^{_{44-2x}}$ * 4B/$2^{_{x}}$B = $2^{_{46-3x}}$

FIRST LEVEL

Number of page table entries in first level page table = Number of pages required to fit second level page table = $2^{_{46-3x}}$

Page table size of First level page table = $2^{_{46-3x}}$ * 4B (This must fit in exactly one page).

So, $2^{_{46-3x}}$ * 4B = $2^{_{x}}$B

      $2^{_{48-3x}}$ = $2^{_{x}}$

solving for x gives x = 12

Page size = $2^{_{x}}$B = $2^{_{12}}$B = 4KB

Answer 2

The $\text{42-bit}$ virtual address is split among the indexing bits for the $3$ level page tables $+$ the page offset.

Since the $3$ levels of page tables occupy a page size (first level page table occupies a page and the pages of second/third level tables also assumed to be of page size), the offset bits should be the same for them (in multiples of $4\:\text{bytes}$ which is the PTE size) where as the offset bits for page frame is in bytes $\text{(2 extra bits)}.$

Thus, if $x$ is the number of indexing bits for a page table, we get $\underbrace{x}_{\text{First level}} +\underbrace{x}_{\text{Second level}} + \underbrace{x}_{\text{Third level}} + \underbrace{x+2}_{\text{Page frame}} = 42$

$\implies x = 10.$

So, number of offset bits in a page $ = x+2 = 12.$

So, size of  page $ = 2^{12} = 4\:\text{KB}.$

Comments

How is it assumed that level 2 & level 3 page tables will also occupy one page?

---

@Kshitij.twr

My guess is that after all page table has to fit in one frame(frame size = page size), then it should be safe to assume page table size as one page size, unless specified. If it doesn’t fit in one frame then again paging needs to be done on that which is already done.