These are the notes for CS Fundamentals for Placements, episode 32. Last episode you invented paging. Today the page table itself becomes the problem: it is far too big. We measure it live, then shrink it with multilevel (hierarchical) paging, hashed page tables and inverted page tables, make the TLB go further with huge pages, and then look at memory the way a programmer sees it: segmentation, the segment table with base and limit, a real segmentation fault, segmentation vs paging, segmented paging, and finally swapping and swap space. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 5 November 2026.
Recap: paging in 30 seconds
- A page is a fixed-size piece of a program's address space (here 4 KB = 4096 bytes).
- A frame is a piece of physical RAM of exactly the same size.
- The page table (one per process) says which frame holds each page.
- A virtual (logical) address splits into a page number and an offset (the byte inside the page). With 32-bit addresses and 4 KB pages, the offset is 12 bits (2^12 = 4096) and the page number is the other 20 bits.
- The MMU (memory management unit, the address-translating hardware in the CPU) replaces the page number with a frame number and keeps the offset.
- Each row of the page table is a page table entry (PTE): the frame number plus bits such as valid (this page is mapped) and dirty (this page was written).
- The TLB (translation lookaside buffer) is a small, fast cache of recent translations.
virtual address = | page number (20 bits) | offset (12 bits) |
│ page table
▼
physical address = | frame number | same offset |
Problem 1: how big is ONE page table?
A flat page table is one simple array with an entry for every page of the address space, whether the program uses it or not. Let's compute its size.
#include <stdio.h>
// One flat page table per process: one entry for EVERY page
void flat(int bits, int pte_bytes) {
unsigned long long pages = 1ULL << (bits - 12); // 4 KB pages
unsigned long long mb = (pages * pte_bytes) >> 20;
printf("%d-bit: %llu entries x %d B = %llu MB per process\n",
bits, pages, pte_bytes, mb);
}
int main(void) {
flat(32, 4);
flat(48, 8); // 524288 MB = 512 GB!
// a small program really uses only 2 MB = 512 pages
printf("used: 512 of %d entries = %.2f%%\n",
1 << 20, 512 * 100.0 / (1 << 20));
}
Output:
32-bit: 1048576 entries x 4 B = 4 MB per process
48-bit: 68719476736 entries x 8 B = 524288 MB per process
used: 512 of 1048576 entries = 0.05%
1ULL << nis 2^n as anunsigned long long(a 64-bit unsigned integer);>> 20divides by 2^20 = 1,048,576, turning bytes into MB.- 32-bit: 2^20 entries × 4 B = 4 MB per process. 100 processes = 400 MB of tables.
- 48-bit (with 8-byte entries): 2^36 entries × 8 B = 512 GB per process. Impossible.
- A small program uses about 2 MB = 512 pages, so only 0.05% of the table is useful.
- Worse: a flat table is one array, so it needs 4 MB of contiguous (side-by-side) RAM, the very problem paging was invented to escape.
Why it failed: a flat table pays for the whole address space, but real programs use only a few small regions of it (code at the bottom, the stack at the top, a big empty gap between). Such an address space is called sparse.
Fix 1: multilevel (hierarchical) paging
The story: finding a book in a huge library
| Big library | Paging |
|---|---|
| The board at the door: rows 1 to 1024, and where each row's shelf list is | Outer page table (indexed by the first part of the page number) |
| The shelf list inside each row | Inner page table (indexed by the second part; gives the frame) |
| An empty row: no shelf list is printed, the board just says "empty" | Missing inner tables: unused regions cost nothing |
| The page inside the book | The offset, unchanged |
A table of tables is called multilevel paging or hierarchical paging. The outer table is also called the page directory.
Two-level paging: split the page number
32-bit virtual address:
| p1: 10 bits | p2: 10 bits | offset: 12 bits |
outer index inner index byte in the page
p1 = va >> 22 (shift right: drop the low 22 bits)
p2 = (va >> 12) & 0x3FF (& with a mask keeps the low 10 bits)
offset = va & 0xFFF (keep the low 12 bits)
>>(shift right) moves bits to the right, dropping the ones that fall off (episode 3).&(bitwise AND) with a mask keeps only the bits that are 1 in the mask.0x3FFis ten 1 bits;0xFFFis twelve.- Why 10 + 10? 2^10 = 1024 entries × 4 B = 4096 B = exactly one page. So every table, outer or inner, fits in one frame and can be placed anywhere in RAM: no contiguous 4 MB array any more.
va ──► p1 ──► outer table[p1] ──► inner table ──► [p2] ──► frame
│
physical = frame << 12 | offset
Two-level translation in C
#include <stdio.h>
// Two-level paging, 32-bit address = 10 | 10 | 12 bits
int inner1[1024], inner3[1024]; // only 2 inner tables exist
int *outer[1024]; // outer table: 1024 pointers
void translate(unsigned va) {
unsigned p1 = va >> 22, p2 = (va >> 12) & 0x3FF, off = va & 0xFFF;
printf("0x%08X -> p1=%u p2=%u off=0x%03X", va, p1, p2, off);
if (!outer[p1]) { printf(" no inner table: page fault\n"); return; }
unsigned frame = outer[p1][p2];
printf(" frame 0x%X -> 0x%X\n", frame, frame << 12 | off);
}
int main(void) {
outer[1] = inner1; outer[3] = inner3; // the OS fills these in
inner1[3] = 0x2A5; inner3[0] = 0x07;
translate(0x00403A7C);
translate(0x00C00010);
translate(0x80000000);
printf("tables: 4 KB outer + 2 x 4 KB inner = 12 KB, flat: 4 MB\n");
}
Output:
0x00403A7C -> p1=1 p2=3 off=0xA7C frame 0x2A5 -> 0x2A5A7C
0x00C00010 -> p1=3 p2=0 off=0x010 frame 0x7 -> 0x7010
0x80000000 -> p1=512 p2=0 off=0x000 no inner table: page fault
tables: 4 KB outer + 2 x 4 KB inner = 12 KB, flat: 4 MB
outeris an array of 1024 pointers (variables holding addresses); a global array starts as all zeros, i.e.NULL(the "points nowhere" pointer).%08Xprints a number in hexadecimal, padded to 8 digits.frame << 12 | offputs the frame number in the high bits and the offset in the low 12 bits: the physical address.- Address 0x80000000 has p1 = 512, where there is no inner table: a page fault, a trap into the OS because the page is not mapped (next episode handles it properly).
- Total table memory: 12 KB instead of 4 MB.
Numerical: memory accesses and effective access time (EAT)
Every level is one more memory access. With 2 levels and no TLB, one memory reference costs 3 accesses: the outer table, the inner table, then the data. In general: levels + 1 accesses on a TLB miss.
TLB lookup = 10 ns, memory access = 100 ns, TLB hit ratio = 90%, 2 levels
TLB hit : 10 + 100 = 110 ns
TLB miss: 10 + 3 x 100 = 310 ns
EAT = 0.9 x 110 + 0.1 x 310 = 99 + 31 = 130 ns (no TLB at all: 300 ns)
The effective access time (EAT) is the average time per memory reference: hit ratio × hit time + miss ratio × miss time. The hit ratio is the fraction of lookups found in the TLB.
Numerical: how many levels?
48-bit virtual address, 4 KB pages, 8-byte entries
offset = 12 bits → page number = 48 - 12 = 36 bits
one table = 4096 / 8 = 512 entries = 2^9 → 9 bits per level
levels = 36 / 9 = 4
Real hardware does exactly this. 64-bit x86 processors (Intel and AMD) use 4-level paging with 48 address bits (bits 0 through 47), for 256 TiB of virtual address space. Intel's 5-level paging adds another 9-bit level, using bits 0 through 56 (57 bits), for 128 PiB; it first appeared in the Ice Lake processors, and Linux supports it since kernel 4.14 (source: Wikipedia, "Intel 5-level paging"). 1 TiB (tebibyte) = 2^40 bytes; 1 PiB (pebibyte) = 2^50 bytes.
The price: a TLB miss means walking 4 or 5 levels, so the TLB matters even more.
Fix 2: hashed page tables
The story: letters in pigeonholes
A hostel has 10,000 rooms but the mail room has only 8 pigeonholes. A letter goes into a pigeonhole chosen by a rule (say, the last digit of the room number). Rooms 4005 and 1235 land in the same pigeonhole, so you check each letter in it.
| Mail room | Hashed page table |
|---|---|
| The "last digit" rule | Hash function: turns a big number (the page number) into a small slot number |
| The 8 pigeonholes | The hash table; each pigeonhole is a bucket |
| Two rooms, same pigeonhole | A collision |
| Checking each letter in the pigeonhole | Searching the chain, a linked list of entries in the bucket |
Each entry holds (page number, frame number, pointer to the next entry). Only pages that are really used have entries, which suits huge, sparse 64-bit address spaces.
#include <stdio.h>
// Hashed page table: bucket = page number % 8, a chain for collisions
struct entry { unsigned page, frame; struct entry *next; };
struct entry *bucket[8];
struct entry pool[6] = {{0x4005, 12}, {0x7F21, 40}, {0x000D, 3},
{0x4015, 25}, {0x1235, 9}, {0x0010, 77}};
void lookup(unsigned page) {
int steps = 0;
for (struct entry *e = bucket[page % 8]; e; e = e->next)
if (++steps, e->page == page) {
printf("page 0x%04X: bucket %u, %d step(s) -> frame %u\n",
page, page % 8, steps, e->frame);
return;
}
printf("page 0x%04X: bucket %u, not found -> page fault\n", page, page % 8);
}
int main(void) {
for (int i = 0; i < 6; i++) { // insert at the chain's head
unsigned b = pool[i].page % 8;
pool[i].next = bucket[b]; bucket[b] = &pool[i];
}
lookup(0x7F21); lookup(0x4005); lookup(0x2222);
}
Output:
page 0x7F21: bucket 1, 1 step(s) -> frame 40
page 0x4005: bucket 5, 4 step(s) -> frame 12
page 0x2222: bucket 2, not found -> page fault
%is the remainder (modulo): 0x7F21 % 8 = 1, 0x4005 % 8 = 5.- Bucket 5 holds four pages (0x4005, 0x000D, 0x4015, 0x1235: all leave remainder 5), so 0x4005 (inserted first, now at the end of the chain) takes 4 steps.
++steps, e->page == pageuses the comma operator: count a step, then compare.- Lesson: a good hash function spreads pages evenly so chains stay short. A variant, the clustered page table, stores several neighbouring pages in one entry.
Fix 3: inverted page tables
The story: one register for the parking lot
| Housing society parking | Inverted page table |
|---|---|
| Every flat keeps its own list of parked cars (200 flats = 200 lists) | Per-process page tables (100 processes = 100 tables) |
| One guard's register: one row per parking spot, "spot 7 → flat B2's car" | One entry per physical frame: (process ID, page number) |
| To find B2's car, read the register line by line | Finding a page means searching the table |
An inverted page table (IPT) has exactly one entry per frame of physical memory. Entry i says which process (by its PID, process ID) and which page of that process is in frame i. The frame number is the entry's position. Wikipedia: "The IPT combines a page table and a frame table into one data structure", and "Inverted page tables are used for example on the PowerPC, the UltraSPARC and the IA-64 architecture."
#include <stdio.h>
// Inverted page table: ONE entry per physical FRAME, for all processes
struct { int pid; unsigned page; } ipt[8] = {
{1, 0x10}, {2, 0x10}, {1, 0x11}, {3, 0x05},
{2, 0x3A}, {1, 0x7F}, {3, 0x06}, {2, 0x11}};
void find(int pid, unsigned page) {
for (int frame = 0; frame < 8; frame++) // search every entry
if (ipt[frame].pid == pid && ipt[frame].page == page) {
printf("pid %d page 0x%02X -> frame %d (searched %d)\n",
pid, page, frame, frame + 1);
return;
}
printf("pid %d page 0x%02X -> not in RAM: page fault (searched 8)\n",
pid, page);
}
int main(void) {
find(1, 0x10); find(2, 0x10); find(2, 0x11); find(3, 0x99);
printf("table size = number of frames = 8, however many processes\n");
}
Output:
pid 1 page 0x10 -> frame 0 (searched 1)
pid 2 page 0x10 -> frame 1 (searched 2)
pid 2 page 0x11 -> frame 7 (searched 8)
pid 3 page 0x99 -> not in RAM: page fault (searched 8)
table size = number of frames = 8, however many processes
| Per-process page table | Inverted page table | |
|---|---|---|
| Entries | one per page, for each process | one per frame, for the whole system |
| Indexed by | page number | frame number |
| Size grows with | number of processes × address space | physical RAM only |
| Lookup | direct index (fast) | search for (PID, page): slow, so real systems add a hash table and rely on the TLB |
| Shared pages | easy (two PTEs point at one frame) | hard: each frame records only one owner |
Fix 4: huge pages (for the TLB)
The TLB holds only a limited number of translations. A program that touches 1 GB of data:
| Page size | Pages for 1 GB | TLB entries needed |
|---|---|---|
| 4 KB (normal) | 1 GB / 4 KB = 262,144 | 262,144 |
| 2 MB (huge) | 1 GB / 2 MB = 512 | 512 |
| 1 GB (huge) | 1 | 1 |
A huge page is a page much larger than the normal size. One TLB entry then covers far more memory (fewer TLB misses), and the page walk is shorter. The Linux kernel documentation says "x86 CPUs normally support 4K and 2M (1G if architecturally supported) page sizes." The price is internal fragmentation: a half-used huge page wastes the rest of it (episode 30). Databases and virtual machines are typical users.
Segmentation: the programmer's view
The story: a school bag with compartments
| School bag | Segmentation |
|---|---|
| Slicing the bag into equal slices (a slice may hold half a lunchbox) | Paging: equal 4 KB pages, blind to what's inside |
| Compartments: books, lunchbox, water bottle | Segments: code, data, stack, heap |
| Each compartment has its own size | Each segment has a base and a limit |
| "Nobody writes in the textbook" | Protection per segment (code read-only, stack read-write) |
Segmentation divides a program's memory into segments: variable-size logical parts that match how the programmer thinks of the program: the code (instructions), the data (global variables), the stack (function calls and local variables), the heap (memory from malloc).
The segment table
- A logical address is a pair: (segment number, offset).
- The segment table has one row per segment: base (where it starts in physical memory) and limit (its length).
- Translation: if
offset < limit, physical = base + offset; otherwise trap (addressing error). This is where the name segmentation fault comes from. - The STBR (segment-table base register) says where the segment table is in memory; the STLR (segment-table length register) says how many segments the process has (segment number must be < STLR).
(s, d) ──► segment table[s] = (base, limit)
d < limit ? ── no ──► TRAP: addressing error
│ yes
▼
physical = base + d
#include <stdio.h>
// Segmentation: address = (segment number, offset)
const char *name[3] = {"code", "data", "stack"};
int base[3] = {4000, 9000, 15000}; // where each segment starts
int limit[3] = {1200, 600, 2000}; // how long each segment is
void translate(int s, int offset) {
printf("(%-5s, %4d) -> ", name[s], offset);
if (offset >= limit[s]) {
printf("TRAP: limit is %d, segmentation fault\n", limit[s]);
return;
}
printf("physical %d\n", base[s] + offset);
}
int main(void) {
translate(0, 100); translate(1, 599);
translate(2, 1500); translate(1, 750);
}
Output:
(code , 100) -> physical 4100
(data , 599) -> physical 9599
(stack, 1500) -> physical 16500
(data , 750) -> TRAP: limit is 600, segmentation fault
%-5s prints a string left-aligned in 5 characters; %4d prints a number right-aligned in 4. Offset 599 is the last legal byte of the 600-byte data segment; 750 traps.
A real segmentation fault: writing to read-only memory
#include <stdio.h>
int main(void) {
char *word = "hello"; // text stored in a READ-ONLY area
printf("word = %s, now changing the first letter...\n", word);
fflush(stdout);
word[0] = 'H'; // try to write to read-only memory
printf("word = %s\n", word);
}
Output:
word = hello, now changing the first letter...
Segmentation fault
A string literal (text in double quotes) is stored in a read-only area next to the code. The memory exists, but its protection says read-only, so the hardware traps the write and the OS stops the program (signal SIGSEGV, exit code 139). fflush(stdout) pushes the first line out before the crash. Fix: char word[] = "hello"; makes a writable copy in an array, and then word[0] = 'H' prints word = Hello.
Segmentation vs paging
| Paging | Segmentation | |
|---|---|---|
| Piece size | fixed (e.g. 4 KB) | varies (each segment its own length) |
| Visible to the programmer? | no | yes: matches code, data, stack |
| Address | page number + offset | (segment number, offset) |
| Table | page table (frame per page) | segment table (base + limit) |
| Waste | internal fragmentation (last page) | external fragmentation (holes between segments) |
| Protection and sharing | per page | per segment (natural: share the code segment) |
Because segments have different sizes, placing them in RAM brings back variable partitions and external fragmentation (episode 30).
Segmented paging: segments made of pages
Segmented paging splits every segment into pages. The address has three parts:
| segment s | page p | offset d |
s → segment table entry: limit + address of THAT segment's page table
p → the segment's page table → frame
physical = frame + d
Numerical: offsets inside a segment are 16 bits and pages are 1 KB (1024 bytes, 10 bits). Then p = offset / 1024 (6 bits) and d = offset % 1024 (10 bits). For (segment 2, offset 5000): p = 5000 / 1024 = 4, d = 5000 − 4096 = 904. Page 4, byte 904 of segment 2.
You keep the programmer's segments with their own protection, and since every piece is a page, there is no external fragmentation (only a little internal fragmentation in each segment's last page).
Swapping and swap space
The story: a full dining hall
| Dining hall | OS |
|---|---|
| Every table is taken, a new family arrives | RAM is full, a new process needs memory |
| A family waiting for dessert moves to the lobby | Swap out: copy a process (or pages) from RAM to disk |
| The lobby | Swap space (the backing store): a reserved area on disk |
| The family returns to any free table | Swap in: copy it back, possibly to a different place |
Swapping moves a process temporarily out of RAM to the backing store and later back in. Swapping in at a different address needs execution-time binding (episode 30). The medium-term scheduler (episode 17) decides which process to swap out.
Numerical: a 100 MB process, disk transfer rate 50 MB/s. Swap out = 100 / 50 = 2 s; swap in = 2 s; total 4 s of copying.
Whole-process swapping is very slow, so modern systems with paging swap individual pages that haven't been used for a while (next episode: demand paging).
The whole chain
| Step | Obvious attempt | What broke | Fix |
|---|---|---|---|
| 1 | One flat page table | 4 MB per process (512 GB at 48 bits), 0.05% used, needs contiguous RAM | Multilevel paging (12 KB instead of 4 MB) |
| 2 | More and more levels | 4-5 memory accesses on a TLB miss | Hashed page table (only used pages) |
| 3 | One table per process | 100 processes = 100 tables | Inverted page table (one entry per frame) |
| 4 | 4 KB pages for 1 GB of data | 262,144 TLB entries needed | Huge pages (512 or 1) |
| 5 | Blind equal slices | Doesn't match code/data/stack; no per-part protection | Segmentation (base, limit, protection) |
| 6 | Variable-size segments | External fragmentation | Segmented paging |
| 7 | RAM is full | No room for a new process | Swapping to swap space |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Writing to a string literal (char *w = "hello"; w[0] = 'H';) |
Segmentation fault |
The text is in read-only memory | char w[] = "hello"; |
| Treating offset = limit as legal | Wrong numerical answer | Legal offsets are 0 .. limit − 1 | Legal only if offset < limit |
| "Two-level paging = two memory accesses" | Wrong EAT | The data access is extra | Levels + 1 accesses on a TLB miss |
| Searching an inverted table by page number only | Wrong frame | Many processes have a page 0x10 | Search for (PID, page) |
Splitting with the wrong shift (e.g. va >> 20 for p1) |
Wrong p1/p2 | p1 is the top 10 bits | p1 = va >> 22, p2 = (va >> 12) & 0x3FF |
| Saying segmentation has internal fragmentation | Wrong theory answer | Segments are exactly sized | Segmentation → external; paging → internal |
Forgetting 1ULL in 1 << 36 |
Wrong or undefined result (int is 32 bits) |
Shifting an int by ≥ 32 |
Use 1ULL << 36 |
Mini project: a two-level page table with a TLB
Write a C program that simulates a 32-bit, 10 | 10 | 12 two-level page table. Commands from stdin: map VA FRAME (create the inner table on demand, then set the entry), read VA (translate; print "page fault" for unmapped addresses) and stats. Add a 4-entry TLB with LRU replacement in front of it, count TLB hits, misses and memory accesses, and print the EAT for TLB = 10 ns, memory = 100 ns. Finally print the memory used by your tables and compare it with a flat 4 MB table.
Practice
1. 32-bit addresses, 8 KB pages, 4-byte PTEs. How big is a flat page table?
Solution
8 KB = 2^13, so the offset is 13 bits and the page number is 32 − 13 = 19 bits. Entries = 2^19 = 524,288. Size = 524,288 × 4 B = 2 MB.
2. Segment 2 has base 3000 and limit 400. Map offsets 350 and 420.
Solution
350 < 400 → physical 3000 + 350 = 3350. 420 ≥ 400 → trap (addressing error / segmentation fault).
3. A hashed page table with 4 buckets (bucket = page % 4), inserting at the head. Insert pages 6, 10, 3, 14. Draw the chains.
Solution
6 % 4 = 2, 10 % 4 = 2, 3 % 4 = 3, 14 % 4 = 2. Bucket 2: 14 → 10 → 6. Bucket 3: 3. Buckets 0 and 1 are empty. Looking up page 6 takes 3 steps.
4. Why do inverted page tables make shared memory hard?
Solution
Each entry stores exactly one (PID, page) owner for its frame. Shared memory means two processes map the same frame, which a single entry can't record. Systems need an extra structure (or allow only one mapping at a time, causing page faults when the other process uses it).
5. Two-level paging, 32-bit, 10 | 10 | 12, 4-byte entries. A process uses the lowest 8 MB of its address space and the top 4 MB (its stack). How much memory do its page tables need?
Solution
One inner table covers 1024 pages × 4 KB = 4 MB. The lowest 8 MB needs 2 inner tables, the top 4 MB needs 1. Total = outer 4 KB + 3 × 4 KB = 16 KB (a flat table: 4 MB).
6. Three-level paging, TLB = 20 ns, memory = 100 ns, hit ratio = 80%. EAT?
Solution
Hit = 20 + 100 = 120 ns. Miss = 20 + 3 × 100 + 100 = 420 ns (three tables + data). EAT = 0.8 × 120 + 0.2 × 420 = 96 + 84 = 180 ns.
7. 39-bit virtual addresses, 4 KB pages, 8-byte entries, each table one page. How many levels?
Solution
Page number = 39 − 12 = 27 bits. Entries per table = 4096 / 8 = 512 = 9 bits. Levels = 27 / 9 = 3.
8. Segmented paging with 1 KB pages: segment 1, offset 3100. Page number and d?
Solution
p = 3100 / 1024 = 3 (3 × 1024 = 3072), d = 3100 − 3072 = 28.
Quick quiz
32-bit virtual address, 4 KB pages
split: p1 = 10 bits, p2 = 10 bits,
offset = 12 bits
virtual address = 0x00801005
// what are p1, p2 and the offset?
A. p1 = 8, p2 = 1, offset = 0x005 B. p1 = 2, p2 = 1, offset = 0x005 C. p1 = 2, p2 = 0, offset = 0x1005 D. p1 = 0, p2 = 0x801, offset = 0x005
Answer
B. 0x00801005 >> 22 = 2. (0x00801005 >> 12) = 0x801, and 0x801 & 0x3FF = 1. 0x00801005 & 0xFFF = 0x005.
Interview questions
- Why is a single-level page table a problem? It needs an entry for every page of the address space: 4 MB per process for 32-bit (4 KB pages, 4 B entries), 512 GB for 48-bit; most entries are unused, and it needs contiguous memory.
- How does multilevel paging save memory? The outer table points to inner tables; inner tables for unused regions are never created, and each table fits in one page.
- What is the cost of multilevel paging? One extra memory access per level on a TLB miss (levels + 1 total); the TLB hides most of it.
- How many levels does x86-64 use? Four (48-bit addresses, 9 bits per level + 12-bit offset); Intel's 5-level paging extends to 57 bits.
- What is a hashed page table? A hash table keyed by the virtual page number, with chains of (page, frame, next) for collisions; good for sparse 64-bit address spaces.
- What is an inverted page table? Pros and cons? One entry per physical frame storing (PID, page). Size depends only on RAM; but lookups need a search (hash + TLB) and sharing pages is hard.
- What are huge pages and why use them? Pages of 2 MB or 1 GB (on x86) instead of 4 KB; one TLB entry covers more memory, so fewer TLB misses; the cost is internal fragmentation.
- What is segmentation? Dividing memory into variable-size logical segments (code, data, stack, heap); addresses are (segment, offset), translated with a segment table of base and limit.
- What causes a segmentation fault? Accessing memory outside the allowed range or with the wrong permission (e.g. writing to read-only memory); the hardware traps and the OS sends SIGSEGV.
- Paging vs segmentation? Fixed vs variable size; invisible vs programmer-visible; internal vs external fragmentation; page table vs segment table.
- What is segmented paging? Each segment is divided into pages, with a page table per segment: the programmer's view without external fragmentation.
- What is swapping? What is swap space? Moving a process (or pages) out of RAM to disk and back; swap space (backing store) is the disk area that holds them.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Page | Fixed-size piece of a program's address space | 4 KB |
| Frame | Piece of RAM the same size as a page | frame 0x2A5 |
| Page table | Table mapping each page to its frame, one per process | page 3 → frame 0x2A5 |
| Page table entry (PTE) | One row of a page table: frame + bits | frame, valid, dirty |
| Valid bit / dirty bit | "This page is mapped" / "this page was written" | |
| Offset | Byte position inside a page or segment | 0xA7C |
| MMU | Hardware that translates virtual addresses to physical ones | |
| TLB | Small fast cache of recent translations | |
| Flat (single-level) page table | One array with an entry for every page | 4 MB for 32-bit |
| Sparse address space | Address space where only a few regions are used | code at bottom, stack at top |
| Contiguous | Side by side in memory, one unbroken block | a 4 MB array |
| Multilevel (hierarchical) paging | Page tables arranged as a table of tables | two-level 10 | 10 | 12 |
| Two-level paging | Page number split into outer and inner indices | p1, p2 |
| Outer page table (page directory) | First-level table; points to inner tables | outer[1024] |
| Inner page table | Second-level table; gives the frame | inner1[1024] |
Shift right (>>) |
Move bits right, dropping the low ones | va >> 22 |
Bitwise AND with a mask (&) |
Keep only the bits that are 1 in the mask | va & 0xFFF |
| Page fault | Trap to the OS because a page isn't mapped or not in RAM | p1 = 512, no inner table |
| Effective access time (EAT) | Average time per memory reference | 130 ns |
| Hit ratio | Fraction of lookups found in the TLB | 90% |
| 4-level / 5-level paging | x86 64-bit schemes using 48 / 57 address bits | 256 TiB / 128 PiB |
| TiB, PiB | Tebibyte = 2^40 bytes; pebibyte = 2^50 bytes | |
| Hash function | Rule turning a big key into a small slot number | page % 8 |
| Hash table | Array of buckets addressed by a hash function | 8 buckets |
| Bucket | One slot of a hash table | bucket 5 |
| Collision | Two keys hashing to the same bucket | 0x4005 and 0x1235 |
| Chain (chaining) | Linked list of all entries in one bucket | 4 entries in bucket 5 |
| Linked list | Items where each points to the next | e->next |
| Hashed page table | Page table stored as a hash table keyed by page number | |
| Clustered page table | Hashed table whose entries cover several neighbouring pages | |
| Inverted page table (IPT) | One entry per physical frame: (PID, page) | ipt[8] |
| PID (process ID) | The number that names a process | pid 2 |
| Shared page | One frame mapped by several processes | shared library code |
| Huge page | A page much larger than normal | 2 MB, 1 GB |
| Internal fragmentation | Wasted space inside an allocated block | half-used huge page |
| External fragmentation | Free memory split into holes between blocks | between segments |
| Segmentation | Dividing memory into variable-size logical segments | code, data, stack |
| Segment | One logical part of a program | the stack |
| Code / data / stack / heap | Instructions / globals / function calls and locals / malloc memory |
|
| Segment table | Table of (base, limit) per segment | data: 9000, 600 |
| Segment base | Where a segment starts in physical memory | 9000 |
| Segment limit | Length of a segment; offset must be below it | 600 |
| STBR / STLR | Registers holding the segment table's address / number of segments | |
| Trap | Interrupt caused by the running program, handing control to the OS | offset 750 |
| Segmentation fault (SIGSEGV) | OS stopping a program that touched memory illegally | writing to "hello" |
| String literal | Text in double quotes in C code, stored read-only | "hello" |
| Read-only memory region | Memory that may be read but not written | where literals live |
| Protection bits | Permission bits (read, write, execute) per page or segment | code: read + execute |
| Segmented paging | Segments divided into pages, a page table per segment | (s, p, d) |
| Swapping | Moving a process (or pages) between RAM and disk | swap out, swap in |
| Swap out / swap in | Copy from RAM to disk / back to RAM | 2 s each |
| Swap space (backing store) | Disk area reserved for swapped-out memory | swap partition |
| Medium-term scheduler | OS part that decides which process to swap out | episode 17 |
| Execution-time binding | Addresses translated on every access, so a process can move | episode 30 |
Summary
- A flat page table is huge and mostly empty: 4 MB per process at 32 bits, 512 GB at 48 bits, only 0.05% used (live).
- Multilevel paging (10 | 10 | 12) builds a table of tables; unused regions need no inner tables: 12 KB instead of 4 MB (live). Each level costs a memory access (levels + 1 on a TLB miss); the TLB hides it (EAT 130 ns). x86 64-bit: 4 levels, 48 bits; 5-level paging: 57 bits.
- Hashed page tables store only used pages in buckets with chains (live: a 4-entry chain). Inverted page tables keep one entry per frame, (PID, page), searched (live); size depends only on RAM, but sharing is hard.
- Huge pages (2 MB, 1 GB) let one TLB entry cover far more memory.
- Segmentation gives memory the programmer's shape: (segment, offset), segment table with base and limit, trap if offset ≥ limit (live), per-segment protection (live: writing to a string literal →
Segmentation fault). It suffers external fragmentation, fixed by segmented paging. - Swapping moves processes or pages to swap space on disk when RAM is full; whole-process swapping is slow (100 MB at 50 MB/s = 4 s).
Next episode: Virtual memory and demand paging: page faults, demand paging, copy-on-write, thrashing and the working set.