Introduction
Virtual Memory Paging
Memory paging is a memory management technique used to control sharing of memory resources belonging to a computer or virtual machine (VM).
In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages.
A computer can address memory beyond the amount physically installed on the system. This non-physical memory, or virtual memory, is actually a section of a hard disk set up to emulate the computer’s RAM.
Address Spaces
Virtual Address Spaces
A virtual address space is the set of ranges of virtual addresses that an operating system makes available to a process (max 64 bits on a 64 bit OS) .
Each process has its own virtual address space that is distinct from other processes.
This provides several benefits, one of which is security through process isolation assuming each process is given a separate address space.
Physical Address space
When a process is loaded into RAM the virtual address space is mapped to a physical address space of the same size.
The physical address space might be non-contiguous, meaning each page could be physically located in different parts of the RAM.
The mapping assignments are recorded in the page table.
Page Table
Page Table
The page table is a data structure used by a virtual memory system in a computer to store mappings between virtual addresses and physical addresses.
The page table is set up by the computer’s operating system, and may be read and written by the memory management unit (MMU) or by low-level system software or firmware during the virtual address translation process .
Physically, the memory of each process may be dispersed across different areas of physical memory, or may have been moved (paged out) to secondary storage, typically to a hard disk drive (HDD) or solid-state drive (SSD).
However every process is given the impression that it is working with large, contiguous sections of memory.
MMU
Memory Management Unit (MMU)
The MMU maps the virtual addresses from each program into separate areas in physical memory, which is generally much smaller than the theoretical maximum.
This means that programs generally have addresses that access the theoretical maximum memory of the computer architecture, 32 or 64 bits.
TLB
Translation Lookaside Buffer
The Translation Lookaside Buffer (TLB) is a a small, fast memory cache that stores recently used mappings between virtual addresses and their corresponding physical addresses.
Once the translation information is retrieved, a new TLB entry is created using this information. This typically includes the virtual address, the corresponding physical address, and additional control bits such as access permissions.
If the TLB is full and there is no space for the new entry, a replacement policy is used to select an existing entry to be evicted from the TLB to make room for the new entry.
Common replacement policies include least recently used (LRU), random replacement, or first-in-first-out (FIFO).
Page Fault / Miss
Page Fault / Page Table Miss
A page fault is an exception that the memory management unit (MMU) raises when a process accesses a memory page without proper preparations .
The MMU raises the exception and the operating system’s kernel handles the exception by loading the requested page into RAM or denying an illegal memory access.
Steps
Step 1 – Search the TLB
When a virtual address needs to be translated into a physical address, the Translation Lookaside Buffer is searched first.
If a match is found, which is known as a TLB hit, the physical address is returned and memory access can continue.
Step 2 – Walking the Page Table
However, if there is no match this results in a TLB miss.
The MMU, the system firmware, or the operating system’s TLB miss handler will look up the address mapping in the page table to see whether a mapping exists.
This is known as a page walk.
Step 3 – Write Back to TLB
If the memory mapping exists, it is written back to the TLB and the faulting instruction is restarted.
The subsequent translation will result in a TLB hit, and the memory access will continue.
Step 4 – Page Fault
If the page is not in RAM (because it had been paged out onto secondary storage) this will result in a page table miss, triggering a page fault).
Step 5 – Paging In
The process is not currently stored in RAM and therefore the system will need to load the process back into RAM (paged in).
Stage 6 – Paging Out
Other data in the RAM may need to be paged out the Secondary Storage.
Step 7 – Page Table Update & Process Restart
Finally the page table and TLB are updated the process is restarted.