Figure: Abstract model of Virtual to Physical address mapping
In this model, both virtual and physical memory are divided up into handy sized chunks called pages. These pages are all the same size, they need not be but if they were not the system would be very hard to administer. Linux on Alpha AXP uses 8 Kbyte pages. Each of these pages is given a unique number; the Page Frame Number (PFN). For every instruction in a program, for example to load a register with the contents of a location in memory, the CPU performs a mapping from a virtual address to a physical one. Also, if the instruction itself references memory then a translation is performed for that reference.
The address translation between virtual and physical memory is done by the CPU using page tables which contain all the information that the CPU needs. Typically there is a page table for every process in the system. Figure shows a simple mapping between virtual addresses and physical addresses using page tables for Process X and Process Y. This shows that Process X's virtual PFN 0 is mapped into memory in physical PFN 1 and that Process Y's virtual PFN 1 is mapped into physical PFN 4. Each entry in the theoretical page table contains the following information:
To translate a virtual address into a physical one, the CPU must first work out the addresses virtual PFN and the offset within that virtual page. If you make the page size a power of 2, then this can be easily done by masking and shifting. Looking again at Figures and assuming a page size of 8192 bytes (which is hexadecimal 0x2000) and an address of 0x2194 in Process Y's virtual address space then the CPU would translate that address into offset 0x194 into virtual PFN 1.
The CPU searches the process's page tables are searched for an entry which matches the virtual PFN. This gives us the physical PFN which we are looking for. The CPU then takes that physical PFN and multiplies it by the page size to get the address of the base of that page in physical memory. Finally, the CPU adds in the offset to the instruction or data that it needs. Using the above example again, Process Y's virtual PFN 1 is mapped to physical PFN 4 which starts at 0x8000 (4 x 0x2000). Adding in the 0x194 byte offset gives us a final physical address of 0x8194.
By mapping virtual to physical addresses this way, the virtual memory can be mapped into the system's physical pages in any order. For example, in Figure Process X's virtual PFN 0 is mapped to physical PFN 1 whereas virtual PFN 7 is mapped to physical PFN 0 even though it is higher in virtual memory than virtual PFN 0. This demonstrates an interesting byproduct of virtual memory; the pages of virtual memory do not have to be present in physical memory in any particular order.