FOR FREE YEAR SOLVED

Multi Level Paging 

Let start this concept with a GATE previous year question

Question: GATE 2003

In a system with 32-bit virtual addresses and 1 KB page size, the use of one-level page tables for virtual to physical address translation is not practical because of

(a) The large amount of internal fragmentation.

(b) The large amount of external fragmentation.

(c) The large memory overhead in maintaining page tables.

(d) The large computation overhead in the translation process.

Solution:

Logical Address = Virtual Addresses = 32 bit and page size = 1KB.

If page size = 1KB = ${\mathbf{2}}^{\mathbf{10}}$, so offset = 10 

Now, number of bits in page number = Logical address – offset = 32 – 10 = 22

So, number of pages in process or Logical Address Space = ${\mathbf{2}}^{\mathbf{22}}$

This is a high number of pages it is difficult to maintain in memory.

So, option (c) is correct.

Let elaborate the problem of large number of pages

Here page size = 1KB = ${\mathbf{2}}^{\mathbf{10}}$ is given and as we know page size and frame size are always the same.

So, we can say page size = frame size = ${\mathbf{2}}^{\mathbf{10}}$ = 1KB.

Let assume page table entry = 4B = ${\mathbf{2}}^{\mathbf{2}}$ and the number of pages already calculate is ${\mathbf{2}}^{\mathbf{22}}$

So, Page Table Size (PTS) 

And we know page tables also reside within a frame of the main memory. 

Now, frame size = ${\mathbf{2}}^{\mathbf{10}}$ = 1KB  and Page Table Size (PTS) = ${\mathbf{2}}^{\mathbf{24}}$ = 16 MB

So, in that case, how can we fit a page table into a frame of main memory?

But load the page table into memory is very important otherwise paging is not possible. 

So, when a page table size is bigger than a frame size of memory, we cannot load this page table into a single frame. Then we must divide the page table exactly like the process and load it into frames.

Now, this page table is divided into some pages and it will be required another page table to maintain newly divided pages. This concept is called multi paging.

Now, first we have calculated by how many pages system can divide the page table.

As we know total Page Table Size (PTS) = ${\mathbf{2}}^{\mathbf{24}}$ B (Calculated above) and page size = 1KB = ${\mathbf{2}}^{\mathbf{10}}$.

Then the system can divide the page table into ${\mathbf{2}}^{\mathbf{14}}$ pages.

Here ${\mathbf{2}}^{\mathbf{22}}$ is the total number of pages in the page table (Because the process is divided into ${\mathbf{2}}^{\mathbf{22}}$ pages) but to fit this page table in a frame of main memory we father divide this ${\mathbf{2}}^{\mathbf{22}}$ pages into ${\mathbf{2}}^{\mathbf{14}}$ pages into this page table.

Now we can say this page table has ${\mathbf{2}}^{\mathbf{22}}$ entries and ${\mathbf{2}}^{\mathbf{14}}$ pages.

So, as we know we need another page table to maintain these ${\mathbf{2}}^{\mathbf{14}}$ pages of page table1, and the number of entries possible in this page table2 is ${\mathbf{2}}^{\mathbf{14}}$ because it contains all page number of ${\mathbf{2}}^{\mathbf{14}}$ pages of page table1.

In above we already assume page entry = 4B = ${\mathbf{2}}^{\mathbf{2}}$.

As we know page table1 has ${\mathbf{2}}^{\mathbf{22}}$ entries and ${\mathbf{2}}^{\mathbf{14}}$ pages.

Now how many entries contain each page:

We know, 

Translation of Logical Address to Physical Address:

We know CPU generates the logical address of 32bit because Logical Address Space (LAS) = ${\mathbf{2}}^{\mathbf{32}}$ = 4 GB.

So, here in the case of multi-level paging which is here two levels paging, it is divided into three parts:

# MSB 14 bit identify page number of Page Table1 (PT1) which is kept in Page Table2 (PT2) and we know 14 bit because the number of entries at PT2 is ${\mathbf{2}}^{\mathbf{14}}$ B.

# Now as we calculated earlier the number of entries possible in one page of Page Table1 (PT1) ${\mathbf{2}}^{\mathbf{8}}$B = 256B.

So, to identify a particular entry of an identified page, requires 8 bit, because the total number of entries on a page is ${\mathbf{2}}^{\mathbf{8}}$.

# Now after reach a particular entry in a selected page of Page Table1 (PT1) and this entry contains the frame number of the main memory. 

So, the system gets the frame number of the main memory, and using offset it can get the exact data that the CPU requests for.

Because address translation works from the outer page table inward, this scheme is also known as a forward-mapped page table.

Now, it is cleared that 2 level paging requires the logical address divided into 3 parts.

Same way 3 level paging requires the logical address divided into 4 parts.

And n level paging requires the logical address divided into n + 1 parts.

Advantage and Disadvantage Multi-Level Paging: 

Memory requirements are less compare to single-level paging technique address translation processing time is high due to more number of page table levels.

This problem can be solved by Translation Look aside Buffer (TLB).