1. Introduction
When a user program wants to allocate memory, it asks the Operating System (OS) to do that by performing a system call. This way, the OS can properly manage memory among all the running processes.
Beyond that, the OS implements Virtual Memory with the main objective of extending memory size by allowing some parts of it to be temporarily moved into the hard drive.
With this mechanism, a given memory address may not be in the physical memory. The solution for that is to use virtual addresses instead of physical addresses.
2. Virtual Memory
One of the main ideas of virtual memory is paging. It consists of basically splitting memory into pieces with the same size (usually 4KB), called pages:
Notice that, without this division, we would need at least the same amount of memory to map all the physical addresses into virtual addresses. Instead, we can translate virtual to physical addresses of pages, as we will see later.
Information of pages’ addresses and whether they are stored in physical memory or in the hard drive is kept in the Page Table structure.
Each page table entry (PTE) contains the information to indicate where that memory page is placed in the physical memory:
The Page Table also presents some other security information, such as information about the process which owns that memory page — because a process should not write into another process’ memory. But for this article, let’s focus on the physical page information only.
Memory Management Unit (MMU) is the hardware device that manages address translation. This device is part of the CPU. On the other hand, the OS is responsible for moving pages into the hard drive and returning them to RAM. Let us see how they interact during the translation process.
3. Translation Process
Suppose we have a program (let’s say, in the C language) with a simple instruction to assign a value to a memory position, like this:
a = 42;
We ask the OS to run our program, and it handles the execution to the CPU. When the CPU reads this instruction, it asks the MMU for a‘s physical address.
In its turn, MMU reads the address and extracts the part that indicates the number of the page. With this virtual page number, it queries the Translation Lookaside Buffer (TLB) to retrieve the physical page number, which consists of a part of the Page Table cached inside the MMU chip, for a matter of performance optimization.
If the page is not found in TLB, then MMU goes to the original Page Table in memory. With the Page Table entry obtained, MMU can translate the physical address so that the CPU can access that address.
But what if that page is not present in memory? Well, in this case, the MMU raises a page fault exception to be handled by the OS, which retrieves that page from the hard drive. When it happens, the OS uses a page replacement algorithm to determine another page that hasn’t been used recently, and that can be moved out to the hard drive.
Now let us get back to the case when MMU can translate the address and see how the translation is performed.
4. Translation
Recall our example from the last section, where we wanted to assign a value to variable a, and suppose its virtual address is 0x00018004 (that we could see by simply printing &a) in a 32-bit system.
This virtual address is read in two parts: one is the number of the page, which is a pointer to a PTE in the page table, and the other is the offset of the address within that page.
Once we are working with a 4KB page size, then we need 12 bits to address the latest position on a given page. So the offset part consists of the first 12 bits in the virtual address.
The remaining 20 bits (in our 32 bits system) are used to indicate the page number. In this case, we can have up to 1,048,576 possible pages. Our virtual address then looks like this:
When the MMU extracts the page number, it gets the value 0x00018 and seeks this page entry from the TLB. Then it finds out that it translates to physical page number 0x0020.
In this example, the offset part is 0x004, which is concatenated to the physical page number, getting to the physical address 0x0020004. We can see how each part of the virtual address is used to translate to the physical address below:
5. Conclusion
Virtual memory is an important feature that allows systems to extend their memory far beyond physical RAM, and translation between virtual and physical addresses is key for this mechanism. To make it happen efficiently, both hardware (MMU) and software (OS) work together.
The translation itself relies on maintaining a page table to keep track of virtual and physical pages in memory and the offset for each address within the page.
It’s also essential to notice that there may be different types of Page Tables that vary according to how the system implements them. In some cases, the Page Table may be hierarchically organized in directories, and an additional resolution of the page directory may be necessary.