CREATE OWN LIBRARY

Multi-level Paging: Important Example 1

Question:

Consider a system using a multi-level paging scheme. The page size is 32 KB. The memory is byte-addressable and the virtual address is 48 bits long. The page table entry size is 4 bytes.

How many levels of page table will require?

(a) 1

(b) 2

(c) 3 

(d) 4

Solution:

Logical Address = 48 bit, page size = 32KB = ${\mathbf{2}}^{\mathbf{15}}$ and page table entry= 4 byte = ${\mathbf{2}}^{\mathbf{2}}$

So, Logical Address Space = ${\mathbf{2}}^{\mathbf{48}}$ and as we know frame size = page size = 32KB = ${\mathbf{2}}^{\mathbf{15}}$

Now, 

# But frame size 32KB, so, we cannot keep this page table in one single frame.

So, we have to divide this table into father pages and create another page table.

Now, this page table1(PT1) and the number of pages by which we can divide the page table is

Number of pages at PT1 =

Now, check this second page table fit in a single frame or not.

Size of Page Table2 (PT2) =

# But frame size = 32KB = ${\mathbf{2}}^{\mathbf{15}}$, so, we cannot also keep PT2 in one single frame.

Now, we also divide the PT2 into pages and create another page table which is Page Table3 (PT3) which has the same number of entries. 

So, Number of pages at PT2 = 

Size of Page Table3 (PT3) =

Now this Page Table3 (PT3) can keep in a single frame because frame size= 32KB = ${\mathbf{2}}^{\mathbf{15}}$ is bigger than PT3 size. 

So, 3 levels of page table will require in this system.

So, option (c) is correct.

Now because it is 3 levels of paging so, the address divided into 4 parts.

To calculate the number bit for PT1 and PT2, we have to calculate the number of entries possible on each page at PT1 and PT2.

So, the number of entries is the same for PT1 and PT2 both have the same procedure to calculate.

Now, PT3 contains the number of entries for PT2. 

So, the number of bits required for PT3 = 7 bit