Question on Operating Systems

[sdaccord01]

Hi, I'm doing my CS homework for the summer and I am stuck on this one problem and am wondering if anyone can help me. Here's the problem:

"Assuming a page size of 4Kbytes and that a page table entry takes 4 bytes, how many levels of page tables would be required to map a 64-bit address space, if the top level page table fits into a single page?"

I do not know how to approach this problem, and the textbook shows and example on a 32-bit virtual address but doesn't go about showing how to go about finding how many levels needed. Any assistance would be much appreciated.

Ken

 

[kranky]

Don't know if this helps, but it sounds like it might. Found it in this PDF.

Consider a system in which the virtual address space is 64 bits, the page size is 4KB, and the amount of
physical memory is 512MB. How much space would a simple single-level page table take? Such a table
contains one entry per virtual page, or 2^(64?12) = 252 entries. Each entry would require about 4 bytes, so the total page table size is 2^54 bytes, or 16 petabytes (peta- > tera- > giga-)! And this is for each process!

Of course, a process is unlikely to use all 64 bits of address space, so how about using multilevel page
tables? How many levels would be required to ensure that each page table require only a single page?
Assuming an entry takes a constant 4 bytes of space, each page table can store 1024 entries, or 10 bits of address space. Thus [52/10] = 6 levels are required. But this results in 6 memory accesses for each address translation!

But notice that there are only 512MB of memory in the system, or 2^(29?12) = 2^17 = 128K physical pages. If we can somehow manage to store only a single page table entry per physical page, the page table size decreases considerably, to 2MB assuming each entry takes 16 bytes. And since processes share physical memory, we need only have a single global page table. This is the concept of an inverted page table.

 

[sdaccord01]

wow, thank your your reply. I really appreciate your fast response. My textbook is bad and never explained how to do multilevel page tables

 

[Tab]

Wow, that is so over my head...