YTread Logo
YTread Logo

Virtual Memory: 5 Page Tables

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

virtual

address to physical address mappings and we're going to see in a minute why we call it a

page

table so we saw before that we have this map from the

virtual

addresses to physical addresses we're going to call this the

page

table what we've seen so far is we had one entry or one

page

table entry for every

virtual

address so here we had one entry for address 512 one entry
virtual memory 5 page tables
for 786 and we also had entries for all the words in between these as well so how big is this so if we need one entry in our

page

table for every

virtual

address remember

virtual

addresses are word access how many do we need well we need one for every word so that's 2 to the 30 or 1 billion entries so that means at this table here for a 32-bit program address space has to be able to fit a billion entries in it and each one of these entries is pretty big it has to say what's the

virtual

address in the physical address so it's at least 32 bits so that means this is about one gigabyte of

memory

just to keep track of this

page

table so this doesn't sound very good I mean we'd have to use up a whole gigabyte of

memory

just to keep track of the

memory

for one particular program so how are we going to solve this well let's talk about

page

table size so we need to translate every address of our programs have a 32-bit

virtual

address space and we have to be able to
access everything in it or the programs can't use all their address space so it's 2 to the 30 words that need

page

table entries if we have one entry for every word it's a billion entries that's way 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 actually load the data so we have to have some sort of

page

table entry for every single word in our

virtual

address space so how can we make this more manageable well here's what we had before we had this fine-grain mapping each word was mapped in our table here what we can do is we can have it in bigger chunks so we divide our

memory

into chunks and we're going to call these chunks that's why it's called a

page

table entry instead of words so here's what this looks like with coarse screen so here we have a whole

page

so we're saying that

virtual

address is 0 through 4095 are
virtual memory 5 page tables
going to map to physical addresses or whatever 4096 to 8191 so now instead of having one entry in our

page

table map one word one entry in our

page

table is going to map this whole chunk of

memory

we're going to call this chunk of

memory

a

page

so in this case we have these four kilobyte

page

s so each entry in our

page

table now handles four kilobytes of data before we had each entry in our

page

table handling one word or four bytes of data so this is now each chunk here is a thousand twenty
four times larger than they were here so we need one thousand as many of these entries makes our

page

table much smaller so now we're going to do this coarse screen

page

s instead so our

page

tables

no longer going to manage entries for each word it's going to manage entries for each

page

so we have fewer entries needed to cover the whole address space and here's the example we had for kilobyte

page

s here there's also trade-off its Lex flexible before we could move each word at a
time here we're going to have to move 4096 bytes at a time four kilobytes every time we want to move a

page

so if we need to move something out to disk to make room we're going to have to move out 4096 bytes at a time to make room so today we typically have four kilobyte

page

s that's a thousand 24 words per

page

and here's a question about them how many entries do we need in our

page

table now that we have four kilobyte

page

s for this 32-bit machine well we need one entry for
every thousand 24 words it's a four kilobyte

page

each word is four bytes that's a thousand 24 words per

page

so that's going to be one million entries so this is great instead of needing a billion entries like we did before we just need 1 million this is enormous ly more manageable so before our

page

table was a gigabyte in size now it's some about 4 megabytes in size which is much more reasonable in fact people even go further than this so today you have lots of 64-bit machines
virtual memory 5 page tables
people are getting very common used to megabyte

page

s so in a two megabyte

page

you get five hundred twenty thousand words per

page

this allows you to cover more of

memory

space with a smaller

page

table so there's a trade-off here cover more

memory

space with a smaller

page

table but you have to move a whole

page

at a time so you get less flexibility now how do we map addresses within a

page

so before this was really easy you just looked up the word address in your

page

table and it told
you what the physical address now our

page

table tells us that all the addresses in this range map to this range so how do we look something up so to do this we think about a

virtual

address space in our physical address space in

page

s so here are the

page

s here's the first

page

in our

virtual

address space it's address 0 2 4095 the second

page

a third

page

the fourth

page

etc the same thing for a physical address space we have

page

s now in this example our physical address space is
smaller than our

virtual

address space so it has fewer

page

s now we want to go ahead and see how this translation works so as translation tells us that at

virtual

address is 0 to 4095 so that's addresses in this

page

our translated physical address is 4096 to 8191 so that's saying that this

page

is translated over here to this

page

so instead of pointing to individual words we're just saying this whole

page

gets translated this whole

page

now that's fine but here's a question
what's the physical address for

virtual

address for that well the map doesn't have an entry for fort just has a map for this range so how do we translate that well the answer it's going to be 4,100 so all of the

virtual

addresses in this range are going to be mapped into this physical

page

here so address 4 over here is offset by 4 bytes from the start of this

page

so we can figure out where this

page

maps it maps over here and then we know that this word is going to be offset by 4
bytes over here in this physical

page

so it's going to be 4 bytes off from address 4096 so it's going to be address 4,100