Lesson 5 · Operating Systems

Memory Management and Virtual Memory

Every address a program uses is a lie the hardware maintains. Memory management in an operating system gives each process a private virtual address space, translates it page by page through the MMU, and keeps only the pages actually in use resident in physical RAM.

Why Virtual Memory Exists

Before virtual memory, programs were loaded at physical addresses and had to be relocated or written position-independently, any program could read or write any other's memory, and a program larger than RAM simply could not run. Every one of those is solved by adding one level of indirection between the address a program uses and the byte it reaches.

The memory manager in operating system design, together with the hardware MMU, maps each process's virtual pages to physical frames. Memory management operating system design is really this one job done well: decide what lives in RAM, and translate every address on the way to it. Each process sees a private, contiguous address space starting at zero, regardless of where its pages actually sit or how scattered they are.

That indirection buys more than isolation. Pages can be shared — one physical copy of libc mapped into every process. They can be copy-on-write, so fork duplicates page tables rather than memory and copies a page only when someone writes it. They can be lazily allocated, so a 1 GB malloc costs nothing until it is touched. And they can be backed by a file, which is what mmap and demand-paged executables are.

The unit is the page, almost always 4 KB, with huge pages of 2 MB or 1 GB available for large working sets. The size is a compromise: smaller pages waste less on partial fills but need larger page tables and more TLB entries to cover the same memory.

One indirection buys isolation, relocation, sharing, and overcommit
Copy-on-write makes fork cheap; lazy allocation makes malloc cheap
4 KB is standard; huge pages cut TLB pressure for big working sets
Shared pages mean one physical copy of libc for the whole system

Address Translation and Paging

A virtual address splits into a virtual page number and an offset. With 4 KB pages the low 12 bits are the offset and the rest is the page number. Only the page number is translated: the MMU looks it up, gets a physical frame number, and concatenates the untouched offset. The tracer on this page uses a 1 KB page to keep the arithmetic readable: virtual address 2500 gives page 2 (2500 ÷ 1024) and offset 452 (the remainder), page 2 maps to frame 7, and 7 × 1024 + 452 is physical address 7620.

A single flat page table is impossible at 64-bit scale. A 48-bit address space with 4 KB pages needs 2^36 entries — 512 GB of table per process, for a table that is almost entirely empty. Real hardware uses a multi-level page table: x86-64 splits the page number into four 9-bit indices walking PML4, PDPT, PD, and PT, so unmapped regions cost nothing because entire subtrees are simply absent.

The price is that a translation now needs four memory reads before the actual access — five reads for one load. Inverted page tables (one entry per physical frame, hashed) fix the space problem instead and are used on some architectures, at the cost of making shared pages awkward.

Each page-table entry carries flags as well as a frame number: present, read/write, user/supervisor, accessed, dirty, and no-execute. The hardware sets accessed and dirty automatically, and replacement algorithms depend on exactly those two bits.

Page number is translated; offset passes through unchanged
x86-64 walks four levels so empty regions cost no memory
A naive walk costs four extra reads per access
PTE flags: present, rw, user, accessed, dirty, no-execute

Page Replacement Algorithms

When no free frame exists, one resident page must be evicted. OPT evicts the page used furthest in the future — provably optimal, impossible to implement, and useful only as the benchmark other algorithms are measured against.

FIFO evicts the oldest and is bad, because age has little to do with usefulness. It also suffers Bélády's anomaly: adding frames can increase faults, which is as counter-intuitive as it sounds. LRU evicts the least recently used, approximates OPT well because of temporal locality, and is too expensive to implement exactly — a true LRU needs a timestamp updated on every single memory access.

So real kernels approximate. The clock (second-chance) algorithm sweeps a circular list checking the hardware accessed bit: set means give it a second chance and clear the bit, clear means evict. It costs almost nothing and behaves close to LRU. Linux refines this into two LRU lists, active and inactive, promoting a page only on a second reference so a single scan cannot flush the working set.

A dirty victim costs extra: it must be written back before its frame is reused, so replacement prefers clean pages and background writeback exists to keep dirty pages few. LFU by contrast weights history too heavily — a page hot at startup and never touched again keeps a high count forever.

OPT is the unreachable benchmark; FIFO ignores usefulness entirely
Bélády's anomaly: more frames can mean more faults under FIFO
Clock approximates LRU using the hardware accessed bit for free
Evicting a dirty page costs a writeback, so clean pages go first

Key reference

Terms, operations, and practical uses

Address translation

Virtual page numberThe high bits of an address; the only part that is translated.
OffsetThe low 12 bits at 4 KB pages; passes through untouched.
Physical frameThe block of RAM currently backing the page.
MMUHardware that performs translation and permission checks on every access.

Page tables

Multi-level tablex86-64 walks PML4, PDPT, PD, PT so empty regions cost nothing.
PTE flagspresent, rw, user/supervisor, accessed, dirty, no-execute.
Inverted page tableOne entry per frame, hashed; saves space but complicates sharing.
Page-table walkFour extra memory reads for a single load, on a TLB miss.

TLB

