Memory Management: From Address Spaces to Paging

Logical vs. physical addresses

• A logical (virtual) address is generated by the CPU when a program runs; the set of them is the process's address space.
• A physical address is what goes to the memory chips.
• Address binding can happen at compile time (absolute code), load time (relocatable code), or — in all modern systems — at execution time, by the MMU on every access. This allows a process to be moved in memory and many processes to share it safely.

Simplest MMU: base (relocation) and limit registers. For each access: if logical ≥ limit → trap (illegal address); else physical = base + logical.

Example: base = 14000, limit = 3000. Logical 346 → physical 14346. Logical 3500 → trap: the process cannot touch memory outside its region. Changing base and limit is a privileged operation — done by the kernel at each context switch.

Dynamic linking and shared libraries (.so, .dll): the code of libc is loaded once into physical memory and mapped into the address space of every process that uses it — saving memory and allowing library updates without recompiling programs.

Contiguous allocation and fragmentation

If each process gets one contiguous region, the OS keeps a list of holes (free blocks) and must choose one for each request:

• First fit — the first hole that is large enough (fast).
• Best fit — the smallest hole that is large enough (leaves tiny leftovers).
• Worst fit — the largest hole (leaves big leftovers).
• Next fit — like first fit, but continue searching where the last search stopped.

Worked example. 1,000 KB of memory. A 200, B 50, C 100, D 50, E 300, F 50 are allocated in order; then A, C and E are freed. Holes: [0, 200), [250, 350), [400, 700), [750, 1000). Requests: G 90, H 250, I 200, J 100, K 200.

With 210 KB free, K (200 KB) fails for three policies: the free memory is split into pieces that are too small. This is external fragmentation, measured here as 1 − largest hole / total free (52 % for first fit). Best fit happens to win on this sequence, but no policy is best for all sequences; simulations show first fit and best fit are similar and better than worst fit, and first fit is faster. The 50-percent rule: with first fit, for N allocated blocks, about 0.5 N blocks are lost to fragmentation — one third of memory may be unusable.

Compaction (moving processes to merge holes) fixes external fragmentation but is expensive and requires execution-time binding. Internal fragmentation is the opposite problem: memory allocated inside a block but unused (a 70 KB request receiving a 128 KB block).

Paging

Paging removes external fragmentation by cutting memory into fixed-size pieces:

• Physical memory is divided into frames; the logical address space into pages of the same size (typically 4 KiB).
• Any page can go into any free frame. A page table per process maps page number → frame number.
• A logical address is split into page number p (high bits) and offset d (low bits). With page size 2ⁿ, the offset is the last n bits.

Translation: physical = frame(p) × page size + d.

Example (page size 1 KiB = 1,024 bytes; page table: page 0 → frame 5, page 2 → frame 2, page 7 → frame 1, page 1 not present):

• Logical 1023 → p = 0, d = 1023 → frame 5 → 5 × 1024 + 1023 = 6143.
• Logical 2100 → p = 2, d = 52 → frame 2 → 2100 (coincidence: page 2 is in frame 2).
• Logical 7700 → p = 7, d = 532 → frame 1 → 1556.
• Logical 1024 → p = 1, not present → page fault (Chapter 10).

Page-table entries contain the frame number plus bits: valid/present, protection (read/write/execute), dirty (modified), referenced/accessed (used recently), user/supervisor. Paging still has internal fragmentation: on average half a page per process region.

Page-table size and multi-level tables

With 32-bit addresses and 4 KiB pages: 12 offset bits, 20 page-number bits → 2²⁰ ≈ 1 million entries × 4 bytes = 4 MiB per process — mostly for unused addresses. With 48-bit addresses and 8-byte entries: 2³⁶ entries = 512 GiB. Impossible.

Solution: page the page table. A multi-level (hierarchical) table splits the page number into several indexes; only the parts of the table that describe used memory exist. If each table must fit in one 4 KiB page with 8-byte entries, it holds 512 entries = 9 bits per level: 36 page bits / 9 = 4 levels — exactly x86-64's four-level paging (PML4, PDPT, PD, PT); newer CPUs add a fifth level for 57-bit addresses.

