This article will explore what virtual memory is, why it exists, and how it works from a high level.
In a previous article, we discussed the benefits of the CPU cache. Caching was invented because of a discrepancy between the speed of memory accesses and the CPU's processing ability. By employing a hardware cache, items recently loaded from main memory are stored in a smaller memory, closer to the CPU, so that they can be quickly retrieved when needed. Thus, caching solved the problem of speed.
But what about capacity?
In this article, we'll look at what virtual memory is and how it helps solve the issue of capacity for CPUs.
Supporting Information
The Memory Hierarchy
Modern computer systems can run tens if not hundreds of different applications simultaneously. Since memory is a limited resource, as more applications consume it performance can degrade and even come to a complete standstill. This is where virtual memory comes in. Figure 1 shows a memory hierarchy including cache, main memory, and virtual memory.
Figure 1. Memory hierarchy
As Figure 1 illustrates, virtual memory exists to increase the memory capacity of the system. This is done by allocating a portion of the disk drive as a dedicated block of memory that “looks” like main memory to any applications that might need it.
To keep disk accesses from degrading speed performance, main memory acts as a fully associative cache for virtual memory, storing recently accessed disk locations. Thus, through the use of virtual memory, main memory becomes another layer in the cache hierarchy.
While the details are outside the scope of this article, it should be noted that virtual memory is managed and controlled via interactions between the computer's operating system and the processor's memory management unit (MMU).
Caching vs. Paging
Recall that a cache breaks up a physical memory address into a number of fields. This is done in order to identify a cache entry that is storing recently accessed data. For a fully associative cache, these fields are the cache tag and byte offset. The cache entry is made up of a matching tag and a cache block that contains the data.
If a matching tag is not found, this is referred to as a cache miss.
Figure 2. Caching nomenclature
Virtual memory works similarly but uses the concept of virtual addresses.
Virtual addresses are made up of a virtual page number and a page offset. The virtual address is used to locate an item in memory called a page frame, usually 4kB in size.
The page frame contains a page frame number and the actual data, referred to simply as a page.
The page offset is used to access a single word within the 4kB page. If a virtual address does not point to a location found in physical memory, a page fault occurs and the system must go out to the disk drive for the requested data. When a page fault does occur, the page on disk is moved to a page frame in memory. Moving a page between main memory and disk is called paging (or swapping).
Figure 3. Paging nomenclature
Since virtual memory is used to expand the capacity of the system's memory, an addressing scheme that accounts for both the locations on disk and the locations in main memory is required. This is where virtual addresses come in.
Virtual addresses span both the disk drive and the main memory, resulting in more virtual addresses than physical memory addresses. Consequently, before the data in a page can be accessed, the system must determine whether that data resides in physical or virtual memory. This is done through address translation.
Figure 4. Virtual addresses map to both virtual and physical memory
Address Translation
As mentioned earlier, physical memory acts as a fully associative cache for virtual memory. Recall that a fully associative cache is a single set with multiple entries. Each entry is compared against the cache tag for a match. With pages sized at 4kB, even a small virtual memory system would require thousands of comparator circuits. To get around this a page table is used.
Page Tables
A page table is a data structure that maps virtual page numbers (part of the virtual address) to page frame numbers.
The page table contains an entry for every virtual address along with a valid bit that denotes whether this page is found in physical memory or not. If the page table entry is valid, then the page frame number is combined with the page offset (the other part of the virtual address) to build the physical memory address, i.e., where the desired data is stored in memory. Figure 5 illustrates how a page table is used to convert from virtual to physical address.
Figure 5. Using a page table for address translation
It's important to remember that page frame numbers represent where a page is stored, while physical addresses represent the location of a single word within a page. If the valid bit of the page table entry is not set, the virtual address must map to a page stored on disk.
The page table, itself, is stored in main memory along with the pages it is used to locate. Thus, with the use of a page table, reading or writing to any page actually takes two memory accesses. This may seem counterintuitive, and it would result in a large performance hit if not for the translation lookaside buffer, or TLB.
Translation Lookaside Buffer
Since pages are 4kB in size, the data within a page exhibits both temporal and spatial locality. This makes page table entries a perfect candidate for caching.
The translation lookaside buffer, or TLB, is a small fully associative cache used to store recently accessed page table entries. By caching the recently used page table entries, the system can forgo making numerous page table lookups, thereby circumventing the problem of accessing memory twice. The TLB often contains only a few hundred entries, yet it has an incredibly high hit rate (as high as 99%).
Figure 6 shows a TLB with four entries.
Figure 6. Simplified TLB implemented as a fully associative cache
Conclusion
This article introduced the concept of virtual memory. Virtual memory is an extension of the memory system used to expand the system's capacity.
Virtual memory also allows for the protection and isolation of memory between applications or processes. It is controlled and managed by a computer's operating system and the processor's MMU. Virtual memory works by allocating a portion of disk space as part of the system's memory.
As an extension of the memory hierarchy, virtual memory has become a fundamental piece of a computer's overall architecture. Understanding virtual memory enhances your computer comprehension in an increasingly complex world.
