CPU and Main memory are scarce resources in an operating system. All processes running in the current operating system share the CPU and memory resources in the system, and the operating system uses CPU scheduler to allocate CPU time and introduces virtual memory system to manage physical memory.

Before we can answer the need for virtual memory, we need to understand what virtual memory is in an operating system and what role it plays in the operating system. As with other abstractions in software engineering, virtual memory is an intermediate layer between the physical memory of the operating system and the processes, which hides the concept of physical memory from the processes and provides them with a cleaner and easier-to-use interface as well as more sophisticated functionality.

If we were to design an operating system from scratch, it would be a natural decision to allow processes in the system to access physical addresses in main memory directly, and this is indeed how early operating systems were implemented, with processes using the physical address of the target memory to access the contents of memory directly. However, modern operating systems have introduced virtual memory, where the virtual address held by a process is converted into a physical address by the Memory Mangament Unit, and then the physical address is used to access memory.

Primary storage is a relatively scarce resource, and although sequential reads are only 1 order of magnitude faster than disk, it provides extremely fast random access. 100,000 times faster than disk for random reads from memory, taking full advantage of the random access speed of memory is an effective way to improve program execution efficiency.

The operating system manages memory in pages. When a process finds that the data it needs to access is not in memory, the operating system may load the data into memory as pages, a process that is done by the memory management unit (MMU) in the figure above. The virtual memory of the operating system acts as an abstraction layer and plays three very critical roles as follows.

  • Virtual memory can be used to act as a cache for memory, increasing the speed at which processes can access the disk.
  • Virtual memory can provide independent memory space for processes, simplifying the process of linking and loading programs and sharing memory through dynamic libraries.
  • Virtual memory can control process access to physical memory, isolate access rights of different processes, and improve system security.

Caching

We can think of virtual memory as a slice of space on disk. When a portion of this space is accessed more frequently, that portion of data is cached in main memory on a page-by-page basis to speed up CPU performance in accessing data.

A Virtual Page (VP) in virtual memory may be in one of three states - Unallocated, Uncached, and Cached, where an unallocated memory page is one that is not requested by a process, i.e., free virtual memory that does not occupy Uncached and cached memory pages represent memory pages that are loaded to disk only and memory pages that have been loaded to main memory, respectively. As shown above, the green virtual memory page in the figure is supported by a Physical Page (PP) in main memory, so it is already cached, while the yellow virtual memory page is only on disk, so it is not cached by physical memory.

When a user program accesses a virtual page that is not cached, the hardware will trigger a Page Fault (PF). In some cases, the accessed page is already loaded into physical memory, but the correspondence does not exist in the Page Table of the user program, so we only need to establish the relationship from virtual memory to physical memory in the Page Table; in other cases, the operating system needs to load the uncached virtual page on disk into physical memory

Because main memory has a limited amount of space, when it does not contain space that can be used, the operating system will evict the appropriate physical memory page from the selection back to disk to make way for a new memory page. The process of selecting the page to be evicted is called Page Replacement in the operating system. The process of selecting a page to be evicted is called page replacement in the operating system. Both the missing page interrupt and page replacement techniques are part of the operating system’s paging algorithm, which is designed to make full use of memory resources as a cache on disk to improve the efficiency of program operation.

Memory Management

Virtual memory provides a separate memory space for running processes, creating the illusion that each process has its own memory. On 64-bit operating systems, each process has 256 TiB of memory space, 128 TiB in kernel space and 128 TiB in user space, and some operating systems use 57-bit virtual addresses to provide 128 PiB of addressing space. Since the virtual memory space of each process is completely independent, they all have full access to the entire memory from 0x0000000000000000 to 0x00007FFFFFFFFFFF.

The virtual memory space is just a logical structure in the operating system, and as we said above, applications eventually need to access the contents of physical memory or on disk. Because the operating system adds an intermediate layer of virtual memory, we also need to implement an address translator for processes to realize the conversion from virtual to physical addresses. The page table is an important data structure in the virtual memory system, and the mapping relationship from virtual memory to physical memory pages is stored in the page table of each process. In order to store the mapping data of 128 TiB virtual memory in a 64-bit operating system Linux introduced a four-layer page table in 2.6.10 to assist in virtual address translation, and a five-layer page table structure in 4.11. More layers of page table structures may be introduced in the future to support 64-bit virtual addresses.

In the four-layer page table structure shown above, the OS will use the lowest 12 bits as the page offset, and the remaining 36 bits will be divided into four groups to indicate the index of the current level in the previous level, and all virtual addresses can be used to find the corresponding physical addresses using the above multi-layer page table.

Since there are multiple layers of page table structure to translate virtual addresses, multiple processes can share physical memory through virtual memory. When we call fork in Linux to create a child process, we actually copy only the page table of the parent process. The parent and child processes will point to the same physical memory through different page tables as shown in the following figure.

Virtual memory can be used not only to share the physical memory of a process during fork, providing a mechanism for copy-on-write, but also to share some common dynamic libraries to reduce the physical memory footprint. All processes may call the same OS kernel code, and C programs will call the same standard libraries.

In addition to the ability to share memory, a separate virtual memory space will also simplify the memory allocation process. When a user program requests heap memory from the operating system, the operating system can allocate several contiguous virtual pages, but these virtual pages can correspond to non-contiguous pages in physical memory.

Memory protection

User programs in the operating system should not modify read-only code segments, nor should they read or modify code and data structures in the kernel or access private and other processes’ memory. If it is not possible to restrict memory access to user processes, attackers can access and modify other processes’ memory to affect the security of the system.

If each process holds a separate virtual memory space, then the virtual memory page table can be understood as a “connection table” between the process and the physical page, where the access relationship between the process and the physical page can be stored, including read, write, and execute permissions.

The memory management unit can decide whether the current process has permission to access the physical memory of the target, so that we end up converging all the functions of permission management into the virtual memory system, reducing the number of code paths that could be at risk.

Summary

The virtual memory design approach can be considered a common tool in software engineering, by combining the respective advantages of disk and memory, ** using the middle layer to schedule resources more rationally to fully improve resource utilization and provide a harmonious and unified abstraction** , while similar caching logic is also more common in real business scenarios.

The virtual memory of an operating system is a very complex component, and no engineer can understand all the details, but it is valuable to understand the overall design of virtual memory, and we can find many ways to design software from it. Let’s return to the question of the day - why virtual memory is needed in Linux operating systems.

  • Virtual memory can combine the advantages of disk and physical memory to provide processes with storage that appears to be fast enough and large enough.
  • Virtual memory provides processes with separate memory space and introduces a multi-layered page table structure to translate virtual memory into physical memory, which can be shared between processes to reduce overhead and simplify the process of linking, loading, and allocating memory for programs.
  • Virtual memory can control the access of processes to physical memory, isolate the access rights of different processes and improve the security of the system.

To conclude, let’s look at some of the more open related issues, and interested readers can think carefully about the following questions.

  • Why can each layer of the page table structure be responsible for addressing only 9-bit virtual addresses?
  • How many layers of page table structures are required to address 64-bit virtual memory in the operating system?