Other designs: hashed page tables (hash the page number; common for sparse 64-bit spaces), and inverted page tables (one entry per physical frame, search by (process, page); saves memory, slows lookup; used by some PowerPC and IA-64 systems).

The TLB and effective access time

Every memory access now needs extra accesses to read the page table (4 with 4 levels!). The TLB (translation look-aside buffer) is a small, fast, associative cache of recent translations (typically 64–2,048 entries).

Effective access time (EAT) with hit ratio h, TLB lookup t, memory access m and L page-table levels:

EAT = h · (t + m) + (1 − h) · (t + (L + 1) · m)

Example: t = 1 ns, m = 100 ns, L = 4. Without a TLB: 5 × 100 = 500 ns. Scanning an array (4 accesses per page, TLB of 4 entries) gives h = 75 %: EAT = 0.75 × 101 + 0.25 × 501 = 201 ns. With h = 99 % (typical thanks to locality): 0.99 × 101 + 0.01 × 501 = 105 ns — only 5 % slower than no translation at all.

The TLB must be flushed (or tagged with an address-space ID, ASID/PCID) on context switches — one reason context switches are expensive (Chapter 3).

Huge pages (2 MiB or 1 GiB on x86-64) let one TLB entry cover 512× more memory. Databases, the JVM (-XX:+UseLargePages) and AI frameworks use them to reduce TLB misses; Linux offers transparent huge pages.

Segmentation

Segmentation divides the address space into variable-size logical units — code, data, heap, stack — each with a base and limit in a segment table; an address is (segment, offset). It matches the programmer's view and allows per-segment protection, but suffers from external fragmentation. Modern x86-64 systems keep segmentation only vestigially and rely on paging; the "segmentation fault" error name survives from that history.

Kernel allocators: buddy and slab

The Linux kernel allocates physical memory with the buddy system: memory is split into power-of-two blocks. A request is rounded up to the next power of two; a larger block is split in halves ("buddies") until the right size is reached. When a block is freed and its buddy is also free, they are merged — fast coalescing, at the price of internal fragmentation. Example with 1,024 KB and 64 KB minimum: a 70 KB request splits 1,024 → 512 → 256 → 128 and uses a 128 KB block (58 KB wasted). cat /proc/buddyinfo shows free blocks of each size.

On top, the slab allocator keeps caches of pre-initialized objects of the same type (process descriptors, inodes) to avoid repeated allocation and initialization (/proc/slabinfo).

Memory in containers and at the edge

A container's memory is limited with cgroups (docker run --memory=2g, Kubernetes resources.limits.memory). If the processes of the container exceed the limit, the kernel's OOM killer terminates one of them (exit code 137, "OOMKilled") — a common production incident. Kubernetes schedules pods by their memory requests and kills them at their limits.

AI models at the edge. Model memory ≈ parameters × bytes per parameter (+ activations and KV cache). A 7-billion-parameter model in 16-bit precision needs 7 × 10⁹ × 2 = 14 × 10⁹ bytes ≈ 13 GiB — too big for an 8 GB edge board; quantized to 4 bits it needs 3.5 × 10⁹ bytes ≈ 3.3 GiB and fits. Memory, not compute, often decides where a task can run — a direct input to the offloading decisions of Chapter 13.

Key takeaways

• Programs use logical addresses; the MMU translates them at run time. Base/limit: trap if logical ≥ limit, else base + logical.
• Contiguous allocation (first/best/worst/next fit) suffers external fragmentation; compaction is costly.
• Paging: page number + offset; physical = frame × page size + offset; no external fragmentation, some internal.
• Page tables can be huge → multi-level (x86-64: 4 levels of 9 bits + 12-bit offset), hashed or inverted tables.
• TLB: EAT = h(t + m) + (1 − h)(t + (L + 1)m); locality makes h ≈ 99 %. Huge pages extend TLB reach.
• Segmentation = variable logical units; modern systems use paging.
• Linux: buddy allocator (power-of-two split/merge) + slab caches.
• Containers: cgroup memory limits and the OOM killer. Edge AI: parameters × bytes decide what fits where.