Paging - Memory management

Question

Why do we need multilevel paging?

According to me the reason is that page table needs contiguous memory allocation.So if page table size is too large, we may not be able to store the table in contiguous memory.

So is this the reason behind multilevel paging?

Also when we page the page table, do we store all levels page table in memory or only the outer level page table?

Comments

go through the concept one more time, what you understood is wrong !

---

I will be very thankful if you could please explain the concept.

---

 Lovejeet Singh

See bro, I will try to explain in some words, see if u could understand it.

Multilevel paging concept is derived from the paging concept, so thought comes how the concept of paging comes, so it has to come because there were some drawbacks in earlier memory management schemes. U have listened about something know as a static partitioning method, in this method we used to divide the memory into some fixed size partitions and drawback of this method was internal and external fragmentation and then later they came with variable partitioning method then in this problem of internal fragmentation was removed but the problem of external fragmentation was there.

This problem of external fragmentation was due to the rule that we had to put the process in a contiguous manner, so they have come up method of paging, here we will divide the process into pages and main memory is divided into frames, we use to put pages into frames  and in this we need not put all the pages of process in memory at same time and we can put some pages at that instant of need.after the invention of paging , some new terms come into picture , like what would be page size, number of pages, number of frames, page table, page table entry etc..

per process, there will be one page table that will be used for cpu to finding which page is sitted in which frame of main memory.Sometimes page table size might be so big that we can not fit it into one frame of main memory, theredore they came up with multilevel indexing(same as indexing in DBMS,)and in this we divide the page table itself into pages.

By this lof of things improved like degree of multiprogramming(we can put lot of process in main memory at same time).This is a big concept if u read by your own.

---

i think the above explanation is best .just i wanted to give you some example suppose page size=4KB(frame size=4KB) and page table size=4MB and the page table is stored in MAIN MEMORY. now the problem is that the page table of such size cant be fit into a frame in the memory(we always takes pages when we have to fit it in a frame in memory).so thatsy the page table of such size is divided into pages and multi level paging comes into play.

Answer 1

From OSTEP,

"Let’s start out with a linear page table. As you might recall1 , linear page tables get pretty big. Assume again a 32-bit address space ($2^{32}$ bytes), with 4 KB ($2^{12}$ byte) pages and a 4-byte page-table entry. An address space thus has roughly one million virtual pages in it ( $2^{32}/ 2^{12}$ ); multiply by the page-table entry size and you see that our page table is 4MB in size. Recall also: we usually have one page table for every process in the system! With a hundred active processes (not uncommon on a modern system), we will be allocating hundreds of megabytes of memory just for page tables!"

Continued:

"The basic idea behind a multi-level page table is simple. First, chop up the page table into page-sized units; then, if an entire page of page-table entries (PTEs) is invalid, don’t allocate that page of the page table at all. To track whether a page of the page table is valid (and if valid, where it is in memory), use a new structure, called the page directory. The page directory thus either can be used to tell you where a page of the page table is, or that the entire page of the page table contains no valid pages"