The origin of virtual memory

Why does virtual memory exist? In the old computer system, there was no virtual memory, and programs ran directly on physical memory. But as we get bigger and bigger and want to do more and more, running our programs directly on physical memory can cause problems.

  • Multi-program running affects memory efficiency.
  • Modifying memory data may cause a program to crash.

To answer the first question, there are several programs that need to be run, but the memory space is insufficient. At this time, we need to copy a program in the memory to the hard disk, and then load the new program into the memory. The whole process is time-consuming, and large amounts of data are loaded and loaded frequently, making memory use inefficient.

Then see question 2, because the application runs on the physical memory, what is there between program security protection measures, when we visit A program data address, may be due to our negligence, fault data access into B program addresses, so baffling problems can lead to B program or collapse directly.

In view of the above problems, excellent programmers invented virtual memory management mechanism, very well to solve all kinds of problems. Follow me to see how virtual memory solves this problem.

Overview of virtual memory systems

The CPU accesses main memory by generating a virtual address, which is translated into an appropriate physical address before being sent to memory. Converting virtual addresses to physical addresses requires the coordination of the Memory Management Unit (MMU), which is part of the CPU chip hardware.

It looks perfect, but it’s not. In the process of MMU address translation, there is a data structure called page table, which stores the mapping between virtual addresses and physical addresses. Each time the MMU converts a virtual address to a physical address, the corresponding page table is read from memory. This is very time consuming, MMU address translation efficiency will be greatly reduced.

Is there room for improvement? The answer is yes. Just cache the page table. In fact, they do. They include a cache of page tables in the MMU called a Translation Lookaside Buffer (TLB). In short, THE function of TLB is to speed up address translation of MMU.

The overall process of virtual memory can be divided into four steps:

1. The CPU generates a virtual address

2. The MMU obtains the page table from the TLB and translates it into a physical address

3. The MMU sends the physical address to the main storage

4. Main memory returns the data corresponding to the address to the CPU

The overall process is shown in Figure 1.

Details of virtual memory

The mapping between virtual addresses and physical addresses is shown in Figure 2.

1. Pages and page tables

Virtual memory systems divide virtual memory into fixed-size chunks, also known as virtual pages. Similarly, physical memory is divided into fixed-size chunks called physical pages.

To map virtual pages to physical pages, we need a data structure called a page table. A Page Table is essentially an array of Page Table entries (PTE).

Each PTE consists of a significant bit and an N-bit address. If the significant bit of the PTE is 1, the n-bit address indicates the starting position of the corresponding physical page, that is, the virtual address can find the corresponding physical page in physical memory. If the significant bit of the PTE is 0 and the following address is empty, the virtual page to which the virtual address points has not yet been assigned. If the significant bit of the PTE is 0 and followed by the address pointing to the virtual page, it indicates that the virtual address has no corresponding physical address in physical memory and points to the starting position of the virtual page on disk. This situation is usually called page missing.

At this point, if there is a page missing phenomenon, MMU will issue a page missing exception, which calls the page missing exception program in the kernel, which will select a sacrifice page in main memory and replace the virtual page we need with the original sacrifice page.

2. Multi-level page tables

We’ve only been talking about single-page tables so far, but in real environments virtual space addresses are large (2^32 = 4GB for a 32-bit system, let alone a 64-bit system). In this case, using a single-page table is obviously inefficient.

A common approach is to use a hierarchical page table. Suppose our environment is a 32-bit virtual address space, which has the following form: The virtual address space is divided into 4KB pages, with each PTE being 4 bytes. The first 2K pages of memory are allocated to code and data. The next 6K pages have yet to be allocated. The next 1023 pages are also unassigned, and the next 1 page is assigned to the user stack.

Figure 3 shows the second-level page surface structure (four or more in real life) constructed for this virtual address space. The first-level page table (1024 Ptes covering exactly 4GB of virtual address space, and each PTE is only 4 bytes. Each PTE is responsible for mapping a 4MB chunk of the virtual address space, each consisting of 1024 contiguous pages. Each PTE in the secondary page table is responsible for mapping a 4KB virtual memory page.

For details, please refer to “Understanding Computer Systems in Depth” P571-P572.

The last

Back to the original problem, the multi-process runtime efficiency is not greatly compromised due to virtual memory MMU and TLB. At the same time, each process has its own page table, so processes do not interact with each other.