Note: there is a figure that goes along with this web page; if you have popups disabled, it didn't appear. Here's a link to it.
In order to give an example of a practical, widely-used, and very nice multilevel paged virtual memory scheme, let's look at how Intel does it.
We'll discuss the following items:
A 32 bit virtual address is divided into a ten bit page table number, a ten bit page number, and a twelve bit offset into a page:
Page Table Number |
Page Number |
Offset |
31-22 | 21-12 | 11-0 |
The "short form" of the translation algorithm is:
Use the page table number to index a directory, getting the address (in physical memory) of a page table. Notice that a process may have 1024 page tables.
Use the page number to index the page table, getting the address in physical memory of the page containing the data. Each page table also has 1024 entries.
Use the offset to index the page, getting the actual data.
In the "long form" of the algorithm, the numbers following correspond to the numbers in the figure in the popup:
PDBR
) in
the CPU tells where the directory starts.
Directory entries and page table entries share a common format:
PFA | Avail | 0 | L | D | A | P C D |
P W T |
U | W | P |
31-12 | 11-9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Bits | Name | Interpretation |
---|---|---|
31-12 | PFA | page frame address |
11-9 | Avail | available to OS |
8 | 0 | must be 0 |
7 | L | PTE -- Must be 0. Dir Entry -- 4MB page |
6 | D | dirty (PTE only -- documented as undefined in directory entry) |
5 | A | accessed |
4 | PCD | page cache disable (can't cache data on this page) |
3 | PWT | page write transparent (tell external cache to use write-through strategy for this page) |
2 | U | user accessible |
1 | W | writeable |
0 | P | present |
Assume the following partial contents of memory for both examples. PDBR contains 001b3000.
Address | Contents |
---|---|
0x0001a038 |
0x000b4045 |
0x000b4b9c |
0x236b12c1 |
0x000b91a0 |
0x1b9d8fc5 |
0x001b31cc |
0x003a9067 |
0x001b3458 |
0x0001a067 |
0x003a9054 |
0x000b9067 |
Example 1: VM address 1cc151a0
Page Table Number: | 0x073 |
Page Number: | 0x015 |
Offset: | 0x1a0 |
PDBR
, the directory starts at
0x001b3000
.
0x001b3000
+
0x1cc
= 0x001b31cc
.
0x003a9067
. Decoding gives us:
Bit(s) | Contains | Means |
---|---|---|
31-12 | 0x003a9 | Page Table
starts at 0x003a9000 |
11-7 | 0x00 | Nothing relevant |
6 | 1 | Nothing in directory |
5 | 1 | Page has been accessed (lately) |
4-3 | 0 | Nothing relevant |
2 | 1 | User accessible |
1 | 1 | Writeable |
0 | 1 | Present |
0x003a9000
) to the offset into the page table
(0x0015
* 4 = 0x0x054
) gives
0x003a9054
as the address of the page table entry.
0x000b9067
. Decoding gives us:
Bit(s) | Contains | Means |
---|---|---|
31-12 | 0x000b9 | Page
starts at 0x000b9000 |
11-7 | 0x00 | Nothing relevant |
6 | 1 | Page is dirty |
5 | 1 | Page has been accessed (lately) |
4-3 | 0 | Nothing relevant |
2 | 1 | User accessible |
1 | 1 | Writeable |
0 | 1 | Present |
0x000b9000
) to the offset (0x1a0
)
tells us the data is at 0x000b91a0
in physical memory.
0x1b9d8fc5
Example 2: VM address 0x4580eb9c
. This one is your's to
figure out.