Intuition The one core ideaA program never speaks the language your RAM chips understand — it uses pretend addresses that the hardware must translate into real addresses on every single memory touch. A TLB (Translation Lookaside Buffer) is a tiny notepad that remembers the last few translations so this rewriting is almost free.
This page assumes nothing and is fully self-contained. By the end you should be able to point at every symbol below and say what it means and what it looks like . We build them one at a time, each using only the ones before it, then hand you off to the main TLB (translation lookaside buffer) note.
A byte is the smallest chunk of memory the machine names individually: 8 bits, holding one of 256 possible values. Think of it as one tiny numbered mailbox that holds one small number.
An address is just the number written on a mailbox so you can say "give me the contents of box #7". Memory is a long row of these numbered boxes.
Worked example Figure 1 — memory as a street of mailboxesMemory is a street of mailboxes , each with a number painted underneath it. When a program says "read address 7", the hardware walks to the pink-arrowed box #7 and reads what's inside (here the value 7). The number under a box is its address — nothing more.
Why this matters: everything a TLB does is turning one box-number into a different box-number . If you don't picture memory as numbered boxes, none of the translation talk lands.
Intuition Why powers of two show up everywhereEach bit is a yes/no switch. With n 2 n n 2 n
log 2 log 10 Why it feels natural: we count in tens as humans.
The fix: the hardware counts in twos — every wire is on/off. The number of binary patterns is 2 n log 2 because the thing we are counting (bit-patterns) grows by doubling.
We will use log 2
Definition Page and page sizeP page is a fixed-size block of consecutive bytes — say 4096 (4 KiB) of them — that memory management treats as one unit. We call this fixed size the ==page size P
P just by cutting its bits (no division, no leftover). That only works if the number of bytes inside a page, P P = 2 ( some integer ) P log 2 3000 ≈ 11.55 not a whole number of bits, and no clean bit-cut exists. So page sizes are always powers of two , which makes log 2 P
The offset is how far into a page a byte sits: box #0, #1, ... up to #( P − 1 ) within that page. It's the "house number on this one street". Because there are P P log 2 P
The page number says which page (which street), the offset says which byte inside it (which house). Together they name any byte.
Worked example Figure 2 — cutting an address into page number and offsetThe raw address is one long bit-string. We draw a vertical cut (yellow dashed line). The blue bits left of the cut = the page number; the pink bits right of the cut = the offset. For a 4 KiB page the cut sits after 12 bits, because log 2 4096 = 12
Why this matters: a TLB translates only the page number and leaves the offset alone. Without the mental picture of "cut the address in two", the idea "offset is not translated" is meaningless.
Intuition The pretend street and the real streetThe program lives on a pretend street of addresses (virtual). The RAM chips have a real street (physical). A referee sits between them and, for each access, points from the pretend box to the real box it currently stands for. That referee's job is translation .
Definition Virtual address (VA) and Virtual Page Number (VPN)A virtual address is the pretend box-number the program uses. Cut it in two (section 3): the high part is the VPN (Virtual Page Number, "which pretend page"), the low part is the offset.
Definition Physical address (PA) and Physical Frame Number (PFN)A physical address is the real box-number in DRAM. A frame is a page-sized slot in real memory, and the PFN (Physical Frame Number) says which real slot. A page of program data is placed into a frame of RAM.
Worked example Figure 3 — only the page number is translatedVPN → PFN is the only arrow that bends (blue); the offset walks straight across unchanged (pink), because the byte keeps its position inside the page no matter which frame the page lives in. This is why the offset is never translated .
This mapping VPN → PFN is stored in the Page Table , and the whole scheme is Virtual Memory .
A page table is a lookup table, held in DRAM , that stores for every VPN the matching PFN plus some status bits. It is the master map from pretend pages to real frames.
The catch: because the map itself lives in DRAM, reading it costs a memory access . So a naive translation is "read the map (1 access), then read your data (1 access)" — at least twice the work. Modern maps are split into several levels, so a full page-table walk can be 4 memory reads before you even touch your data. This slowness is the entire reason a TLB is worth building.
Definition Valid / permission bitsAlongside each PFN the table stores tiny flags: valid (is this page actually in memory?) and permissions (may I read / write / execute it?). These ride along in TLB entries too, so a bad access can be caught instantly.
If a page's valid bit is off, touching it triggers a Page Fault — the OS must fetch it from disk. That is a different, much slower event than a mere translation miss.
≪ log 2 P P f starts at byte f × P P = 2 l o g 2 P log 2 P
∣ OR operator, written ∣ either input has a 1 there. When one number has all-zero low bits (an empty slot) and the other has its bits only in that slot, OR simply drops the second into the hole — this is the bit-level version of concatenation ∥
Worked check: PFN 0x0037 with P = 4 k = 12
0 x 0037 = 55 55 ≪ 12 = 55 × 4096 = 225280 = 0x37000. This is the frame's base byte address , with the low 12 bits all zero (an empty offset-slot).Now OR in the offset 0xABC: since 0x37000 has zeros in its low 12 bits and 0xABC fits in exactly 12 bits, 0x37000 ∣ 0xABC = 0x37ABC
Intuition Programs repeat themselvesPrograms don't scatter their accesses randomly; they hammer the same few pages over and over (loops, nearby data). This habit is called locality of reference .
Because of Locality of Reference , a notepad holding just the last-used handful of VPN → PFN mappings will satisfy the vast majority of translations. That notepad is a cache , and this specific one is the TLB. (The general caching idea is Cache (memory hierarchy) .)
Definition Cache / hit / missA cache is a small fast store of recently-used answers. A hit = the answer was in the cache (fast). A miss = it wasn't there, so you pay the slow path once, then remember the answer. These three words drive the whole TLB flow.
Definition EMAT (Effective Memory Access Time)EMAT is the average time one memory access really takes once you mix fast cache-hits with occasional slow misses. It is the number the main note uses to prove the notepad helps: you weight the fast path by its hit rate and the slow path by its miss rate, then add them up. Keep the acronym in your pocket — you'll meet the full formula on the parent page.
Definition Context switchA context switch is when the CPU stops running one program and starts another. Because each program has its own pretend street, VPN 0x5 in program A points to a totally different frame than VPN 0x5 in program B.
So after a Context Switch , the notepad's remembered translations may belong to the wrong program — stale entries. You only need to know why it happens: two programs reuse the same VPNs for different frames.
split address into page and offset
shift and OR equal place bits
Read it bottom-up: everything funnels into K = TLB . If any upstream box is fuzzy, the arrows into K break.
Test yourself — cover the right side and answer aloud.
A byte is how many bits, and how many values can it hold? 8 bits, 256 possible values.
An address is, in plain words, what? The number painted on a mailbox — how you name one storage location.
Why do memory sizes come in powers of two? Addresses are made of bits; n 2 n
log 2 4096 = ? 12; the number of bits needed to name 4096 things, since 2 12 = 4096
Why must the page size P So an address splits into page-number and offset by a clean bit-cut, making log 2 P
What does the symbol ∥ Concatenation — glue two bit-groups side by side into one number (not multiply).
What does bitwise OR (∣ Sets a bit to 1 if either input has it; used to drop the offset into the empty low bits of the frame's base address.
When you split an address, which part is translated? Only the page-number part; the offset passes through unchanged.
VPN vs PFN in one line each? VPN = which pretend (virtual) page; PFN = which real (physical) frame.
Why does shifting left by k 2 k Each left slide of the bits doubles the value; doing it k 2 k
Where does the page table physically live, and why is that a problem? In DRAM; reading it costs a full memory access, so translation would double every access.
What is locality of reference? Programs touch the same few pages repeatedly, so caching translations pays off.
What does EMAT stand for and measure? Effective Memory Access Time — the average time per access mixing fast hits with slow misses.
Cache hit vs miss? Hit = answer already stored (fast); miss = not stored, pay slow path once, then remember it.
Why can the TLB hold wrong data after a context switch? Different programs reuse the same VPNs for different frames, so old entries become stale.