Fig. 4-11, pg. 206, shows the MMU looking up the PT and putting the PA together. The x86 is a little more complicated because it has multiple page tables. Also note that the PT is in memory, not usually physically inside the MMU as might be thought from this picture.
Fig. 4-9, pg. 203, shows the parts in play. Put the PT in the memory box.
The x86 PTE looks like this, as shown in Tan., pg. 818, important bits:
|
Page frame number: bits 12-31 |
|
|
|
|
|
D |
A |
|
|
U |
W |
V |
V: valid bit, same as P, present bit, bit 0
W: writable if 1, bit 1
U: supervisor if 0, user if 1 ßfor user/kernel separation
A: accessed
D: dirty
x86 has page size 4KB = 0x1000 bytes, so an individual page has bytes at offset 0, 1, 2, …, 0xfff
Virtual memory (program image memory) is subdivided into “pages”
Physical memory is subdivided similarly, into “page frames”
Pages/addresses are mapped from VA space to PA space by the MMU
Example: VA = 0x123456 is offset 0x456 on page 0x123
Suppose it maps to PA = 0x6789a456, say, offset 0x456 on page frame 0x6789a
The crucial mapping fact here is the pfn 0x6789a, which is held in a page table (PT).
Page tables have page table entries, PTEs, so that PT[0] = PTE0, etc.
Last time looked at Tan., pg. 204 example of a page table:
PTE0: page 0 -> pfn 2 maps VAs 0K through (4K-1), i.e. A = 0 to A = 0xfff (“normal” addresses are VAs)
PTE1: page 1 -> pfn 1
PTE2: page 2 -> pfn 6
...
PTE6: page 6 -> nothing (not present) ß on x86, V bit = 0 here
Ex. A = VA= 0x2345, is offset 345 on pg. 2, maps to offset 345 on pfn 6, i.e. PA = 0x6345
This happens for each address involved in program execution: PCs, pointers, SPs, etc.
SAPC: has 4M of memory set up for use, i.e., one page table, and paging is turned on. The SAPC’s one page table is at VA 52000 (in the Tutor area.) We’ll use mdd to display 32-bit quantities nicely (md shows low byte first, mdd shows high byte first): The 12 bits of the flags show up as the low 3 hex digits, marked ^^^ here, while the top 5 hex digits provide the pfn.
Tutor> mdd 52000
00052000
00000007
00001007
00002007
00003007
-----^^^ -----^^^
-----^^^ -----^^^
PTE0
PTE1
PTE2
PTE3
This shows that page 0 (VA 0 to VA fff) is mapped to pfn=0 (PA 0 to PA fff), page 1 (VA 1000 to VA 1fff) is mapped to pfn=1 (PA 1000 to PA 1fff), page 2 is mapped to pfn=2, and so on. This is the identity mapping. VA = PA for every address, 0 to 0x3ffffff. Paging is turned on, but memory is being used just as if it wasn’t on.
We can show the A and D bits in action. If we do a read on page 0, for example “md 400”, the A bit will go on in PTE0, and if we do a write in page 0, “ms a00 66”, the D bit will go on. Try it out!
We were looking at the one page table (PT) for the 4M of memory of the SAPC. It is located at VA 52000, in the Tutor area of memory. Recall that we saw that normally for the SAPC, paging is turned on but the mapping is the identity map, so that page 0 of VA space maps to pfn 0, page 1 to pfn 1, and so on. That means that VA = PA for all addresses on the SAPC, that is addresses 0 – 3fffff.
We can easily set up non-identity paging following Tan’s example on p. 204 (first 3 pages):
page 0 -> pfn 2
page 1 -> pfn 1 ßleave this one alone!
page 2 -> pfn 6
Since the PT is at 52000, and each PTE is 4 bytes long, that means PTE0 is at 52000, PTE1 is at 52004, PTE2 at 52008, and so on.
We need to replace PTE0 with a PTE with pfn = 2, and PTE2 with a PTE with pfn=6:
Tutor> ms 52000
00002007
Tutor> ms 52008
00006007
and check—
Tutor> mdd 52000
00052000
00002007 00001007 00006007 ...
-----^^^ -----^^^ -----^^^
pfn
flg
pfn flg
pfn flg
Instruction Example: movl %eax, 0
Operand address = 0, a VA. With the above PT in effect, the MMU would see page 0, offset = 0, access PTE0 and find pfn=2. Thus the MMU would map VA 0 to PA = pfn|offset = 00002|000 = 2000.
Suppose the instruction itself is at address 6a9, also a VA. Then the MMU would reuse PTE0 and map this address to 00002|6a9 = 26a9. The CPU would first do an instruction fetch, sending VA=6a9 to the MMU, which would map it to PA=26a9 and put this address on the bus. The instruction would be fetched into the CPU, decoded, and the operand write to VA=0 would cause VA=0 to be sent to the MMU, where it would be mapped to 26a9 and put on the bus as part of the write cycle.
Page Faults
(an
intro)
What about page 6, with a PTE having P=0, not present? An access to page 6 (addresses 0x6000-6fff) will cause a page fault. The MMU is saying “help! I don’t know what to do, please fill in this pfn!!” The page fault is a trap to the OS. The OS can often determine what should be in that page, say by reading the executable file for another page of code. It finishes by filling in a good pfn and setting P=1. Then it causes the CPU to re-execute the instruction, which succeeds this time because P=1 in the PTE.
Note that most instruction executions don’t cause page faults and proceed without a bit of help from the OS. The OS gets involved only occasionally, when a new page is referenced for the first time (or a system call or interrupt comes along.)
Page faults are crucial to demand paging, the core of virtual memory support. A program image starts out with only a few pages of memory, and page faults notify the OS of the needs of the program. This way, memory is provided “just in time.” This concept is called demand paging.
x86:
Multiple Page Tables are used to cover a
32-bit address space
So far we’ve been looking at one page table handling 4M of VA space, using 1024 PTE’s, each mapping one 4K page. A real system has (up to) a whole 32-bit address space, 4G of memory space. 4M vs. 4G -- that’s a factor of 1K bigger. So it takes 1K = 1024 PT’s to cover the whole 32-bit address space.
These 1024 PTs are managed via a “page directory” of 1024 PDEs, each 4 bytes, and with the same format as PTEs except that the D bit is not in use. The resulting system of a page directory at one level, page tables at the next level, and finally the pages themselves, is called a two-level paging system. See Fig. 4-12, pg. 208 for a diagram. Label the page directory.
For a fully-utilized 32-bit address space, we would be using 1024 PTs plus the PD, 1025 4K pages of MMU overhead memory, or just over 4M of memory. Fine for a 4G program but would be too much for a small process image. Luckily, the V bit in the PDE allows us to mark a whole PT as trivial, so the PTs need only cover the memory in (virtual) use.
A small process image would typically have 3 PTs in use, one for the code+data in the first 4M of VA space, one at the top end of user space for the stack, and one covering the C library DLL area. That’s 3 PTs + PD, or 4 pages of memory overhead, or 16K. Not bad at all.
(The PD is at VA 51000 in the SAPC, in case you want to look at it. Pretty boring though, since it points to only one page table.)
Last time: PTs, PD used to define the mapping VA à PA over a full 32-bit address space.
The PD is located in physical memory by the CPU’s CR3 register.
Each process has a PD, and a process switch just repoints CR3, and bingo, that whole address space becomes current.
Analogy with puppets in boxes.
A process that is not current on a CPU reside in a group of “random” pages in physical memory, but when it is chosen to run, and its saved-CR3 is put in place, that whole address space becomes “mapped in,” suddenly usable for ordinary accesses by the CPU. It is called “mapped in”, as opposed to “copied in” or “loaded”, because only pointers are changed, not contents of any full page.
How does the
page
directory get used in VA to PA mappings?
Each VA (32 bits) can be broken down into 3 bitstrings, the highest 10 bits determining the PDE, and thus the PT, the middle 10 bits determining the PTE within that PT, and thus the page pfn, and the low 12 bits determining the offset within that page. The PA consists of the pfn concatenated with the offset bits.
Example:
VA = 0x12345678 =
00010010001101000101011001111000
**********----------************
PDE 0x48
PTE 0x345 offset 0x678
The MMU would access PDE 0x48 to find the location (PA) of PT 0x48, and in PT 0x48, it would access PTE 0x345 to obtain the pfn for the physical page. It would then put together this pfn and the offset of 0x678 to form the PA.
So what do we get from all this? The individual process images, shown in Fig. 11-23, pg. 813, for Windows 2000. Use of almost all of 2G in the user image, even more in Linux and Solaris.