Resolving Virtual Memory Addresses

Deconstructing a Virtual Memory Address

Consider a virtual address on a 32-bit computer (this means, in part, that the an address is 32 bits).  The number of bytes addressable in such a system is 2^32, or 4 gigabytes. 

The idea is to select a "page size" (the number of bytes that will be retrireved from the execution image of a process in the swap space) and an identically-sized "frame size" (the number of bytes in RAM in which a page will be placed).  The page size should be a power of 2.

Suppose that the page size is 4K bytes. 12 bits will be needed to address each byte in such a page.  So, if one looks at a 32 bit virtual address it will look something like

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0

This virtual address refers to the 10th byte in virtual memory space (1010 is 10 in binary). 

If we now consider the virtual address space to be broken up into 4K-byte page sizes, with page 0 starting at byte 0, we can view the first 20 bytes of a 32 bit address as the page number and the last 12 bytes as the byte offset into that page.  So, taking the address above as an example, we have

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0

where the blue portion represents the page number and the red portion the offset into that page. 

So now, if the OS takes the 4K bytes of page 0 of the process from swap space and places it into a free frame in RAM, say frame 5, the actual RAM address of the byte referred to in the virtual address will be

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0

So, the hardware must be able to resolve the given virtual address to the acutal RAM address. 

How does this work?  The OS must build a table for each process that has an entry for each of the possible pages (there are 2^20 possible pages) in which the ith entry in the table will contain the value of the actual 20 bit address of the frame in RAM where the ith page of the execution image of the process is stored.  In the above example, the 0th entry of the table would hold the 20 bit string ending in 101, indicating that the page 0 of the virtual view of the process is actually in RAM frame 5 (101 in binary).  If the last 12 bits of the virtual address are concatenated to the frame address, we get the actual byte address in RAM that we seek.

Of course, not all virtual pages of a process will generally be in RAM at one time.  Thus, the page table also includes control bits in each entry, maintained by the OS, alongside the frame addresses that indicate whether that entry is valid (whether the virtual page is in RAM or not).

The OS must put in the page table register of the process the address of the page table for that process.

Then the hardware must do the following each time it must resolve a virtual address to a real RAM address.

1. circuits follow the page table register value to the correct page table
2. access the correct entry in that table with the first 20 bits of the virtual address to find the frame address in RAM where that page is located, and
3. concatenate the last 12 bits of the virtual address to the resolved frame address to get the proper byte address inside that frame.

If, in step 2, the circuits discover that the valid bit is not set in that entry of the page table, this indicates that this page is not in RAM.  In this case the circuit must start a "page fault" exception, which

• saves the current PC value,
• sets the supervisor bit in the PS register to supervisor mode
• puts a predetermined value into the PC that is ensured to be the address of the page fault handling routine in the OS

The OS regains control at this point and begins an operation to retrieve the faulting page from the swap space and put it into a selected frame in RAM, also updating the page table entry for that virtual page to hold the selected frame address and setting the valid bit in that entry to "valid." 

The OS can then either restart the process that was tabled by the page fault exception, because the page it faulted on is now in RAM, or it can simply put that page at the end of the ready to run queue and select another process to run.

Page Replacement Strategies

Of course, as the above process repeats over time, there will be pages pages from many processes scattered throughout RAM, and RAM can wind up with no free frames.  When a page fault occurs in this situation and a new page must be brought into RAM from swap space, the OS must have an algorithm for deciding which page do remove from a RAM frame so that the newly retrieved page can be put there.  There are various strategies that can be used.  Among these is one that selects on these criteria

• a page that has not been recently used is a candidate for removal (because it is less likely than others to be needed as a result of the principle of locality).
• a page that which has not been modified while it was in a RAM frame is a candidate for removal (because pages that have been modified from their form in the execution image of the process in swap space must be rewritten to that page in the execution image on swap space if it is to be removed from RAM in order to preserve the changes made to it, whereas pages that have not been modified while they were in RAM can simply be replaced by a newly retrieved page).