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

From @Sachin Mittal 1 comment below

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}×4= 4MB$ of page table size. but after two paging only 16KB would suffice.

---

option (D) is Belady’s Anomaly where increasing page table size may cause more no. of page faults.

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 page, size of Page table can also be too huge to fit in single Page. So we do multi level paging.

• 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

nice explanation @Akash sir

---

Page table need not be page alligned so the exlaination is partly correct only

---

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

---

@ayush_27 option 2

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.