These are the notes for CS Fundamentals for Placements, episode 31. Last episode, giving every program one unbroken stretch of RAM (contiguous allocation) ended in external fragmentation: 400 K free, yet a 350 K program could not run. Today we fix that for good with paging: pages, frames, the page table, the page number and page offset, logical-to-physical address translation, page table entry bits (valid, protection, dirty, reference), the page-table base register (PTBR), page table size numericals, page size trade-offs and shared pages. Then we make paging fast with the TLB: TLB hits and misses, the hit ratio, effective access time (EAT) numericals, the TLB flush and the ASID. 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. All outputs are deterministic.
The problem: memory in pieces
From episode 30: 1000 K of RAM held programs A (300 K), B (200 K), C (300 K) and D (200 K). B and D finished:
| A 300K | hole 200K | C 300K | hole 200K |
- 400 K is free in total, but a 350 K program fails: no single hole (free gap) is big enough. Free memory chopped into pieces between processes is external fragmentation.
- Compaction (sliding programs together so the holes join) works, but copying hundreds of megabytes stops everything.
The root cause is the rule "one program = one unbroken stretch". What if a program could live in pieces, scattered anywhere?
The idea: paging
The story: a big family on a train
| Railway booking | Paging |
|---|---|
| A family of 14 can't get 14 berths side by side, so it is split into groups of 8 (group 0, group 1) | The OS cuts a program's logical memory into equal fixed-size pieces: pages |
| Every coach has exactly 8 berths; a group goes into any coach with space | RAM is cut into slots exactly one page big: frames; any page goes into any free frame |
| A reservation chart: group 0 → coach S4, group 1 → coach S9 | A page table per process: page 0 → frame 5, page 1 → frame 2 |
| Berth 5 stays berth 5 in whichever coach you land | The offset (position inside the page) stays the same inside the frame |
Definitions
- Page: a fixed-size block of a process's logical address space (the addresses the program sees, from episode 30).
- Frame (page frame): a fixed-size block of physical memory (real RAM), exactly the same size as a page.
- Page table: a table, one per process, with one entry per page, giving the frame number that holds that page.
- Paging: the memory-management scheme that lets a process's physical memory be non-contiguous: its pages sit in any free frames.
logical memory page table physical memory (frames)
page 0 ───────► 0 │ 5 │ ───────► frame 5
page 1 ───────► 1 │ 2 │ ───────► frame 2
page 2 ───────► 2 │ 7 │ ───────► frame 7
What paging fixes and what it costs:
| Contiguous allocation (ep 30) | Paging | |
|---|---|---|
| External fragmentation | Yes: holes between processes | None: any free frame can be used |
| Internal fragmentation | With fixed partitions | Only in the last page of each process: less than one page (on average about half a page) |
| Compaction needed | Sometimes | Never |
| Extra cost | Relocation + limit registers | A page table per process, and a lookup on every access (fixed by the TLB) |
Pages on a real machine
#include <stdio.h>
#include <unistd.h>
int main(void) {
long page = sysconf(_SC_PAGESIZE); // ask the OS: page size?
printf("page size on this machine: %ld bytes\n", page);
int program = 10000; // a 10,000-byte program
long pages = (program + page - 1) / page; // round UP
printf("a %d-byte program needs %ld pages\n", program, pages);
printf("wasted in the last page: %ld bytes\n", pages*page - program);
}
page size on this machine: 4096 bytes
a 10000-byte program needs 3 pages
wasted in the last page: 2288 bytes
sysconf(from<unistd.h>) asks the operating system for a system setting;_SC_PAGESIZEis the page size.- 4096 bytes = 4 KiB. A KiB (kibibyte) is 1024 bytes; a MiB (mebibyte) is 1024 KiB; a GiB (gibibyte) is 1024 MiB. (KB, MB, GB strictly mean powers of 1000, episode 1.)
- The program needs ⌈10000 / 4096⌉ = 3 pages = 12,288 bytes, so the last page wastes 12,288 - 10,000 = 2288 bytes of internal fragmentation.
(program + page - 1) / pageis the integer way of rounding up a division.- 4096 = 2^12. Page sizes are always a power of two, which makes splitting an address trivial (next section).
Page number and offset
Every logical address is split into two parts:
- Page number (p): which page the byte is in. It is the index into the page table.
- Page offset (d): where the byte is inside that page, from 0 to page size - 1.
logical address 20000, page size 4096
page = 20000 / 4096 = 4 (4 x 4096 = 16384)
offset = 20000 % 4096 = 3616
check: 4 x 4096 + 3616 = 20000
Because the page size is 2^n, the offset is the low n bits and the page number is all the bits above them:
m-bit logical address
|<-- page number p: m - n bits -->|<-- offset d: n bits -->|
With m = 32 and 4 KiB pages (n = 12): 20 bits of page number, 12 bits of offset. No division is needed: the hardware just takes the wires.
The obvious mask fails (live)
A bitwise AND (&, episode 3) keeps only the bits that are 1 in both numbers. The number we AND with to keep some bits is called a mask. The obvious mask is the page size:
#include <stdio.h>
int main(void) {
unsigned a = 20000; // a logical address
unsigned p = a >> 12; // 4096 = 2^12: drop the low 12 bits
unsigned d = a & 4096; // keep the low 12 bits?
printf("address %u -> page %u, offset %u\n", a, p, d);
printf("check: %u * 4096 + %u = %u\n", p, d, p * 4096 + d);
}
address 20000 -> page 4, offset 0
check: 4 * 4096 + 0 = 16384
Wrong! 4096 in binary is 1 0000 0000 0000: a single 1-bit (bit 12) followed by twelve zeros. 20000 & 4096 keeps only bit 12, which is exactly the bit we wanted to drop, and 20000 has a 0 there. To keep the low 12 bits we need twelve 1-bits: 4096 - 1 = 4095 = 0xFFF = 1111 1111 1111.
#include <stdio.h>
int main(void) {
unsigned a = 20000; // a logical address
unsigned p = a >> 12; // 4096 = 2^12: drop the low 12 bits
unsigned d = a & 4095; // 4095 = 0xFFF: twelve 1-bits
printf("address %u -> page %u, offset %u\n", a, p, d);
printf("check: %u * 4096 + %u = %u\n", p, d, p * 4096 + d);
printf("with / and %%: page %u, offset %u\n", a / 4096, a % 4096);
}
address 20000 -> page 4, offset 3616
check: 4 * 4096 + 3616 = 20000
with / and %: page 4, offset 3616
Rule: page number = addr >> n (or addr / size), offset = addr & (size - 1) (or addr % size). >> shifts the bits right, dropping the low n bits.
Address translation
The MMU (memory management unit, episode 30) translates every logical address:
- Split the logical address into page number p and offset d.
- Look up entry p of the page table to get the frame number f.
- Physical address = f × page size + d. In bits: the frame number simply replaces the page number; the offset is copied unchanged.
logical [ p | d ] ──page table: p → f──► physical [ f | d ]
Where is the page table? The PTBR
The page table is itself in RAM (it is far too big for registers). A CPU register, the page-table base register (PTBR), holds the physical address where the current process's page table starts. On a context switch (the CPU moving from one process to another, episode 17), the OS saves the old process's state and loads the new process's PTBR, which switches the whole memory map in one step. (On x86 this register is called CR3.) Some systems also keep a page-table length register (PTLR) with the table's size, so page numbers beyond it trap.
What's inside a page table entry (PTE)
A page table entry (PTE) is one row of the page table:
| frame number | valid | protection (R/W/X) | dirty | reference |
| Bit | Meaning | Example |
|---|---|---|
| Valid (present) bit | 1 = this page belongs to the process and is in RAM; 0 = not, so the MMU traps to the OS (an invalid access, or a page fault, episode 33) | page 3 below |
| Protection bits | What is allowed on the page: read, write, execute | code pages are read + execute, not write |
| Dirty (modified) bit | Set by hardware when the page is written; the OS must save a dirty page to disk before reusing its frame | after x = 5 on that page |
| Reference (accessed) bit | Set by hardware whenever the page is read or written; tells the OS which pages are in active use | used by page replacement, episode 34 |
A trap is an interrupt caused by the running program itself, handing control to the OS.
The MMU, simulated (live)
#include <stdio.h>
// One process, page size 4096. Page table: page -> frame + bits
int frame[4] = {5, 2, 7, 0}; // where each page sits in RAM
int valid[4] = {1, 1, 1, 0}; // page 3 is not in memory
int rw[4] = {0, 1, 1, 1}; // page 0 is code: read-only
void translate(unsigned addr, int is_write) {
unsigned p = addr / 4096, d = addr % 4096;
printf("%s %5u: page %u offset %4u -> ",
is_write ? "write" : "read ", addr, p, d);
if (p >= 4 || !valid[p]) { printf("TRAP: invalid page\n"); return; }
if (is_write && !rw[p]) { printf("TRAP: read-only\n"); return; }
printf("frame %d, physical %u\n", frame[p], frame[p] * 4096 + d);
}
int main(void) {
translate(100, 0); translate(5000, 1); translate(9000, 0);
translate(13000, 0); translate(200, 1);
}
read 100: page 0 offset 100 -> frame 5, physical 20580
write 5000: page 1 offset 904 -> frame 2, physical 9096
read 9000: page 2 offset 808 -> frame 7, physical 29480
read 13000: page 3 offset 712 -> TRAP: invalid page
write 200: page 0 offset 200 -> TRAP: read-only
frame[]is the page table.valid[]andrw[]are the valid and write-permission bits.read 100: page 0, offset 100 → frame 5 → 5 × 4096 + 100 = 20580.write 5000: page 1 (4096..8191), offset 904 → frame 2 → 8192 + 904 = 9096.read 9000: page 2, offset 808 → frame 7 → 28672 + 808 = 29480.read 13000: page 3, valid bit 0 → trap.write 200: page 0 is read-only code → trap. This is exactly how a realSegmentation faultis caught: the hardware checks the PTE and traps; the OS stops the program.
Worked example (the in-video "Try it")
Page size 1024 bytes; page table 0 → 3, 1 → 8, 2 → 1. Logical address 2100:
- p = 2100 / 1024 = 2, d = 2100 % 1024 = 52.
- Page 2 → frame 1. Physical = 1 × 1024 + 52 = 1076.
How big is the page table?
Recipe:
- Offset bits n = log2(page size).
- Page-number bits = logical address bits - n.
- Number of entries = 2^(page-number bits) (one entry per page, not per frame).
- Page table size = entries × bytes per entry.
Physical side:
- Frames = physical memory size / page size.
- Frame-number bits = log2(frames).
- A PTE needs the frame-number bits plus the flag bits, rounded up to whole bytes (usually 4 or 8).
Example: 32-bit logical addresses, 4 KiB pages, 64 MiB RAM.
offset bits = 12
page bits = 32 - 12 = 20 → 2^20 = 1,048,576 entries
frames = 2^26 / 2^12 = 2^14 = 16,384 → frame number = 14 bits
PTE = 14 bits + flags → 4 bytes
page table = 2^20 x 4 B = 4 MiB, for EVERY process
Calculator (live)
#include <stdio.h>
// Page table size = number of pages x bytes per entry
void table(int addr_bits, int offset_bits, int entry_bytes) {
int page_bits = addr_bits - offset_bits;
unsigned long long entries = 1ULL << page_bits;
unsigned long long kib = entries * entry_bytes / 1024;
printf("%d-bit, %2d offset bits: 2^%d entries x %d B = ",
addr_bits, offset_bits, page_bits, entry_bytes);
if (kib >= 1048576) printf("%llu GiB\n", kib / 1048576);
else if (kib >= 1024) printf("%llu MiB\n", kib / 1024);
else printf("%llu KiB\n", kib);
}
int main(void) {
table(32, 12, 4); // 32-bit address, 4 KiB pages
table(32, 22, 4); // 32-bit address, 4 MiB pages
table(48, 12, 8); // 48-bit address, 4 KiB pages
}
32-bit, 12 offset bits: 2^20 entries x 4 B = 4 MiB
32-bit, 22 offset bits: 2^10 entries x 4 B = 4 KiB
48-bit, 12 offset bits: 2^36 entries x 8 B = 512 GiB
1ULL << page_bitsis 2^page_bits (shifting 1 left by k places multiplies it by 2^k);ULLmakes it a 64-bit unsigned number so 2^36 does not overflow.- 32-bit with 4 KiB pages: 4 MiB per process. With 4 MiB pages: only 10 page bits, a 4 KiB table.
- 48-bit addresses (x86-64 with 4-level paging "supports 48 virtual address bits", sandpile.org) with 4 KiB pages and 8-byte entries: 512 GiB per process, far bigger than the RAM. A flat (single-level) page table is impossible there; episode 32 fixes it with multilevel paging.
Page size trade-offs
| Small pages (e.g. 4 KiB) | Big pages (e.g. 2 MiB, 4 MiB) | |
|---|---|---|
| Internal fragmentation | Little (less than one small page per process) | Up to a whole big page |
| Page table size | Large (more pages) | Small |
| TLB coverage (memory one TLB entry covers) | Small → more TLB misses | Large → fewer misses |
| Disk transfers | Many small ones | Fewer, bigger ones (more efficient per byte) |
| Loading only what's used | Fine-grained | Coarse |
There is no single winner; real systems use a small default page and allow big pages for programs that need lots of memory (huge pages, episode 32).
Average internal fragmentation with paging is about half a page per process (the last page is, on average, half full).
Shared pages
40 students run the same text editor on one server. The editor's code is 150 KB, each student's data is 50 KB.
no sharing: 40 x (150 + 50) = 8000 KB
shared code: 150 + 40 x 50 = 2150 KB
With paging, each student's page table points its code pages at the same frames: one physical copy, many page tables. These are shared pages. Sharing is only safe for reentrant code (also called pure code): code that never modifies itself, so it is read-only and no process can disturb another. The protection bits mark these pages read + execute only. This is how shared libraries (episode 30) are kept in RAM only once.
The new problem: two trips per access
The page table is in RAM. So every load or store now needs:
- one RAM access to read the PTE, then
- one RAM access to read or write the actual data.
If one RAM access takes 100 ns (nanoseconds, billionths of a second), every access now takes 200 ns: twice as slow. Unacceptable.
The TLB
The story: the delivery boy's memory
| Delivery at a big society | TLB |
|---|---|
| A huge residents' register at the gate: slow to search | The page table in RAM |
| A tiny notebook of regular customers: "Mehta → flat 1204" | The TLB: recent page → frame translations |
| Name in the notebook? Go straight up | TLB hit: frame found in about a clock cycle |
| Not there? Check the register, write it in the notebook, cross out an old note | TLB miss: read the page table from RAM, save the translation, replace an old entry |
Definitions
- TLB (translation lookaside buffer): a small, very fast cache inside the MMU that stores recent page-number → frame-number translations.
- Associative memory: memory in which every entry is compared with the search key at the same time (in parallel), instead of one by one. This makes the TLB fast, and expensive, so it is small.
- TLB hit: the page number is found in the TLB; the frame number comes out immediately and RAM is accessed once (for the data).
- TLB miss: the page number is not in the TLB; the page table is read from RAM, the translation is put into the TLB, then the data is accessed.
- Hit ratio (h): the fraction of lookups that hit. Miss ratio = 1 - h.
- When the TLB is full, an entry is replaced, often the least recently used (LRU) one (episode 10).
Typical figures (Wikipedia, "Translation lookaside buffer"): size 12 to 4,096 entries, hit time 0.5 to 1 clock cycle, miss penalty 10 to 100 clock cycles, miss rate 0.01 to 1%. On x86 the hardware walks the page tables itself on a miss (starting from CR3); MIPS uses a software-managed TLB: a miss raises an exception and the OS fills the TLB.
logical [p | d] ──► TLB? ──hit──► f ──► physical [f | d]
│
miss
▼
page table (RAM, via PTBR) ──► f, and put (p, f) into the TLB
TLB simulation (live)
#include <stdio.h>
int tlb[4], used[4], now, hits, misses; // a 4-entry TLB, LRU
void touch(int page) {
int lru = 0; now++;
for (int i = 0; i < 4; i++) {
if (tlb[i] == page) { hits++; used[i] = now; return; }
if (used[i] < used[lru]) lru = i;
}
misses++; tlb[lru] = page; used[lru] = now; // walk the page table
}
void test(const char *name, int step) { // step = bytes between reads
for (int i = 0; i < 4; i++) tlb[i] = -1, used[i] = 0;
hits = misses = 0;
for (int r = 0; r < 4; r++) // read 64 KiB, 4 times
for (int a = 0; a < 65536; a += step) touch(a / 4096);
printf("%-10s hits %5d misses %3d hit ratio %.2f%%\n",
name, hits, misses, 100.0 * hits / (hits + misses));
}
int main(void) { test("in order", 4); test("jumping", 4096); }
in order hits 65472 misses 64 hit ratio 99.90%
jumping hits 0 misses 64 hit ratio 0.00%
- A 4-entry TLB with LRU replacement.
touch(page)is one lookup: a hit updates the entry's last-used time; a miss replaces the least recently used entry. testreads 64 KiB (16 pages of 4 KiB) four times: either in order, 4 bytes at a time (16,384 reads per pass), or jumping 4096 bytes each time (16 reads per pass).- In order: 65,536 lookups, 64 misses (each of the 16 pages misses once per pass, because 16 pages don't fit in 4 entries), 99.90% hit ratio: each translation is reused 1023 more times.
- Jumping: 64 lookups, all misses: the 16 pages cycle through a 4-entry LRU TLB, so every page has been evicted by the time it comes back.
- This is locality (episode 8): programs keep using memory near what they just used, which is why a tiny TLB works so well, and why walking arrays in order is faster.
Effective access time (EAT)
Let m = time of one RAM access, t = time to search the TLB, h = TLB hit ratio.
hit: t + m (TLB, then the data)
miss: t + m + m (TLB, the page table, then the data)
EAT = h(t + m) + (1 - h)(t + 2m)
If the question doesn't give a TLB time, take t = 0: EAT = h·m + (1 - h)·2m = (2 - h)·m.
Some questions say the TLB search overlaps the memory access or is negligible; then use EAT = h·m + (1 - h)·2m. Always write the formula you use.
Numerical
m = 100 ns, t = 20 ns, h = 0.80:
EAT = 0.8 x (20 + 100) + 0.2 x (20 + 200) = 96 + 44 = 140 ns
EAT calculator (live)
#include <stdio.h>
// Effective access time (EAT) with a TLB
int main(void) {
double m = 100, t = 20; // ns: one RAM access, one TLB search
double ratio[4] = {0.80, 0.90, 0.98, 0.99};
printf("no TLB at all: %.0f ns (page table + data)\n", 2 * m);
for (int i = 0; i < 4; i++) {
double h = ratio[i];
double eat = h * (t + m) + (1 - h) * (t + 2 * m);
printf("hit ratio %.0f%%: EAT = %.1f ns, slowdown %.0f%%\n",
100 * h, eat, 100 * (eat - m) / m);
}
}
no TLB at all: 200 ns (page table + data)
hit ratio 80%: EAT = 140.0 ns, slowdown 40%
hit ratio 90%: EAT = 130.0 ns, slowdown 30%
hit ratio 98%: EAT = 122.0 ns, slowdown 22%
hit ratio 99%: EAT = 121.0 ns, slowdown 21%
Without a TLB every access costs 200 ns. With 99% hits it costs 121 ns, only 21% slower than plain memory. Raising the hit ratio matters far more than shaving the TLB time.
Finding the hit ratio you need
m = 100 ns, t = 0. For EAT ≤ 110 ns: (2 - h) × 100 ≤ 110 → h ≥ 0.90.
Context switches: TLB flush and ASID
The TLB is shared by all processes, but page numbers are not: process A's page 4 is in frame 9, process B's page 4 is in frame 2. After a context switch from A to B, a TLB hit on page 4 would give B A's frame: wrong, and a security hole.
- TLB flush: mark every TLB entry invalid on each context switch. Simple and safe, and the only option on some older hardware (Wikipedia names the Intel 80386), but the new process starts cold: every lookup misses until the TLB refills.
- ASID (address-space identifier): tag each TLB entry with a small number naming the process (address space) it belongs to. A hit needs both the page number and the ASID to match the current process, so entries of many processes coexist and no flush is needed. The OS flushes only when it reuses an ASID.
TLB: ASID | page | frame
A | 4 | 9
B | 4 | 2
On x86 the ASID is called the PCID (process-context identifier). From the Linux kernel patch that started using it: "PCID is a "process context ID" -- it's what other architectures call an address space ID", "x86's PCID is 12 bits" (4096 values), and "Every non-global TLB entry is tagged with a PCID". (Global entries, such as kernel pages that every process maps the same way, are marked so they survive switches.)
The whole chain
| Step | Obvious attempt | What broke | Fix |
|---|---|---|---|
| 1 | One unbroken stretch per program | External fragmentation: 350 K fails with 400 K free | Paging: pages in any frames |
| 2 | Divide addresses | Slow, and the mask & 4096 gave offset 0 |
Page size = 2^n: offset = low n bits, mask = size - 1 |
| 3 | Pages anywhere | Where is each page? | Page table (via the PTBR): p → f |
| 4 | Let every access through | Bad pages, writes to code | Valid and protection bits trap |
| 5 | One flat table | 4 MiB (32-bit) to 512 GiB (48-bit) per process | Next: multilevel tables, huge pages |
| 6 | Page table in RAM | Every access = 2 RAM trips | TLB (99.9% hits with locality) |
| 7 | TLB shared by processes | Wrong frame after a switch | TLB flush or ASID (x86 PCID) |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
offset = addr & 4096 |
offset 0 and check: 4 * 4096 + 0 = 16384 (wrong output, live) |
4096 is a single 1-bit | addr & 4095 (mask = page size - 1) |
| Translating the offset too | Wrong physical address | Only p becomes f | Physical = f × size + d |
| Miss costs t + m | Wrong EAT | A miss reads the page table and the data | Miss = t + 2m |
| Page table entries = RAM / page size | Wrong numerical | That's the number of frames | Entries = 2^(logical bits - offset bits) |
| Forgetting to round up pages | 2 pages for 10,000 bytes | A partial page still needs a whole frame | ⌈size / page size⌉ |
Using 1 << 36 with int |
warning: left shift count >= width of type [-Wshift-count-overflow], and the value prints 0 |
1 is a 32-bit int |
1ULL << 36 |
| Sharing writable pages | One process changes another's data | Sharing is safe only for read-only (reentrant) code | Share code, give each process its own data |
| Forgetting the flush / ASID | Wrong frame after a context switch | TLB entries belong to a process | Flush on switch, or tag with an ASID |
Mini project: a paging + TLB simulator
Write a C program that reads, from stdin, a page size, a page table (frame number, valid bit, write bit per page) and a list of accesses like r 20000 or w 5000. Simulate an 8-entry TLB with LRU replacement in front of the page table. For each access print the page, offset, whether it was a TLB hit or miss, and the physical address or the trap. At the end, print the hit ratio and the EAT for m = 100 ns, t = 10 ns. Then add ASIDs: accept switch A / switch B lines and compare the hit ratio with "flush on every switch" against "tag with ASID".
Practice
1. Page size 2 KiB: split logical address 7000.
Solution
2 KiB = 2048 = 2^11. p = 7000 / 2048 = 3 (3 × 2048 = 6144), d = 7000 - 6144 = 856. In bits: p = 7000 >> 11, d = 7000 & 2047.
2. 36-bit logical address, 4 KiB pages, 4-byte entries. Page table size?
Solution
Offset 12 bits, page number 24 bits → 2^24 = 16,777,216 entries × 4 B = 2^26 B = 64 MiB.
3. m = 80 ns, t = 0, h = 95%. EAT?
Solution
EAT = 0.95 × 80 + 0.05 × 160 = 76 + 8 = 84 ns.
4. Why can only read-only pages be shared?
Solution
If a writable page were shared, one process's writes would change the other processes' data, breaking the isolation between them. Read-only (reentrant) code never changes, so every process can safely use the same frames. (Writable pages can be shared until the first write with copy-on-write, episode 33.)
5. A process of 72,766 bytes, page size 2048 bytes. How many pages, and how much internal fragmentation?
Solution
72,766 / 2048 = 35.53 → 36 pages (73,728 bytes). Internal fragmentation = 73,728 - 72,766 = 962 bytes.
6. 32-bit logical addresses, 1 GiB of physical memory, 4 KiB pages, and each PTE holds the frame number plus valid, dirty, reference and 3 protection bits. Find the frame-number bits, the PTE size and the page table size.
Solution
Frames = 2^30 / 2^12 = 2^18 → 18-bit frame number. PTE = 18 + 1 + 1 + 1 + 3 = 24 bits = 3 bytes (in practice rounded to 4). Entries = 2^(32 - 12) = 2^20. Table = 2^20 × 3 B = 3 MiB (or 4 MiB with 4-byte entries).
7. m = 100 ns, t = 0. What hit ratio keeps EAT within 110 ns?
Solution
EAT = h × 100 + (1 - h) × 200 = 200 - 100h ≤ 110 → h ≥ 0.90.
8. Page size 1 KiB, page table 0 → 6, 1 → 4, 2 → 9, 3 → invalid. Translate logical 3000 and 3500.
Solution
3000: p = 2, d = 3000 - 2048 = 952 → frame 9 → 9 × 1024 + 952 = 10,168. 3500: p = 3 → valid bit 0 → trap.
Quick quiz
RAM access m = 50 ns
TLB search t = 10 ns
TLB hit ratio h = 90%
// effective access time?
A. 60 ns B. 65 ns C. 110 ns D. 55 ns
Answer
B. EAT = 0.9 × (10 + 50) + 0.1 × (10 + 100) = 54 + 11 = 65 ns.
Interview questions
- What is paging, and what problem does it solve? Splitting logical memory into fixed-size pages and physical memory into same-size frames, so a process can occupy any free frames. It removes external fragmentation and the need for compaction.
- Page vs frame? A page is a block of logical (virtual) memory; a frame is a block of physical memory of the same size.
- How is a logical address translated? Split into page number and offset; the page table gives the frame number; physical = frame × page size + offset.
- Why are page sizes powers of two? So the offset is just the low bits and the page number the high bits: no division.
- Does paging have fragmentation? No external; internal only in the last page of each process (about half a page on average).
- What does a page table entry contain? Frame number plus valid, protection (R/W/X), dirty and reference bits.
- What is the PTBR? A register holding the address of the current process's page table; changed on every context switch (CR3 on x86).
- How big is a page table for 32-bit addresses and 4 KiB pages? 2^20 entries × 4 B = 4 MiB per process.
- Small vs large pages? Small: less internal fragmentation, bigger tables, more TLB misses. Large: the reverse.
- What are shared pages? Frames of read-only (reentrant) code mapped into many processes' page tables, so only one copy is in RAM.
- What is a TLB and why is it needed? A small, fast, associative cache of page → frame translations; without it every access would need an extra RAM access for the page table.
- What is the EAT formula? EAT = h(t + m) + (1 - h)(t + 2m).
- What happens to the TLB on a context switch? It is flushed, or entries are tagged with an ASID (PCID on x86) so no flush is needed.
- Who handles a TLB miss? On x86, the hardware page walker; on MIPS, the OS (software-managed TLB).
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Contiguous allocation | Each process gets one unbroken stretch of RAM | episode 30 |
| External fragmentation | Free memory split into holes between processes, none big enough | 400 K free, 350 K fails |
| Internal fragmentation | Wasted space inside an allocated block | 2288 bytes in the last page |
| Hole | A free gap in memory | 200 K between A and C |
| Compaction | Sliding processes together so holes join | slow |
| Logical (virtual) address | Address generated by the program | 20000 |
| Logical address space | All logical addresses a process can use | 0 .. 2^32 - 1 |
| Physical address | Real address in RAM | 20580 |
| Paging | Memory scheme where a process's pages sit in any free frames | |
| Page | Fixed-size block of logical memory | 4 KiB |
| Frame (page frame) | Fixed-size block of physical memory, same size as a page | frame 5 |
| Page table | Per-process table: page number → frame number | 0 → 5, 1 → 2 |
| Page number (p) | Which page an address is in; index into the page table | 20000 → 4 |
| Page offset (d) | Position of the byte inside its page | 20000 → 3616 |
| Address translation | Turning a logical address into a physical one | (p, d) → f × size + d |
| MMU | Hardware that translates addresses on every access | |
sysconf(_SC_PAGESIZE) |
C call asking the OS for its page size | 4096 |
| KiB / MiB / GiB | 1024 bytes / 1024 KiB / 1024 MiB | 4 KiB page |
| Power of two | 2 multiplied by itself n times | 4096 = 2^12 |
>> (right shift) |
Moves bits right, dropping the low ones | 20000 >> 12 = 4 |
<< (left shift) |
Moves bits left; 1 << k = 2^k | 1ULL << 36 |
Bitwise AND (&) |
Keeps bits that are 1 in both numbers | 20000 & 4095 = 3616 |
| Mask | A number used with AND to keep chosen bits | 4095 = 0xFFF |
| PTBR (page-table base register) | Register with the address of the current page table | CR3 on x86 |
| PTLR (page-table length register) | Register with the page table's size | |
| Context switch | CPU moving from one process to another | load new PTBR |
| PTE (page table entry) | One row of the page table: frame number + bits | |
| Valid (present) bit | 1 = page belongs to the process and is in RAM; 0 → trap | page 3 |
| Protection bits | Read / write / execute permissions of a page | code: read-only |
| Dirty (modified) bit | Set when the page is written; must be saved before reuse | |
| Reference (accessed) bit | Set when the page is used | page replacement |
| Trap | Interrupt caused by the running program, handing control to the OS | invalid page |
| Page fault | Trap on access to a page that is not in RAM (episode 33) | |
| Segmentation fault | OS stopping a program after an invalid memory access | write to read-only page |
| Page table size | Entries × bytes per entry | 4 MiB for 32-bit, 4 KiB pages |
| Flat (single-level) page table | One table with an entry for every page | 512 GiB for 48-bit |
| Page size trade-off | Small pages: less waste, bigger tables; big pages: the reverse | |
| TLB coverage (reach) | Memory covered by all TLB entries together | entries × page size |
| Shared pages | The same frames mapped in many processes' page tables | one editor copy |
| Reentrant (pure) code | Code that never modifies itself, safe to share | editor code |
| TLB (translation lookaside buffer) | Small fast cache of recent page → frame translations | 4 entries in our demo |
| Associative memory | All entries compared with the key at once | the TLB |
| TLB hit | Translation found in the TLB | 65,472 hits |
| TLB miss | Translation not in the TLB; read the page table | 64 misses |
| Hit ratio (h) | Fraction of lookups that hit | 99.90% |
| Miss penalty | Extra time a miss costs | 10-100 cycles |
| LRU | Replace the least recently used entry | our TLB |
| Locality | Programs keep using memory near what they just used | in-order reads |
| Hardware-managed TLB | CPU walks the page table itself on a miss | x86 |
| Software-managed TLB | A miss raises an exception and the OS fills the TLB | MIPS |
| EAT (effective access time) | Average time of one memory access | 140 ns |
| ns (nanosecond) | One billionth of a second | 100 ns |
| TLB flush | Invalidating all TLB entries | on a context switch |
| ASID (address-space identifier) | Tag on each TLB entry naming its process | A, B |
| PCID | x86's ASID, 12 bits | 4096 values |
| Global TLB entry | Entry shared by all processes, not flushed | kernel pages |
Summary
- Paging cuts logical memory into pages and RAM into same-size frames; a per-process page table (found through the PTBR) maps page → frame. No external fragmentation; internal only in the last page (live: 3 pages for 10,000 bytes, 2288 bytes wasted).
- An address splits into page number (high bits) and offset (low bits); the mask is page size - 1 (live:
& 4096gave offset 0,& 4095gave 3616). - Physical = frame × page size + offset. PTEs carry valid, protection, dirty and reference bits; invalid pages and illegal writes trap (live).
- Page table size = 2^(page-number bits) × entry size: 4 MiB for 32-bit, 512 GiB for 48-bit (live) → next episode. Small vs big pages is a trade-off; shared pages keep one copy of read-only code.
- Paging makes every access two RAM trips; the TLB caches translations (live: 99.90% hits in order, 0% jumping). EAT = h(t + m) + (1 - h)(t + 2m) (live: 140, 130, 122, 121 ns).
- On a context switch, flush the TLB or tag entries with an ASID (x86: 12-bit PCID).
Next episode: Page table structures and segmentation: multilevel paging, hashed and inverted page tables, huge pages, segmentation and segmented paging.