TLB hitCached translation resolved in roughly one cycle.
TLB reachEntries x page size — only 256 KB at 64 entries and 4 KB pages.
Huge pages2 MB or 1 GB pages, used mainly to extend reach.
ASID / PCIDAddress-space tags that let entries survive a context switch.

Page faults

Minor faultPage already in RAM; the kernel just installs the mapping.
Major faultMust read from storage; the process blocks meanwhile.
Copy-on-writefork shares pages until a write forces a private copy.
Demand pagingNothing is mapped until it is touched.

Replacement and pressure

OPTEvicts the page used furthest ahead; the unreachable benchmark.
Belady's anomalyUnder FIFO, more frames can produce more faults.
ClockSecond-chance sweep using the hardware accessed bit; near-LRU for free.
ThrashingWorking set exceeds resident set, so faulting displaces useful work.

Fragmentation

ExternalScattered free holes; paging eliminates it entirely.
InternalWasted tail inside a page; averages half a page per allocation.
SegmentationVariable-length logical units; matches structure, fragments externally.
Working setThe pages a process actively needs over a recent interval.

Implementation

Translate a virtual address

page_size = 1024
virtual_address = 2500
page_table = {2: 7}
page = virtual_address // page_size
offset = virtual_address % page_size
physical_address = page_table[page] * page_size + offset
print('physical address', physical_address)

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
    int pageSize = 1024;
    int virtualAddress = 2500;
    unordered_map<int, int> pageTable = {{2, 7}};
    int page = virtualAddress / pageSize;
    int offset = virtualAddress % pageSize;
    int physicalAddress = pageTable[page] * pageSize + offset;
    cout << "physical address " << physicalAddress << '\n';
}

import java.util.Map;
class Main {
    public static void main(String[] args) {
        int pageSize = 1024;
        int virtualAddress = 2500;
        Map<Integer, Integer> pageTable = Map.of(2, 7);
        int page = virtualAddress / pageSize;
        int offset = virtualAddress % pageSize;
        int physicalAddress = pageTable.get(page) * pageSize + offset;
        System.out.println("physical address " + physicalAddress);
    }
}

Watch it run

Step through it

Running on page size 1024, virtual address 2500, page 2 → frame 7

Output

Read all 12 Steps

Start with virtual address 2500 The CPU produces address 2500 in this process's virtual address space. Translation must find the matching physical byte.
Calculate the virtual page Integer division gives 2500 ÷ 1024 = 2, so the address belongs to virtual page 2.
Calculate the page offset The remainder is 452. This is the byte's position inside page 2 and it will not change during translation.
Look up page 2 The memory-management unit uses page 2 as an index into this process's page table.
Validate the entry Before using the mapping, the hardware checks that the page is present and that the requested access is permitted.
Find the frame base Physical frame 7 begins at 7 × 1024 = 7168.
Add the unchanged offset Adding the original offset selects the corresponding byte inside frame 7: 7168 + 452.
Use physical address 7620 The translation is complete. Memory hardware can now access physical address 7620.
Now translate VA 9300 — page 9 A second access, this time to virtual address 9300. 9300 ÷ 1024 gives page 9, offset 84. The same arithmetic as before, a different page.
Page 9 is not present — page fault The page-table entry for page 9 has present = no. The CPU traps into the kernel before the instruction completes. This is a page fault: not an error, just the memory manager being asked to do work it deferred.
Kernel finds a free frame and loads the page The memory manager picks free frame 3, reads the page's 1024 bytes in from disk, and writes the new mapping into the page table. If no frame were free, a replacement algorithm would evict one first.
Resume the instruction — it now succeeds Control returns to the faulting instruction and it re-executes. The translation now resolves: frame 3 × 1024 = 3072, plus offset 84 = 3156. The program never learns that any of this happened.

Fragmentation and Thrashing

External fragmentation is free memory that exists but is unusable because it is split into scattered holes — 100 MB free, no contiguous 10 MB block. It is the defining problem of contiguous allocation with first-fit, best-fit, or worst-fit, and paging eliminates it entirely, because any free frame can back any page.

Internal fragmentation is what paging creates instead: a 4100-byte allocation occupies two pages and wastes 4092 bytes. It is bounded and predictable, averaging half a page per allocation, and that trade — unbounded external for bounded internal — is why paging won. Huge pages worsen it considerably, which is the argument against using them by default.

Segmentation divides memory by logical unit (code, data, stack) rather than fixed size, which suits how programs are structured but reintroduces external fragmentation because segments vary in length. x86 supported segmentation and paging together; 64-bit mode largely abandoned segmentation, keeping paging.

Thrashing is the failure mode where the resident set is too small for the working set — the pages a process actively needs — so it faults, evicts a page it is about to need, and faults again. CPU utilisation collapses while disk saturates, and the classic disaster is the OS responding to low utilisation by admitting more processes. The fix is to reduce multiprogramming or add RAM; the working-set model and page-fault-frequency control both aim to detect it before it spirals.

External: scattered holes. Paging removes it completely
Internal: wasted tail inside a page, ~half a page per allocation
Segmentation matches program structure but fragments externally
Thrashing means the working set does not fit — add RAM or admit less