GATE CSE 2009 | Question: 34

Question

A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because

• A. It reduces the memory access time to read or write a memory location.

• B. It helps to reduce the size of page table needed to implement the virtual address space of a process

• C. It is required by the translation lookaside buffer.

• D. It helps to reduce the number of page faults in page replacement algorithms.

Comments

Page table structure does not directly affect page faults.
 

Page faults depend on how pages are allocated and accessed, which is governed by Replacement algorithms (FIFO, LRU, etc.), not the number of levels in the page table.

---

The correct option is B. It helps to reduce the size of page table needed to implement the virtual address space of a process
 

 

---

References : Galvin 

Ans : Option B 

Answer 1

Option - > (B)

• A. It reduces the memory access time to read or write a memory location. -> No This is false. Actually because of multi level paging we increase no of memory accesses.

• B. It helps to reduce the size of page table needed to implement the virtual address space of a process -> This is true, In case of big virtual memory , size of single level page table will be more compared to size of multilevel page table . 

• C. It is required by the translation lookaside buffer.-> Examiner was not being enough creative here, This is false & There is no relation. This option is just given for no reason !

• D. It helps to reduce the number of page faults in page replacement algorithms.-> This is false, we might increase no of page faults. (Due to second / third level page not in memory here !) So this is false.

Comments

@Psy Duck For which option, are you talking about?

---

@ayush_27 option 2

---

Awesome explanation !!

Answer 2

B.

Which is a clear reason why we perform paging.

When the page table size increases we perform paging on the page table. Resulting in multi-level page table.

Comments

See this question to see how drastically two level paging reduces size. Only 16KB. In multi-level paging, we do have entries for pages that are actually being used.

If we use Flat page table (Single page table) then we would need $2^{20} \times 4 = 4$MB of page table size. but after two paging only $16$KB would suffice.

Answer 3

A.   This is false.  Because in multi level paging we increase number of memory accesses depending upon number of levels of Page tables. Since to access each level you need 1 memory access.

---

B. This is true, In case of most of the programs most of the space is empty and they only utilize a small portion of the memory that is reserved in Main memory which causes lots of invalid entries in Page Table which in-turn increase the Page Table Size.

Lets Take an Example-

Consider,

Page Size = 4 KB.

PTE = 8 Bytes,

VAS = $2^{^{32}}$Bytes.

Then Size of Page Table = 8MB.

If a process only need Lets say, 20 Pages in Main memory then Only 20 entries are valid in Page Table equivalent to 20*8 = 160 Bytes. Rest all the space is invalid. Idea of Multi Level Paging is to not store these invalid entries (or at least reduce) and hence more levels are made which points to each chunk in the default Page table(page table directly pointing to main memory) and only stores the valid chunks in the main memory .

Then total space in the main memory = Size of second level page table + Size of valid chunks(chunks containing valid entries) in default page table . This reduces a lot space. Similarly More levels can be introduced to further reduce space. Trade-off is access time and Page Faults.

NOTE: MULTILEVEL PAGING IS NOT FORCED. WE HAVE NO NEED TO FIT PAGE TABLE IN ONE PAGE, WE CAN SIMPLY OCCUPY MORE PAGES. 

---

C. This is false since there is no relation of TLB with MLP. 

---

D. This is false, since more lower level pages will cause more page faults due to absence of more and more Default Page table entries which program might need further(as stack and heap size grows).

 

---

If you liked the answer, Please Drop a  ⬆ UPVOTE

Answer 4

(A) In multi level page table we have to go through multiple page tables instead of only one in single level page table. So it actually increases the memory access time. This is False.

(B) In multi level paging we can avoid saving invalid or unused entries in the respectively lower levels and the physical memory itself but in case of single level paging we do not have any other option than storing all the entries. This is True

(C) This option is unrelated and False.

(D) This may increase the number of page faults because of the absence of higher level pages are not in the memory.

Answer 5

In a single-level page table, there is one entry for every virtual page. Therefore, for a large virtual address space, the page table can become very large. Moreover, the complete page table has to be allocated even if large portions of the virtual address space are unused.

In multilevel paging, the page table is divided into multiple levels. The lower-level page tables are created only for those portions of the virtual address space that are actually required. Therefore, page-table entries for unused or unallocated portions do not need to be stored.

For example, if a process uses only a small portion of a very large virtual address space, multilevel paging can avoid allocating page-table structures for the unused portions. Hence, the actual memory required for the page tables can be significantly reduced.

Therefore, option (B) is correct: multilevel paging helps reduce the size of the page table needed to implement the virtual address space of a process.

Answer 6

Correct Answer Option B Because,....

EXAMPLE : 

Q) A proess having 32 bit VAS and a page size of 4KB and using only 2^16 Bytes 

1)with single level paging:

then with a single level paging the size of page table will be 2^20*2^2=4MB 

2)with multilevel paging:

if we use multilevel paging the size of the page table can be reduced to 8KB (since,the pages are stored from address 0 i.e together at one place )

VAS :

10

10

12

No of pages in the process = 2^20 pages

No,, of useful pages = 2^16/2^12 = 2^4 = 16 pages 

so,at first level page table only 16 entries are useful

all these can be grouped to one chunk of size 2^10 entries in first level PT

so, at second level page table the no,, of useful entries will be only one 

since,we are dealing with chunks...

i.e 1*2^10+1*2^10 = 8KB

Here we can clearly see that the multilvel paging reducing the size of page table as compared to single level paging right.

so,multilevel paging always helps to reduce the size of page table needed to implement the virtual address space of a process is true but, it doesn't mean that multilevel paging is forced to reduce the size of page table we can stop at any level i.e,it is a big misconception that  if the page table size is 4MB and page size is 4KB that's why we use multilevel paging to fit that page table in the availble page space.why we even want to fit in one page we can span over the other pages and even if the size of the page table is fit enough with the page size we can still use multilevel paging to reduce the page table size and to save memory.here everything is our choice i.e we have divided the VAS in to 10 | 10 | 12 but if we want we can leave it without dividing further 20 | 12 .although the process size is too small and page table size is too big we are just trying to reduce size of page table and store with few memory.