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

 

[Nothinman]

I'm thinking this is a trick question. AFAIK the max page table levels any system uses is 3 and I believe 2 is the most common case for performance reasons. Whether the system is 64-bit or 32-bit isn't terribly relevant because in both cases almost all of the address space goes unused for normal processes. If your professor really wants you to tell him how much memory it would take to allocate page tables for a full 64-bit space, just do the math.

http://www.cs.purdue.edu/homes/cs354/LectureNotes/Fall2002/week14-1/

 

[Sianath]

Currently, Windows works as follows (32-bit):

CR3 register contains the physical address of the Page Directory for a given process
The Page Directory holds 1024 Page Directory Entries (PDE's), 4 bytes each (32-bit address)
Each PDE points to the address of a Page Table
Each Page Table holds 1024 Page Table Entries (PTE's), 4 bytes each (32-bit address)
Each Page Table Entry contains the physical address of a Page in memory

Notice that it works out that the Page Directory and each Page Table take up 4K? That's so that they fit exactly on one page. Sneaky eh?

This gives you the full 32-bit address space of 4 GB
- 1024 PTE's * 1024 PDE's * 4K each page = 4,294,967,296 bytes

The breakdown is as follows for any virtual memory address:

High 10 bits = index into the page directory (which PDE)
Next 10 bits = index into the page table (which PTE)
Low 12 bits = offset into the page

Now, expand this to address the 64-bit address space.

Dont' worry about the /3GB switch right now... just know that it changes the Virtual Address layout to include an index into a list of PD's... it adds another layer.