Virtual Memory (a somewhat long complete -- I hope -- picture)

A student writes:

	Hello Dr. Patt

	I am very confused about the diagrams corresponding 
	to the 2-level virtual address. 

I understand.  It is very clear that I went over it too fast.
So, we will go over it carefully tomorrow at the review session.
Meanwhile, let me see if I can do better in this email.  Although,
to do it completely could get pretty long.

	Is this the correct sequence of events of going from a VA of a
	page to the PA of the frame that that page is mapped to?

	   1. Get virtual address of page x

Indeed, step 1.

	   2. Go to PTE in virtual memory the describes page x

Nope, you can not read virtual memory.  BUT, you do know where in virtual
memory that PTE is.  So, in order to get the PTE of the page containing
x, you need a strategy.  And, that strategy is what we are after.

So, rather than have me try to read what is confusing for you to write, 
let me try again.  Let's take the VAX example.  It is somewhat cleaner.

1. Let's start this time with system space.  The VAX provides 1 GB of system
virtual memory (all locations whose 32-bit virtual address starts with 10).
We cannot store the entire o/s in physical memory at one time.  At least not
in Cameron's laptop.  He only has 512 MB, and he needs at least a few memory
locations for the application he wishes to run.  So, we only store at any one 
time only those pages of system virtual space that we need to work on the job 
at hand.  The rest we leave on the disk.

2. We need a page table for the system virtual space.  Pages on the VAX are
2^9 bytes, so we have 2^21 pages in system virtual space.  That means 2^21
PTEs.  Do you understand why?  Each PTE is 4 bytes wide.  Thus the system
page table (from now on, SPT) uses up 8 MB of physical memory.  No problem
for Cameron, he has 512 MB, so he still has 504 MB left to do useful work.

3. If I want to find the value of x and I have its VA, and its VA starts with 
10, I can find its PA by using the SPT which is in physical memory.  For 
example, if I have a virtual address as shown here:

	| 10  |  page number in system space (call it Q)  | byte_on_page |

The "10" tells me to look up the PTE in the SPT.  The PTE is at physical
address SBR + 4xQ.  How do I know that?

Answer: SBR is the base address of the SPT which is in physical memory.
That is, SBR is a PHYSICAL address.  Q is the page number.  4 is the
number of bytes in a PTE.  SBR + 4xQ is the straightforward way to index
into a sequentially stored array.

I go to that address and voila!  The PTE for page Q of system space.  If the
valid bit is set (the page is resident), I get the physical address of x by 
going to the frame specified by the PFN of the PTE and going to the 
byte_on_page specified by the VA of x.  That is, the physical address of x 
is the PFN concatenated with the byte_on_page bits of the VA.

So, we now know how to find stuff that is in system virtual memory by using the
system page table which is in physical memory.

What about finding stuff that is in process virtual memory.  Let's look at 
one process, and one VA in that process' Program virtual memory (P0 virtual
space). Let's call it the VA of y, and let's say it is on page R.

  VA of y | 00  |  page number in system space (call it R)  | byte_on_page |

To find y, we need the PTE of page R  If we were in system space (#3 above), 
we simply go to the SPT.  Why not in this case go to the P0PT?  We could IF 
the P0PT were in physical memory.  But do we really want to waste 8MB of 
physical memory for every page table of every process?

How about if we put the process page table (P0PT) not in physical memory, but 
in system virtual memory, where there is plenty of room.  We can still get the 
PTE of page R, but in order to do it, we need to first find the frame of 
physical memory that contains the PTE of page R.

Step 1: We take the VA of y.  Its high two bits are 00, indicating PO Virtual
memory.  The page number of VA (call it R) allows us to figure out where in 
system virtual memory its PTE is.  Answer: P0BR + 4xR.  That is a VA.  It is
the virtual address of the PTE of page R, the page that contains y.

Step 2: We look at the VA of the PTE of page R.

      VA  | 10  |  page number in system space (call it S)  | byte_on_page |

The PTE of page R is in page S of system space.

But we saw in #3 above, that the SPT can tell us where in physical memory
page S is.  

Step 3: SBR + 4xS is the physical address of the PTE of page S of system
space.  That PTE provides the PFN of that page of system space that contains
the PTE of page R. So, that PFN concatenated with the byte_on_page will get 
us the physical address of the PTE of page R.

Step 4: We can now look at the PTE of page R.  The PFN of that PTE specifies
the frame that holds page R, and the byte_on_page of the VA of y gives the
exact location in that frame that contains y.

Does that help?  If not, as I said, we will go over it at the review session
if anyone wants me to.

Yale Patt

	   3. "Zoom out" treating the PTEs as pages themselves and find the PTE
	       for them in physical memory in System Space
	   4. Use the PTE in physical memory to tell you information about
	      the PTE in virtual memory (this is the PTE that we zoomed out
	      from and treated as a a page). The information that you should get
	      is in the page of PTEs that's in VM, which one do you care about.
	   5. This leads you back to VM but this time you know specifically the PTE
	      that you need to find.
	   6. That PTE should point you the frame you were searching for
	      in Physical Memory, in other words it should give you PA.

	I know this might be confusing to read since it was confusing for me to
	write but please tell me the correct sequence and if what I said is
	correct then elaborate on it if possible.

	Thank you
	<<name withheld to protect ...>>