Virtual memory explained — How Android keeps your apps running smoothly

Galaxy S21 running memory booster app


At the heart of your Android smartphone is the Linux kernel, a modern multitasking operating system. Its job is to manage the computer resources on your phone, including the CPU, GPU, display, storage, network, and so on. It is also responsible for the Random Access Memory (RAM). The apps, the background services, and even Android itself all need access to the RAM. How Linux partitions and allocates that memory is vital to the smooth operation of your smartphone. This is where virtual memory comes in.

What is Virtual Memory?

As a quick refresher, programs (apps) are made up of code and data. The code is loaded into memory when you launch an app. The code starts at a certain point and progresses step by step. The data is then read from storage, retrieved over the network, generated, or a combination of all three. Any location in memory that stores code or data is known by its address. Like a mailing address that uniquely identifies a building, a memory address uniquely identifies a place in RAM.

Virtual memory allocates app data to a space in your phone’s physical RAM.

The problem is that apps don’t know where they are loaded in RAM. So, for example, if the program expects address 12048 to be used as a counter, then it must be that exact address. But the app can be loaded into memory elsewhere and address 12048 can be used by another app.

The solution is to give all apps virtual addresses, starting at 0 and going up to 4 GB (or more in some cases). Then any app can use any address it needs, including 12048. Each app has its own unique but virtual address space and never has to worry about what other apps are doing. These virtual addresses are mapped to actual physical addresses somewhere in RAM. It is the job of the Linux kernel to manage all mapping of the virtual addresses to physical addresses.

Why is virtual memory useful?

Virtual memory is a digital representation of the physical memory implemented so that each app has its own private address space. This means that apps can be managed and run independently of each other, as each app is self-sufficient in memory.

This is the fundamental building block of all multitasking operating systems, including Android. Since the apps run in their own address space, Android can start an app, pause it, switch to another app, run it, and so on. Without virtual memory, we would only be running one app at a time.

Without virtual memory, we would only be running one app at a time.

It also allows Android to use swap space or zRAM and thereby increase the number of apps that can remain in memory before shutting down to make room for a new app. You can read more about how zRAM affects smartphone multitasking at the link below.

Read more: How Much RAM Does Your Android Phone Really Need?

Those are the basics of virtual memory, so let’s take a look at exactly how it all works under the hood.

Virtual Memory and Pages

To facilitate the mapping from virtual to physical, both address spaces are divided into sections, called pages. Pages in the virtual and physical space must be the same size and are generally 4K long. To distinguish between the virtual pages and the physical ones, the last page frames are called instead of just pages. Here is a simplified diagram showing the allocation of 64K virtual space to 32K physical RAM.

Gary Sims / Android Authority

Page zero (from 0 to 4095) in virtual memory (VM) maps to page frame two (8192 to 12287) in physical memory. Page one (4096 to 8191) in VM is assigned to page frame 1 (also 4096 to 8191), page two is assigned to page frame five, and so on.

One thing to note is that not all virtual pages need to be mapped. Since each app is given enough address space, there will be gaps that don’t need to be mapped. Sometimes these holes can be gigabytes in size.

If an app wants to access the virtual address 3101 (that is at page zero), it is translated to an address in physical memory in page frame two, namely physical address 11293.

Memory Management Unit (MMU) is here to help

Modern processors have a special piece of hardware that handles the mapping between the VM and the physical memory. It is called the Memory Management Unit (MMU). The MMU contains a table that maps pages to page frames. This means that the OS doesn’t have to do the translation, it’s done automatically in the CPU, which is much faster and more efficient. The CPU knows that the apps are trying to access virtual addresses and automatically translates them to physical addresses. The job of the operating system is to manage the tables used by the MMU.

How does the MMU translate the addresses?

Gary Sims / Android Authority

The MMU uses the page table set by the operating system to translate virtual addresses to physical addresses. Sticking to our example of address 3101, which is 0000 1100 0001 1101 in binary, the MMU translates it to 11293 (or 0010 1100 0001 1101). It does it like this:

The first four bits (0000) are the virtual page number. It is used to look up the page frame number in the table. The input for page zero is page frame two, or 0010 in binary. Bits 0010 are used to create the first four bits of the physical address. The remaining twelve bits, called the offset, are copied directly to the physical address.

