Virtual Memory: 12 Multi-level Page Tables

let's talk a little bit about

page

table size and this is important because we mentioned that, well, we need a million entries for a 32-bit

page

table, which are going to take up a good amount of

memory

, so to a 32 bit machine with 4 kilobyte pages, this is what we have been talking about, by default we need a million entries in the page table, so we find that we have 32 bits, but we have 12 bits of offset page, so we have 20. address bits when translated, so 2 to 20 is a million page entries. We also said that each page table is about four bytes, so we need about 20 bits for the physical page, we need some miscellaneous permission bits and the like, so what works?

Well, it works with 4 megabytes in total, so we need 4 megabytes to store a page table. Okay, that doesn't seem so bad, except that each program needs its own page table. Remember that each program needs its own page table because each program has its own. translation from its own

virtual

address space to the physical address space, so if we have 100 programs running, which is very typical for computers today, we need 400 megabytes of

memory

just for the page

tables

, which is a lot of memory just to keep track of where. those programs have memory and here's the hard part about this: we can't swap the page

tables

on disk so if we don't use them we can't write them out of disk to free up space and the reason for this is if the page table pages is not in RAM, we can't access it, so we can't find it, so there is no way to find the memory for a program if we can't access the page table because we need the page table to do the translation.

So how can we fix this? Remember how we fixed problems with memory in the first place. Remember what

virtual

memory did. So virtual memory was a

level

of indirection that we added and well, we can solve this problem with more IND addressing. Let's take a Look at that, so what we're going to do is we're going to have

multi

-

level

page tables, so we're going to have a first level page table and our first level page table is going to be 4 kilobytes and it's going to have a 1024 page table. . and entries, so it will point to another 1.24 pages, then we will have a second level page table and each of them will have 1.24 entries, so if we need to access something in this part, this is actually , it doesn't point to a memory translation, it will point to another page and this page will be another page of page table entries, so what we are saying is that this page table points to this entire set of page table entries. pages. entry and this one will point to another group and this one will point to another group, so now I have two levels in our hierarchy here, so in memory here we're going to have to store this in memory, so we can take a look at this , what it says is that this first level page table tells me if I need to access any of this data, find where exactly it is in this page table in memory and this is how it is located in memory if I need to access any of this data, it is in this part of the page table out of memory and if I need to access any of this data, it is out of disk, so by having this first and second level, these

multi

level page tables we can start paginating parts of our page table, we no longer have to have them in memory all the time, so second level page tables can be paged because we can always find them.

We can use the first level page table to find. Now the first level page table has to stay in memory because we need to be able to access it in order to find the other page tables. This brings us to the point where we only need to have one of these pages in memory. and another to access the actual program memory, so in multi-level page table, what is the smallest amount of page table data we need to keep in memory for each 32-bit application? We're assuming 4 kilobyte pages here, well, I type I just gave you the answer for this, so it's 4 kilobytes plus 4 kilobytes.

We always need the first level page table because the first level page table allows us to find the second level page tables, but if we really want to do something with the program, we need. Both a first level page table and a second level page table, at least one so we can do a real translation, so we need a 4 kilobyte first level page table and a 4 kilobyte second level page table , so the minimum amount is 4 plus 4 kilobytes. 8 kilobytes per program, which is much better than 4 megabytes per program if we have to keep the entire page table in memory, so here's our memory.

We need to have at least one first level page table and that will point at least. a second level page table and we need both in memory at the same time so we can do any translation. Now let's take a look at how we actually do the translation with a multi page table, so here is our virtual address that we are going to translate, you can see here in memory, we have our first level page table entry and we have some entries of second level page table, let's go ahead and translate them, these are the page offset bits and we know that they just go Now we're going to look at our virtual page number, so here's our virtual page number, but now we will divide it into two parts, one for each level, so we will take the upper parts of the virtual address.

We're going to call this part the one that goes to the first level table, so here are the first 10 bits of our virtual address and we'll use them to look up our first level page table, which tells us that We'll need to get our second level page table at physical address 003, so we go and grab that address, we get our second level page table from memory and remember this can be on disk if it points at that address, we grab the second one. level page table we load it into memory sorry, we access it and now how do we find out which of these pages we really want?

Well, let's take the rest of the bits here to have the rest of the bits. of our virtual page number here another 10 bits these 10 bits are going to tell us oh, we want this entry here now once we have that entry that gives us our translation, then the multi level page table we take the top 10 bits here and we use that to determine which of the entries in our first level page table we want, that tells us where to go for our second level page table and it can also tell if it's on disk, that's what allows us to page the page tables once we have them.

We go to our second level page table and use the next 10 bits of our address to find the particular entry that gives us our translation, so in order for these page tables to look, we have to keep our page table memory top-notch pages at all times. we can find the other pages and we need at least one second level page table in memory at all times to be able to do actual translations because remember it is this table that gives us the translations for the program so how do we use them? our virtual page number we send some of the bits to choose the entry in the first level table and some of the bits to choose the entry in the second level table.

The benefit of this we can now page out parts of the page table so we don't have to keep everything in memory for each program all the time, so here's a question, if I'm running 100 applications on my computer with a page table two level pages, how much memory do I have to keep in RAM at all times to access all the applications to be able to access their data what is the minimum amount I have to keep in memory at all times for their page tables, in this case it is 800 kilobytes so for each application we need a first level page table and at least one second level page table so we can get some translations 100 applications, that is 100 * 8 kilobytes or 8 Kil 800 kilobytes, if we had had to keep the entire page table in memory, this would be 100 * 4 megabytes or 400 megabytes, so we are saving a lot of space by doing this