Virtual Memory: 5 Page Tables

now we're going to talk about

page

tables

and the

page

table is the mapping that keeps track of these mappings from

virtual

addresses to physical addresses and we'll see in a minute why we call it a page table, as we saw before. We have this map from

virtual

addresses to physical addresses. We'll call it a page table. What we've seen so far is that we had an entry or a page table entry for each virtual address, so here we had an entry for the address. 512 an entry for 786 and we also had entries for all the words in between, so how big is this?

If we need an entry in our page table for each virtual address, remember that virtual addresses are access words, how many do we need? We need one for each word, so that's 2 out of 30 or a billion entries, which means that in this table here, for a 32-bit program, the address space has to be able to hold a billion entries and each of these entries is beautiful. big, it has to say what the virtual address is in the physical address, so it's at least 32 bits, which means it's about a gigabyte of

memory

just to keep track of this page table, so this doesn't sounds really good.

I mean, we have to use a whole gigabyte of

memory

just to keep track of the memory of a particular program, so how are we going to solve this? Well, let's talk about the size of the page table, so we need to translate each address of our programs to 32 bits. virtual address space and we have to be able to access everything in it or programs can't use all of its address space, so it's 2 out of every 30 words that need entries in the page table, if we have one entry per Every word is a billion entries. too many entries now remember if we don't have a page table entry then we can't access that location we need the page table entry to get the physical address so we can load the data so we have to have some type page table entry for each word in our virtual address space, so how can we make this more manageable?

This is what we had before we had this detailed mapping. Each word was mapped to our table. Here what we can do is have it. into larger chunks so we divide our memory into chunks and we're going to call these chunks that's why it's called page table entry instead of words this is what this looks like with a thick screen so here we have a full page, so we're saying the virtual address is 0 to 4095, it's going to map to physical addresses or whatever 4096 to 8191, so now instead of having an entry in our page table, it's going to map one word, one entry in our page table will allocate this entire chunk of memory.

We're going to call this chunk of memory a page, so in this case we have these four kilobyte pages, so each entry in our page table now handles four kilobytes of data before each entry in our page table handled one word or four bytes of data, so now each chunk here is one thousand twenty-four times larger than they were here, so we need a thousand, since many of these entries make our page table much smaller, so now we are going to make these thick screen pages so that our page

tables

will no longer manage entries for each word, they will manage entries for each page, so we need less entries to cover the entire address space and this is the example we had for kilobyte pages.

Here there is also a compensation of your flexible Lex before. we could move each word at a time here we are going to have to move 4096 bytes at a time, four kilobytes each time we want to move a page, so if we need to move something to disk to make space, we are going to We have to move 4096 bytes to the time to make room, so today we typically have four kilobyte pages, which is 1,024 words per page and here's a question about how many entries we need in our page table now that we have four kilobyte pages. for this 32 bit machine, we need one entry for every thousand 24 words, that's a four kilobyte page, each word has four bytes, that's one thousand 24 words per page, so it's going to be a million entries, so this is great instead of needing a billion. entries like we did before, we only need 1 million, this is enormously more manageable, so before our page table was a gigabyte in size, it is now about 4 megabytes in size, which is much more reasonable, so In fact, people even go further, so today I have a lot of 64-bit machines and people are getting very used to megabyte pages, so on a two megabyte page you get five hundred and twenty thousand words per page, which which allows you to cover more memory space with a smaller page table, so there is a tradeoff. here it covers more memory space with a smaller page table, but you have to move an entire page at a time for less flexibility.

Now, how do we assign addresses within a page? Before this was really easy, you just looked up the word address in its page table and it told you what the physical address is. Now our page table tells us that all addresses in this range map to this range, so how do we look up something? To do this, we think of a virtual address space at our physical address. space in pages so here are the pages here is the first page in our virtual address space is address 0 2 4095 the second page a third page the fourth page etc. same for a physical address space now we have pages in this example our physical address space is smaller than our virtual address space so it has fewer pages.

Now we want to go ahead and see how this translation works, since the translation tells us that the virtual address is 0 to 4095, so the addresses on this page, our translated physical address is 4096. to 8191, that means this page is translated here to this page, so instead of pointing out individual words, we just say that this entire page is translated, okay, but here's a question: what is the physical address for the virtual address? Well the map doesn't have an entry for Fort it only has a map for this range so how do we translate it? Well, the answer will be 4,100, so all virtual addresses in this range will be assigned to this physical. page here, so address 4 here is offset by 4 bytes from the start of this page, so we can determine where this page is allocated and then we know that this word will be offset by 4 bytes here on this physical page, so which will be 4 bytes from address 4096, so it will be address 4,100