Background
Basic Concepts
The only storage directly accessible by the CPU is registers and main memory. Data on disk must be loaded into memory before the CPU can process it.
Memory access takes time, so a cache is placed between the CPU and memory to bridge the speed gap.
CPU <-> Registers (~1ns) <-> Cache (~10ns) <-> Main Memory (~100ns)
Address Binding
The process of translating addresses used by a program into actual memory addresses. There are three types based on binding time.
[Address Binding Timing]
1. Compile-time Binding
- Memory location determined at compile time
- Recompilation needed if location changes
- Example: MS-DOS .COM programs
2. Load-time Binding
- Address determined when loading program into memory
- Uses relocatable code
- Address cannot change after loading
3. Execution-time Binding (Modern OS)
- Addresses dynamically translated during execution
- Requires MMU (Memory Management Unit) hardware
- Processes can be moved within memory
Logical and Physical Addresses
- Logical Address: Address generated by the CPU. Also called virtual address
- Physical Address: Actual address of memory hardware
[Address Translation via MMU]
CPU --[Logical addr: 346]--> MMU --[Physical addr: 14346]--> Memory
|
Relocation Register
(base value: 14000)
Physical address = Logical address + Relocation register value
346 + 14000 = 14346
User programs deal only with logical addresses and cannot see physical addresses directly.
Dynamic Loading and Dynamic Linking
Dynamic Loading: Loads routines into memory only when they are called. Unused routines do not occupy memory, improving memory utilization.
Dynamic Linking: Links libraries at runtime.
[Static Linking vs Dynamic Linking]
Static Linking:
Program A: [code + libc copy] -- 50MB
Program B: [code + libc copy] -- 50MB
Total memory: 100MB
Dynamic Linking (Shared Libraries):
Program A: [code + libc ref] -- 10MB
Program B: [code + libc ref] -- 10MB
libc.so: [shared library] -- 40MB
Total memory: 60MB
Linux: .so files (Shared Object)
Windows: .dll files (Dynamic-Link Library)
Contiguous Memory Allocation
The simplest memory management approach, placing each process in a contiguous memory region.
Memory Protection
[Base Register and Limit Register]
Base Limit
| |
v v
+-------+=======================+-------+
| OS | Process P's region | Other |
+-------+=======================+-------+
0 300040 420940
For address addr generated by CPU:
if (addr >= base && addr < base + limit)
Access allowed -> Physical memory access
else
Trap raised -> OS handles error
Memory Allocation Strategies
Methods for allocating memory to processes from the free space (hole) list.
[Memory Allocation Example]
Initial state:
|---OS---|--P1--|-------free-------|--P3--|---free---|
Allocation strategies:
1. First Fit: Allocate in the first sufficiently large hole
Pros: Fast
2. Best Fit: Allocate in the smallest sufficient hole
Pros: Creates small remaining space
Cons: Full search needed, creates very small fragments
3. Worst Fit: Allocate in the largest hole
Pros: Remaining space is large enough to reuse
Cons: Full search needed
Fragmentation
[External vs Internal Fragmentation]
External Fragmentation:
|P1| free |P2| free |P3| free |P4|
100KB 50KB 80KB
Total free space: 230KB, but cannot load a 200KB process!
(Not contiguous)
Solution: Compaction - Move processes to one end
|P1|P2|P3|P4|-----230KB free-----|
Internal Fragmentation:
When memory is allocated in fixed-size blocks
If process is smaller than block, space is wasted inside
Process size: 18,462 bytes
Block size: 20,000 bytes
Internal fragmentation: 1,538 bytes wasted
How Fragmentation Actually Comes About
The diagram above shows a state in which fragmentation already exists. Walking through the allocations and frees in order makes it much easier to see why this is unavoidable.
[How external fragmentation forms: 1000KB total]
0) Start: everything is one free hole
|----------------- 1000 free -----------------|
1) Allocate A(200), B(300), C(150), D(250) in order (first fit)
|--A:200--|----B:300----|--C:150--|---D:250---|-100-|
2) B exits -> 300KB returned
|--A:200--|---300 free---|--C:150--|---D:250---|-100-|
3) Allocate E(120) -> lands at the front of B's old hole
|--A:200--|-E:120-|-180fr-|--C:150--|---D:250---|-100-|
4) D exits -> 250KB returned
|--A:200--|-E:120-|-180fr-|--C:150--|--250 free--|-100-|
Total free space now = 180 + 250 + 100 = 530KB
Yet a 300KB process cannot be loaded,
because the largest contiguous run is only 250KB.
Step 3 is the crux. The instant 120KB went into a 300KB hole, a useless 180KB sliver appeared. No allocation strategy eliminates this. Best fit shrinks the leftover sliver and therefore shatters memory into finer pieces; worst fit tries to preserve large runs and burns through the big holes faster. As long as process sizes vary, there is no reason for hole sizes and request sizes to line up.
Compaction solves the problem in principle. Push every live process to one side and the 530KB merges into a single run. The problem is the cost. Moving a process means physically copying all of its memory, and the process cannot run while that copy is in flight. Move several gigabytes and you get a pause measured in seconds. Furthermore, the relocation register has to be updated afterwards, so execution-time binding is a precondition. A program whose addresses were fixed at compile time or load time cannot be moved at all.
Internal fragmentation is a different animal. It happens deterministically the moment you fix the allocation unit, and the average waste can be computed in advance. With 4 KiB pages, roughly 2 KiB is wasted per process in its final page: if request sizes are spread evenly relative to the page boundary, the last page is on average only half full. Raising the page size improves the translation efficiency discussed later, but it grows this waste in step. Which side you take is decided by the workload.
Paging
Paging is a technique that allocates logical address space non-contiguously, completely eliminating external fragmentation.
Basic Concepts
- Page: Fixed-size blocks of logical memory
- Frame: Same-size blocks of physical memory
- Page Table: Table mapping pages to frames
[Paging Address Translation]
Logical address = Page number(p) + Page offset(d)
Example: Page size 4KB (2^12), 32-bit logical address
Upper 20 bits = Page number (max 2^20 = 1M pages)
Lower 12 bits = Offset (0 ~ 4095)
+--------+--------+
| p (20) | d (12) | Logical address
+--------+--------+
|
v
[Page Table]
p -> f (frame number)
|
v
+--------+--------+
| f (20) | d (12) | Physical address
+--------+--------+
[Paging Example]
Logical Memory (4 pages): Physical Memory (8 frames):
+------+ +------+
|Page 0| ----+ | | Frame 0
+------+ | +------+
|Page 1| --+ | |Page 2| Frame 1
+------+ | | +------+
|Page 2| -+| | | | Frame 2
+------+ || | +------+
|Page 3| || +------------>|Page 0| Frame 3
+------+ || +------+
|+--------------->|Page 1| Frame 4
| +------+
+---------------->|Page 2| Frame 5 (X)
+------+
|Page 3| Frame 6
+------+
| | Frame 7
+------+
Page Table:
Page 0 -> Frame 3
Page 1 -> Frame 4
Page 2 -> Frame 1
Page 3 -> Frame 6
Following One Address All the Way Through
The diagram above only shows that pages correspond to frames. Let us put real numbers in and follow what arithmetic actually happens when the CPU issues one address. Assume 4 KiB pages and a 32-bit logical address.
A 4 KiB page fixes how many bits are needed to point at a byte inside a page. 4096 is 2 to the 12th, so the offset is exactly 12 bits. That 12 is not a designer's choice; it falls out of the page size. In a 32-bit address, once the low 12 bits go to the offset, the remaining upper 20 bits become the page number.
[Translating logical address 0x00004A3C]
Logical addr: 0000 0000 0000 0000 0100 1010 0011 1100 (0x00004A3C)
|<------ upper 20 bits ---->|<- 12 bits ->|
1) offset d = low 12 bits
0xA3C = 2620
(check: 0x4A3C = 19004; 19004 mod 4096 = 2620)
2) page number p = upper 20 bits
0x00004A3C >> 12 = 4
(check: 19004 div 4096 = 4)
3) Read entry 4 from the page table
valid bit 0 -> page fault here, trap into the OS
valid bit 1 -> we get frame number f. Here f = 9
4) physical addr = (f * page size) + d
= (9 * 4096) + 2620
= 36864 + 2620
= 39484 (0x00009A3C)
Two things are worth noticing. First, the offset passes through untranslated. Pages and frames are the same size, which is why the low three hex digits A3C survive into the result unchanged. Second, real hardware does this with a bit shift, not a multiply. That is precisely why page sizes are powers of two: the address can be split by wiring alone, with no divider or multiplier.
This translation happens on every single memory touch the program makes: once to fetch the instruction, and again if that instruction reads data. But the page table itself lives in memory, so a naive implementation turns one memory access into two. That means the program runs exactly twice as slow, and that is the reason the TLB exists.
TLB (Translation Lookaside Buffer)
Looking up the page table in memory every time doubles memory accesses. The TLB serves as a cache for the page table.
[Address Translation via TLB]
CPU --logical addr(p, d)--> TLB lookup
|
+---------------+---------------+
| |
TLB Hit TLB Miss
(fast, ~1ns) (slow)
| |
Get frame f Page table lookup
| Get frame f
| Add to TLB
| |
+---------------+---------------+
|
Access memory with
physical addr (f, d)
Effective Access Time (EAT) calculation:
TLB hit rate = 99% (typical)
Memory access time = 100ns
TLB access time = 10ns
EAT = 0.99 * (10 + 100) + 0.01 * (10 + 100 + 100)
= 0.99 * 110 + 0.01 * 210
= 108.9 + 2.1
= 111ns
Without TLB: 200ns (2 memory accesses)
With TLB: 111ns (44.5% improvement)
Checking by Hand Why the EAT Formula Has That Shape
Why the EAT formula looks the way it does becomes obvious once you count how many times memory is actually touched on a miss.
On a hit, the hardware probes the TLB once (10ns in the example above) and reads the data once at the resulting physical address (100ns), for 110ns. On a miss, it probes the TLB and learns the entry is absent (10ns), goes to memory once to read the page table (100ns), and then goes to memory again with the resulting physical address to read the data (100ns), for 210ns. So the miss cost is the hit cost plus one memory access, and EAT is nothing more than those two values weighted by the hit rate.
Let us redo it with different numbers. On a machine where the hit rate drops to 98 percent, memory access is 80ns, and TLB access is 1ns:
[Hit rate 98%, memory 80ns, TLB 1ns]
hit cost = 1 + 80 = 81ns
miss cost = 1 + 80 + 80 = 161ns
EAT = 0.98 * 81 + 0.02 * 161
= 79.38 + 3.22
= 82.6ns
With no TLB at all: 80 + 80 = 160ns
Overhead vs the ideal 81ns = 82.6 / 81 = about 1.02x
If the hit rate falls to 90%:
EAT = 0.90 * 81 + 0.10 * 161
= 72.9 + 16.1
= 89.0ns
Overhead = 89.0 / 81 = about 1.10x
The gap between a 98 percent and a 90 percent hit rate is only 8 percentage points, yet overhead goes from 2 percent to 10 percent, a fivefold increase. That is because one miss costs nearly twice what a hit costs, and it is exactly why people say the last few percent of cache hit rate are unusually expensive.
A TLB holds tens to hundreds of entries, which bounds how much memory it can cover. A TLB holding 64 entries for 4 KiB pages covers only 256 KiB at a time. A program that randomly sweeps a region larger than that sees its hit rate collapse. This is where increasing the page size helps: the same number of entries covers a far wider range. The price is the increased internal fragmentation described earlier.
Page Table Structures
When a process's address space is large (e.g., 64-bit), the page table itself becomes very large.
How large becomes clear if you just multiply it out. According to the Linux kernel documentation, the virtual address widths currently supported on x86-64 are 48-bit and 57-bit. With 4 KiB pages over a 48-bit address space, the page count is 2 to the 36th, roughly 68.7 billion. Even assuming an 8-byte entry, one table is 512 GiB, and one is needed per process.
[Size of a flat page table]
48-bit virtual address, 4 KiB (2^12) pages:
page count = 2^48 / 2^12 = 2^36 = 68,719,476,736 pages
entry size = assume 8 bytes
table size = 2^36 * 8 = 2^39 bytes = 512 GiB
Even if a process really uses only 10 MiB,
the table would have to reserve 512 GiB up front.
For a 57-bit virtual address:
page count = 2^57 / 2^12 = 2^45
table size = 2^45 * 8 = 2^48 bytes = 256 TiB
This absurd situation, where the page table dwarfs physical memory, is the reason hierarchy exists. The key observation is that address spaces are sparse. A process uses a tiny slice of its 48-bit space, and huge empty gaps sit between the code region, the heap, and the stack. A hierarchy shrinks the table by simply never creating the lower-level tables that correspond to those gaps. Marking the entry in the upper table as absent makes the entire subtree that would have hung below it disappear.
Hierarchical Page Table (Multi-level Page Table)
[Two-level Page Table]
32-bit address, 4KB pages:
+--------+--------+--------+
| p1(10) | p2(10) | d(12) |
+--------+--------+--------+
Outer Page Table (Level 1)
+---+
| 0 |---> Level 2 Table A
+---+ +---+
| 1 |--+ | 0 |--> Frame number
+---+ | +---+
| 2 | | | 1 |--> Frame number
+---+ | +---+
| | ...|
| +---+
|
+-> Level 2 Table B
+---+
| 0 |--> Frame number
+---+
| ...|
+---+
Advantage: Level 2 tables for unused regions are not created
-> Memory savings
The x86-64 Page Walk
The Linux kernel documentation names the page table levels, from the top down, PGD (Page Global Directory), P4D (Page Level 4 Directory), PUD (Page Upper Directory), PMD (Page Middle Directory), and PTE (Page Table Entry). P4D was introduced to accommodate five-level page tables; in a four-level configuration, PUD takes that slot. Hardware vendor manuals call the same levels by different names, but here we use the kernel documentation's names, since those are the ones verified.
The same kernel documentation explains that the original x86-64 was limited by four-level paging to 256 TiB of virtual address space, and that five-level paging bumps the limit to 128 PiB. Even on a five-level machine, however, the kernel does not allocate virtual address space above 47-bit by default. It goes higher only when an application explicitly asks with a high hint address. Some programs stash their own tags in the upper bits of pointers, and widening the address space abruptly would break them.
Numbering how one address passes through four levels looks like this.
[Four-level page walk: how a 48-bit address is cut]
Split the 48-bit virtual address as 9 + 9 + 9 + 9 + 12
+--------+--------+--------+--------+------------+
| L4 (9) | L3 (9) | L2 (9) | L1 (9) | offset(12) |
+--------+--------+--------+--------+------------+
each level index is 9 bits = 512 entries per table
8 bytes * 512 entries = 4096 bytes = exactly one page
1) Read the physical address of the top table (PGD)
from the CPU's page table base register
2) Read the PGD entry at index L4 -> memory access 1
which gives the physical address of the next table
3) Read that table's entry at index L3 -> memory access 2
4) Read the next table's entry at index L2 -> memory access 3
5) Read the final entry (PTE) at index L1 -> memory access 4
this yields the frame number and the protection bits
6) Append the offset to form the physical address and
read the actual data -> memory access 5
Cost of one TLB miss = 5 memory accesses
Cost of one TLB hit = 1 memory access
The 9-bit index per level is no accident. An entry is 8 bytes, so 512 of them come to 4096 bytes, exactly one page. The page tables themselves can then be managed in page units, which makes allocation and replacement uniform.
You can also see that the EAT calculation from the previous section gets far heavier in a four-level environment. One miss demands not one extra memory access but four. Real CPUs cache intermediate-level entries separately to soften this, but why TLB-miss-heavy workloads are so slow is explained by this one diagram.
Hashed Page Table
[Hashed Page Table]
Input logical page number p to hash function
-> Maps to hash table slot
-> Search chain (linked list) for p
-> Return corresponding frame number
Useful for very large address spaces like 64-bit
Inverted Page Table
[Inverted Page Table]
Regular page table: One per process (logical -> physical)
Inverted page table: One for the system (physical frame -> process, page)
One entry for each physical memory frame:
Frame 0: (PID=5, Page=3)
Frame 1: (PID=2, Page=7)
Frame 2: (empty)
Frame 3: (PID=5, Page=0)
...
Advantage: Table size proportional to physical memory
Disadvantage: Full table search needed for translation (solved with hashing)
Swapping
A technique that moves all or part of a process to disk to free memory.
[Standard Swapping]
Main Memory Backing Store (Disk)
+---------+ +---------+
| OS | | |
+---------+ | P2's |
| P1 | <-- swap in --- | image |
+---------+ | |
| P3 | --- swap out --> | |
+---------+ +---------+
| free |
+---------+
Modern systems swap at page granularity
rather than swapping entire processes
[Page-level Swapping]
Only specific pages of a process are moved to disk:
- Swap out pages not used for a long time
- Swap in again when needed
- Foundation technology for virtual memory
Memory Protection
Memory protection in a paging environment is implemented by adding protection bits to page table entries.
[Page Table Entry Structure]
+-------+-----+-----+-----+-------+
| Frame | Valid| Read| Write| Exec |
| Number| Bit | OK | OK | OK |
+-------+-----+-----+-----+-------+
Valid bit:
1 = This page belongs to the process's logical address space
0 = Invalid page (trap raised on access)
Protection bits:
Write attempt on read-only page -> Hardware trap
Code pages: Allow execute only, deny writes
// Memory protection example: mprotect system call
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
void segfault_handler(int sig) {
printf("Segmentation fault! Attempted access to protected memory\n");
exit(1);
}
int main() {
signal(SIGSEGV, segfault_handler);
// Allocate memory in page-size units
size_t page_size = getpagesize(); // Usually 4096
void *ptr = aligned_alloc(page_size, page_size);
// Write data
*(int *)ptr = 42;
printf("Value: %d\n", *(int *)ptr);
// Protect memory as read-only
mprotect(ptr, page_size, PROT_READ);
// Write attempt -> Segmentation fault!
*(int *)ptr = 100;
free(ptr);
return 0;
}
Failure Cases and Pitfalls
Memory problems usually arrive as the vague report that the machine is slow. If you have a fixed order for separating the symptom into numbers, you get to the cause in minutes. The commands below are for Linux; vmstat and free ship in the procps-ng package.
Symptom 1: The Machine Is Broadly Slow and the Disk Keeps Spinning
The first thing to check is whether you are swapping. Run vmstat at one-second intervals.
vmstat 1
Example output.
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
r b swpd free buff cache si so bi bo in cs us sy id wa st
2 1 512340 81234 12044 240188 184 392 2210 1180 1420 3100 12 8 41 39 0
1 2 528900 76120 11980 231044 256 512 2680 1420 1510 3320 11 9 38 42 0
3 1 541220 72880 11902 226310 312 604 3010 1690 1620 3480 10 10 35 45 0
The man page describes the fields as follows. si is "Amount of memory swapped in from disk (/s)" and so is "Amount of memory swapped to disk (/s)." In the memory section, swpd is "the amount of swap memory used," free is "the amount of idle memory," buff is "the amount of memory used as buffers," and cache is "the amount of memory used as cache."
The verdict is simple. If si and so stay nonzero, you are swapping right now. Conversely, a large swpd with si and so at zero just means pages evicted in the past are still sitting in swap, and nothing is wrong at the moment. Missing that distinction and panicking at the swpd number alone is a common mistake. In the output above, so keeps climbing and the wa column, which is I/O wait, sits near 40, so memory is short, pages are being pushed to disk, and the CPU is idling while it waits on that disk.
Symptom 2: free Is Nearly Zero, but Is Memory Really Short?
This is where the most common misreading happens.
free -h
Example output.
total used free shared buff/cache available
Mem: 15Gi 4.2Gi 324Mi 210Mi 11Gi 10Gi
Swap: 8.0Gi 501Mi 7.5Gi
A free column of 324 MiB does not mean memory is gone. According to the man page, buff/cache is the sum of buffers and cache, and available is an "Estimation of how much memory is available for starting new applications, without swapping." The kernel fills spare memory with page cache and reclaims it on demand, so the number to look at is available, not free. The output above has 10 GiB left, which is comfortable. The same document states that used is calculated as total minus available. The -h option scales each value to the shortest three-digit unit and attaches unit labels such as B, Ki, Mi, Gi, Ti, and Pi.
Symptom 3: A Process Vanished Without a Single Log Line
If the application log shows no sign of shutdown and the exit code the shell reports points at SIGKILL, the kernel most likely killed it. Look at the kernel ring buffer.
dmesg -T | grep -i -E 'out of memory|oom'
Example output.
[Sat Aug 15 04:12:31 2026] myserver invoked oom-killer: order=0, oom_score_adj=0
[Sat Aug 15 04:12:31 2026] Out of memory: Killed process 4711 (myserver)
total-vm:8394204kB, anon-rss:7912044kB, file-rss:0kB
The exact wording varies by kernel version, so treat the output above as an illustration of the shape rather than an exact string. What is certain is that the kernel decides which process to kill by a score. The man page describes /proc/PID/oom_score as "the current score that the kernel gives to this process for the purpose of selecting a process for the OOM-killer." The score mainly reflects memory usage, and the oom_score_adj setting adjusts it.
To find out how much a given process actually uses, look at its memory map. According to the man page, pmap reports "the memory map of a process or processes," with the syntax pmap [option ...] pid .... -x shows the extended format and -X shows even more detail, though the documentation warns that the format of -X changes according to /proc/PID/smaps.
getconf PAGESIZE
pmap -x 4711 | tail -3
Example output.
4096
Address Kbytes RSS Dirty Mode Mapping
...
total kB 8394204 7912044 7910020
The value getconf PAGESIZE returns is a POSIX-defined system configuration value. The man page defines PAGESIZE as "Size of a page in bytes. Must not be less than 1." and states that PAGE_SIZE is a synonym for it. You need this value to know how many offset bits the earlier arithmetic uses, and to divide out how many pages a process actually occupies.
When This No Longer Applies
Half of this chapter is about contiguous memory allocation, and no general-purpose operating system in use today allocates that way. Linux, Windows, and macOS all use paging; none of them place an entire process in a contiguous run chosen by first fit or best fit. External fragmentation made the approach impractical, and paging is precisely what was invented to remove that problem.
There are still two reasons to learn this material. One is that understanding what paging solved requires knowing the state of things before it was solved. The other is that contiguous allocation is still alive in specific places.
The first such place is embedded systems and real-time operating systems that have no MMU or do not use one. With no address translation at all, there is no option other than carving physical memory into regions and handing them out. Real-time systems sometimes prefer it outright: a constant access time is better than not knowing when a page fault will strike.
The second place lives inside modern systems. Buffers a device reads and writes directly via DMA often have to be physically contiguous, and reserving huge pages up front is ultimately about securing a large contiguous run. This chapter also explains why such reservations succeed more often right after boot: the longer a system runs, the more physical memory fragments, and the harder large contiguous runs become to find.
The paging half of this chapter, by contrast, has no expiry date. Address translation, the TLB, multi-level tables, and protection bits are running on every instruction on every server, laptop, and phone in use today. Application developers never touch page tables directly, but chase a performance problem far enough and this layer surfaces. Why code that sweeps memory sequentially is so much faster than code that sweeps it randomly, and why huge pages help only on certain workloads, are questions whose answers all live here.
References
- Linux kernel, Page Tables: https://www.kernel.org/doc/html/latest/mm/page_tables.html — verified 2026-08-16
- Linux kernel, Complete virtual memory map (x86-64): https://www.kernel.org/doc/html/latest/arch/x86/x86_64/mm.html — verified 2026-08-16
- Linux kernel, 5-level paging: https://www.kernel.org/doc/html/latest/arch/x86/x86_64/5level-paging.html — verified 2026-08-16
- vmstat(8): https://man7.org/linux/man-pages/man8/vmstat.8.html — verified 2026-08-16
- free(1): https://man7.org/linux/man-pages/man1/free.1.html — verified 2026-08-16
- pmap(1): https://man7.org/linux/man-pages/man1/pmap.1.html — verified 2026-08-16
- sysconf(3): https://man7.org/linux/man-pages/man3/sysconf.3.html — verified 2026-08-16
- proc_pid_oom_score(5): https://man7.org/linux/man-pages/man5/proc_pid_oom_score.5.html — verified 2026-08-16
Summary
Main memory management is a core function for providing efficient and safe memory space to processes. The MMU translates logical addresses to physical addresses, paging eliminates external fragmentation, and the TLB ensures address translation performance. Hierarchical page tables and inverted page tables efficiently manage large address spaces, and protection bits ensure memory isolation between processes.