Virtual Memory

Overview

In physical addressing, the CPU accesses main memory directly using a physical address (PA). Each byte-size cell in main memory has a unique physical address to accommodate.

In virtual addressing, the CPU accesses main memory indirectly using a virtual address (VA). A virtual address is converted into a physical address via a process called address translation. This is performed by the memory management unit (MMU) found on the CPU.

Address Spaces

An address space is an ordered set of nonnegative integer addresses. The physical memory system has a physical address space (PAS). Each process has its own virtual address space (VAS).

Typically the lowest part of the virtual address space is unmapped so that any references to it are illegal. This allows catching references though null pointers and other pointers with small integer values.

Pages

Virtual memory is partitioned into fixed-size blocks called virtual pages (or pages). Physical memory is also partitioned into physical pages (or page frames) of the same size.

Each virtual page belongs to any one of three disjoint sets:

• Unallocated. Pages that have not yet been allocated by the virtual system.
  • PTEs have their valid bit set to 0 and their address field set to NULL.
• Cached. Pages that are not currently cached in physical memory.
  • PTEs have their valid bit set to 1. Their address field refers to an address in main memory.
• Uncached. Pages that are not currently cached in physical memory.
  • PTEs have their valid bit set to 1. Their address field refers to an address in disk.

Page Tables

A page table is a lookup table managed by the OS. It is an array of page table entries (PTEs), each of which consists of a valid bit, permission bits, and a (possibly null) memory address. Page tables are usually arranged in a hierarchy. A hierarchy of more than one level is called a multi-level page table. Each process has its own hierarchy of page tables.

The starting address of a page table is contained in a special CPU register called the page table base register (PTBR).

Address Translation

Consider a $k$-level page table hierarchy. Then a virtual address is partitioned into $k$ virtual page numbers (VPNs) and a virtual page offset (VPO).

Each VPN $1\le i\le k$ is used to index into a page table at level $i$. Each PTE in a level $1\le j<k$ table points to the base of some page table at level $j+1$. Each PTE in a level $k$ table contains either a physical page number (PPN) or the address of a disk block. The PPN is concatenated with the VPO. also known as the physical page offset (PPO), to construct the physical address.

Translation Lookaside Buffer

The translation lookaside buffer (TLB) is a small, virtually addressed cache where each cache line holds a block consisting of a single PTE.

Memory Mapping

Memory mapping refers to the initialization of virtual memory areas by associating it with an object on disk.

void *mmap(void *start, size_t length, int prot, int flags,
           int fd, off_t offset);
int munmap(void *start, size_t length);

Object Types

There exist two types of objects:

• A regular file. The file section is divided into page-size pieces, with each piece containing the initial contents of a virtual page.
• An anonymous file. This file, created by the kernel, contains all binary zeros. When swapping, the kernel simply erases the victim page as opposed to swapping out with contents on disk.

The kernel swaps virtual pages in and out of the swap file. Note this implies the size of the swap file bounds the total amount of virtual pages that can be allocated.

Shared/Private

An object can be mapped into an area of virtual memory as either a shared object or a private object. Only a single copy of a shared object needs to be stored in physical memory. Private objects are mapped into virtual memory using copy-on-write (COW). Once a process attempts to write to a private object, the kernel produces a copy that the process writes to instead.