The only difference between 3101 and 11293 is that the first four bits have been changed to represent the page in physical memory, rather than the page in virtual memory. The advantage of using pages is that the next address, 3102, uses the same page frame as 3101. Only the offset changes, so if the addresses stay within the 4K page, the MMU has an easy time doing the translations. In fact, the MMU uses a cache called the Translation Lookaside Buffer (TLB) to speed up the translations.

Translation Lookaside Buffer explained

The red boxes mark the TLB in the Arm Cortex-X1

The Translation Lookaside Buffer (TLB) is a cache of recent translations performed by the MMU. Before an address is translated, the MMU checks whether the page-to-page frame translation is already stored in the TLB. If the requested page lookup is available (a hit), the translation of the address is immediately available.

Each TLB item typically contains not only the page and page frames, but also attributes such as memory type, cache policy, access permissions, and so on. If the TLB does not contain a valid entry for the virtual address (a miss), the MMU is forced to look up the page frame in the page table. Since the page table itself is in memory, this means that the MMU needs to access the memory again to resolve the pending memory access. Thanks to special hardware within the MMU, the translation table in memory can be read quickly. Once the new translation has been executed, it can be cached for possible future reuse.

Looking back: the history of Android – the evolution of the largest mobile operating system in the world

Is it as simple as that?

On some level, the translations performed by the MMU seem quite straightforward. Do a search and copy some bits. However, there are a few issues that complicate things.

My examples dealt with 64K of memory, but in the real world apps can use hundreds of megabytes, even a gigabyte or more of RAM. A full 32-bit page table is approximately 4 MB in size (including frames, absent/present, modified, and other flags). Each app needs its own page table. If you run 100 tasks (including apps, background services, and Android services), that’s 400MB of RAM to hold the page tables.

To distinguish between the virtual pages and the physical ones, the latter are called page frames.

It gets worse if you go over 32 bit, the page tables have to stay in RAM all the time and they can’t be swapped or compressed. In addition, the page table needs an entry for each page, even if it is not used and has no associated page frame.

The solution to these problems is to use a multi-level page table. In our working example above, we saw that four bits were used as page numbers. It is possible to split the table into several parts. The first two bits can be used as a reference to another table that contains the page table for all addresses starting with those two bits. So there would be one page table for all addresses starting with 00, another for 01 and 10 and finally 11. So now there are four page tables plus a top level table.

Check out: The best phones with 16GB RAM

The top-level tables should remain in memory, but the other four can be interchanged if necessary. Likewise, if there are no addresses starting with 11, then no page table is needed. In a real-world implementation, these tables can be four or five levels deep. Each table points to a different one, according to the relevant bits in the address.

Above is a diagram from the RISC-V documentation showing how that architecture implements 48-bit virtual addressing. Each Page Table Entry (PTE) has some flags in the space that would be used by the offset. The permission bits, R, W, and X, indicate whether the page is readable, writable, and executable, respectively. If all three are zero, the PTE is a pointer to the next level of the page table; otherwise it is a leaf PTE and the lookup can be done.

How Android handles a page error

If the MMU and the OS are in perfect harmony, then all is well. But there can be errors. What happens if the MMU tries to look up a virtual address and it cannot be found in the page table?

This is known as a page error. And there are three types of page errors:

Hard Page Error — The page frame is not in memory and must be loaded from swap or from zRAM. Soft Page Error — If the page is loaded into memory at the time the error is generated, but is not marked in the memory manager as loaded into memory, this is called a minor or soft page error. The page error handler in the operating system must make the entry for that page in the MMU. This can happen if the memory is shared by several apps and the page is already in memory, or when an app has requested new memory and it has been allocated lazily, waiting for the first page access. Invalid Page Error — The program is trying to access memory that is not in the address space. This leads to a segmentation error or access violation. This can happen if the program tries to write to read-only memory, or if it ignores a null pointer, or overflows in buffer.

The benefits of virtual memory

As we have discovered, virtual memory is a way to map the physical memory so that apps can use the RAM independently, without worrying about how other apps are using the memory. It allows Android to use both multitasking and swapping.

Without virtual memory, our phones would be limited to running one app at a time, apps wouldn’t be swappable, and any attempt to keep more than one app in memory at a time would take some fancy programming.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *