Virtual Memory
The memory requirements of modern programs are growing rapidly. However, meeting these demands solely by adding more physical memory is not sustainable due to high costs and limitations of current technologies. Virtual memory addresses this challenge by creating the illusion of a large, continuous address space for each program, even when physical memory is limited.
In today’s article, I will explain the concept of virtual memory, its workings, and its critical role in the efficiency of modern computing systems.
Fundementals
Address Spaces
Most modern computers use a 64-bit addressing system, allowing them to theoretically address up to 2⁶⁴ locations in memory — equivalent to an astonishing 16 exabytes (EB). However, this capacity far exceeds the physical RAM available in most systems today, which typically hover around 16 gigabytes (GB). This stark contrast highlights the gap between the vast addressable space and the relatively limited physical memory, making modern DRAM insufficient to fully satisfy the potential address space.
Virtual Memory bridges this gap by creating the illusion of a full address space for each program, regardless of the physical memory limitations. It achieves this by mapping the virtual addresses used by programs to physical addresses during execution, enabling efficient memory utilization while maintaining the appearance of ample memory for all running applications.
Virtual Pages, Physical Frames
The virtual address space is divided into pages, while the physical address space is divided into frames. A virtual page is mapped to a physical frame if the page resides in physical memory. Otherwise, it is mapped to a location on disk.
When a program accesses a virtual page that is not in physical memory but resides on disk, the Virtual Memory System retrieves the page from disk, loads it into a physical frame, and updates the mapping. This process is known as demand paging and ensures that only necessary pages are loaded into memory, optimizing the use of physical resources.
Page Table
During address translation, an OS-managed lookup table called the Page Table plays a central role. This table is indexed using a portion of the virtual address and stores corresponding physical addresses. If the required physical address is absent from the table, a page fault occurs, prompting the OS to load the data from disk into main memory.
This process resembles caching, where page faults can be likened to cache misses. To minimize these faults, refetching mechanisms are employed. When the table is full, the system evicts virtual addresses deemed unlikely to be needed, freeing up physical memory for more relevant data.
Address Translation
As mentioned earlier, address translation is performed using a table called the page table, which contains an entry for each virtual page. These entries typically include the following components:
- Valid Bit: Indicates whether the virtual page is currently located in physical memory. If it is not, the page must be fetched from the disk.
- Physical Page Number (PPN): Specifies the physical address where the virtual page is located when it is in memory.
- Replacement Bit(s): Used to implement page replacement policies, determining which page to evict when physical memory is full.
- Permission Bits: Define access permissions, such as read, write, or execute, for the virtual page.
- Dirty Bit: Indicates whether the page has been modified since being loaded into memory, helping to optimize writes back to disk.
An abstract example of address translation is illustrated below. The total number of bits in the address is reduced during the translation process due to the size difference between virtual and physical memory.
Page Offset the least significant 12 bits of the address remain unchanged during translation. These bits are used to locate the specific data within a page. This works because a physical page is typically 4KB in size, and the offset precisely identifies the location of the data within the page.
Storing Page Table
It’s not feasible to store a page table with entries for every virtual memory location in physical memory, especially given the vast virtual address space. Additionally, since page size is process-specific, separate page tables must be maintained for each process.
To overcome this, multi-level page tables are used. The idea is to hierarchically organize page tables so that only a small portion of them needs to reside in physical memory at any given time. This hierarchical structure resembles the levels in a cache system.
As shown above, a small portion of the page table is stored in physical memory at any given time, minimizing memory usage. The virtual address is divided into three distinct parts:
- Page Table Indexes: These segments are used to navigate the levels of the page table hierarchy. Each index corresponds to a specific level in the multi-level page table structure.
- Page Offset: This is the least significant portion of the virtual address and is used to locate the exact data within the physical page.
The Page Table Offset pinpoints the exact entry within the page table that maps a virtual page to its corresponding physical page. This hierarchical organization ensures efficient address translation while conserving physical memory resources.
Translation Lookaside Buffer (TLB)
Breaking the page table into levels simplifies storage in physical memory, but it increases the number of memory accesses needed for address translation. To mitigate this, Translation Lookaside Buffers (TLBs) are employed.
A TLB is a small, high-speed cache designed specifically to store recently used Virtual-to-Physical address translations. By caching these translations, the TLB significantly reduces the overhead of multiple memory accesses during most instruction fetches and data operations, often reducing the required accesses to just one TLB lookup.
Larger page sizes further enhance spatial locality, as a single translation covers a wider range of contiguous memory. This reduces the number of TLB misses, making TLBs even more powerful in systems with appropriately sized pages.
Memory Protection
Virtual Memory not only enhances memory management but also provides critical protection mechanisms for modern systems. This is particularly important in multi-programming environments, where multiple processes run concurrently. A process can only access the physical pages mapped in its page table.
Page — Level Access Control
Access control in virtual memory ensures that processes can only access memory they are permitted to. Each process’s page table stores access privileges, such as read, write, or execute. When a process tries to access a page, the system checks these privileges. If the process lacks the required permissions, the translation is denied, preventing unauthorized access.
A Page Directory Entry (PDE) is part of a multi-level page table and represents the first level of access. It points to an entire page table, allowing protection or control over all entries within that table. In contrast, Page Table Entry (PTE) bits provide control at the individual entry level, allowing protection for a single virtual page.
In summary, Virtual Memory provides an abstraction of a large address space to programs, even if the physical memory is limited. It achieves this by dividing memory into pages and frames , mapping virtual pages to physical frames using a page table. If a page is not in memory, a page fault occurs, and the data is fetched from disk via demand paging.
To optimize performance, multi-level page tables reduce memory usage for storing tables, and Translation Lookaside Buffers cache recent translations to minimize access delays. Virtual Memory also enforces protection by ensuring processes can only access pages mapped in their page tables, with additional access control provided by bits in Page Table Entries and Page Directory Entries.
Resources
- Digital Design and Computer Architecture 2nd Edition by David Harris & Sarah Harris
- Onur Mutlu Lectures
