Memory Hierarchy

CSS Optional — Paper-II, Section-A · Chapter 7 · 🔥 High-yield conceptual + numerical topic

No single memory technology is simultaneously fast, large, and cheap. SRAM is fast but costs roughly 100× more per bit than DRAM; disk is cheap and vast but a million times slower. The memory hierarchy is the engineering answer to this trilemma: layer several technologies so the system behaves as though it has the speed of the fastest and the capacity of the largest.

---

SECTION 1 — The Hierarchy Structure

     ▲  Faster, smaller, costlier per bit
     │
┌────┴─────────────┐
│    Registers     │   ~0.3 ns   |  ~256 bytes      | inside CPU
├──────────────────┤
│    L1 Cache      │   ~1 ns     |  32–64 KB        | SRAM, split I/D
├──────────────────┤
│    L2 Cache      │   ~4 ns     |  256 KB–1 MB     | SRAM, per core
├──────────────────┤
│    L3 Cache      │   ~15 ns    |  8–32 MB         | SRAM, shared
├──────────────────┤
│  Main Memory     │   ~60–100 ns|  8–64 GB         | DRAM
├──────────────────┤
│   SSD / Flash    │   ~0.1 ms   |  256 GB–4 TB     | NAND flash
├──────────────────┤
│   Hard Disk      │   ~10 ms    |  1–20 TB         | magnetic
├──────────────────┤
│  Tape / Cloud    │   seconds   |  unlimited       | archival
└──────────────────┘
     │
     ▼  Slower, larger, cheaper per bit

1.1 The Four Properties That Change Down the Hierarchy

As you descend:

That last row is the one candidates forget, and it is the row that makes the whole scheme work: the CPU touches the top levels overwhelmingly more often than the bottom ones.

1.2 Managed By Whom?

A distinction examiners like:

This is why cache is invisible to the programmer while virtual memory is an OS service.

---

SECTION 2 — Why the Hierarchy Works: Locality of Reference

The hierarchy would fail completely if memory access were random — a small fast level would then be hit only in proportion to its size. It succeeds because programs exhibit locality:

• Temporal locality — a location referenced now will likely be referenced again soon. Cause: loops, recursion, repeatedly used variables and subroutines. Exploited by: keeping recently used data in the upper levels.
• Spatial locality — locations near a referenced one will likely be referenced soon. Cause: sequential instruction execution, array traversal, contiguous data structures. Exploited by: transferring whole blocks rather than single words.
• Sequential locality — a special case of spatial locality: instructions execute in increasing address order unless a branch occurs. Exploited by: instruction prefetching.

The 90/10 rule of thumb: a program typically spends about 90% of its execution time in about 10% of its code. That 10% fits comfortably in cache, which is why small caches produce large gains.

2.1 Two Governing Principles

• Inclusion property — data present at level i is also present at level i+1. Registers ⊂ L1 ⊂ L2 ⊂ Main memory ⊂ Disk. This simplifies coherence, though some designs use exclusive caches to avoid duplication.
• Coherence property — copies of the same data at different levels must be kept consistent. Enforced by write-through or write-back policies (see Cache Memory) and, in multiprocessors, by protocols such as MESI.

---

SECTION 3 — Levels in Detail

3.1 Registers

Fastest storage, physically inside the CPU datapath, accessible in a single cycle with no addressing overhead. Typically 16–32 general-purpose registers of 32 or 64 bits. Allocated by the compiler, which is why register pressure is a compiler-optimisation concern.

3.2 Cache (L1 / L2 / L3)

SRAM buffers bridging the CPU–DRAM speed gap.

• L1 — smallest and fastest, split into separate instruction and data caches (a Modified Harvard arrangement — see Harvard and Non-Neumann Architecture). Private to each core.
• L2 — larger, unified, usually private per core.
• L3 — largest, shared across all cores, which also makes it the medium for inter-core data sharing.

Fully covered in Cache Memory.

3.3 Main Memory (DRAM)

The working store holding running programs and their data. Volatile. Slower than cache but far denser and cheaper. See Memory Organization for SRAM vs DRAM and chip interfacing.

3.4 Virtual Memory ⭐

Virtual memory extends the hierarchy onto disk, letting a program use more address space than the machine has physical RAM.

• Paging — virtual address space is divided into fixed-size pages (commonly 4 KB); physical memory into equally sized frames. A page table maps pages to frames.
• Page fault — the referenced page is not in physical memory; the OS fetches it from disk. Extremely expensive (milliseconds versus nanoseconds), so page-fault rates must be kept minuscule.
• TLB (Translation Lookaside Buffer) — a small fully associative cache of recent page-table entries. Without it, every memory reference would require an extra memory access just to read the page table.
• Thrashing — when the working set exceeds available frames, the system spends more time paging than computing. Throughput collapses.

Cache vs Virtual Memory — a favourite comparison

The key insight: cache and virtual memory apply the same hierarchy principle at different scales — but because the disk penalty is roughly 100,000× the DRAM penalty, virtual memory must use full associativity and sophisticated replacement, whereas cache can afford simpler schemes.

3.5 Secondary and Tertiary Storage

SSDs and hard disks provide non-volatile bulk storage; tape and cloud archives form the tertiary level. See External Memory.

---

SECTION 4 — Formulas (Derived, Explained, Extended to More Levels)

One idea builds every formula on this page:

$$\text{Average time} = \sum (\text{Probability of a case}) \times (\text{Time that case costs})$$

🗣️ In simple words: list every possible case (hit here, miss here and hit there, …), write how often it happens and how long it takes, multiply, and add. If you forget a formula in the exam hall, rebuild it this way.

4.1 Building Blocks — Hit Ratio and Miss Ratio

What it finds: how often the faster level already has the data.

$$H = \frac{\text{Hits}}{\text{Total accesses}} = \frac{\text{Hits}}{\text{Hits} + \text{Misses}} \qquad \text{Miss ratio} = 1 - H$$

• Local hit ratio — out of the accesses that reach a level, the fraction found there. Exam values for L2, L3 … are local unless stated.
• Global hit ratio — out of all CPU accesses, the fraction served by that level.

$$H_{2,\,global} = (1-H_1)\,H_2$$

🗣️ In simple words: if L1 hits 80% and L2 hits 90% of what reaches it, L2 actually serves only 20% × 90% = 18% of all accesses.

4.2 Two Levels — Simultaneous vs Hierarchical

4.2.1 The Difference First

If the question names neither, write your assumption in one line before solving.

4.2.2 Simultaneous Access — Derivation

What it finds: average time per access when cache and memory start searching together.

Step 1: List the cases

• Hit → probability $H$, time $T_1$
• Miss → probability $1-H$, time $T_2$ (memory was already searching, so no extra cache time)

Step 2: Probability × time, then add

$$T_{eff} = H\,T_1 + (1-H)\,T_2$$

Step 3: Simplify

$$\begin{aligned} T_{eff} &= H T_1 + T_2 - H T_2 \\ &= T_2 - H\,(T_2 - T_1) \end{aligned}$$

🗣️ In simple words: start from slow memory time, and every hit saves you $(T_2 - T_1)$.

4.2.3 Hierarchical Access — Derivation

What it finds: average time per access when memory is checked only after a cache miss.

Step 1: List the cases

• Hit → probability $H$, time $T_1$
• Miss → probability $1-H$, time $T_1 + T_2$

Step 2: Probability × time, then add

$$T_{eff} = H\,T_1 + (1-H)\,(T_1 + T_2)$$

Step 3: Simplify

$$\begin{aligned} T_{eff} &= H T_1 + T_1 + T_2 - H T_1 - H T_2 \\ &= T_1 + T_2 - H T_2 \\ &= T_1 + (1-H)\,T_2 \end{aligned}$$

🗣️ In simple words: everyone pays the cache time; only the misses also pay memory time.

This is the textbook AMAT formula:

$$AMAT = \text{Hit time} + \text{Miss rate} \times \text{Miss penalty}$$

4.2.4 Gap Between the Two Models

$$\begin{aligned} T_{hier} - T_{sim} &= \big[T_1 + (1-H)T_2\big] - \big[H T_1 + (1-H)T_2\big] \\ &= (1-H)\,T_1 \end{aligned}$$

🗣️ In simple words: the difference is just the cache time wasted on misses. (Numericals 1 and 2: $0.1 \times 10 = 1$ ns.)

4.3 Three Levels — Derivation

• $H_1, H_2$ = local hit ratios of L1 and L2; main memory always has the data, so $H_3 = 1$
• $T_1, T_2, T_3$ = access times of L1, L2, memory

4.3.1 Hierarchical (Three Levels)

Step 1: List the cases

Step 2: Expanded form

$$T_{eff} = H_1T_1 + (1-H_1)H_2(T_1+T_2) + (1-H_1)(1-H_2)(T_1+T_2+T_3)$$

Step 3: Collect each time term

• $T_1$ appears in all three cases → coefficient $H_1 + (1-H_1)H_2 + (1-H_1)(1-H_2) = 1$
• $T_2$ appears in cases 2 and 3 → coefficient $(1-H_1)H_2 + (1-H_1)(1-H_2) = (1-H_1)$
• $T_3$ appears only in case 3 → coefficient $(1-H_1)(1-H_2)$

Step 4: Simplified form

$$T_{eff} = T_1 + (1-H_1)\,T_2 + (1-H_1)(1-H_2)\,T_3$$

Step 5: Nested form (exam method — innermost bracket first)

$$T_{eff} = T_1 + (1-H_1)\big[\,T_2 + (1-H_2)\,T_3\,\big]$$

🗣️ In simple words: each level's time is multiplied by the fraction of accesses that get down to that level. Check with Numerical 3: $2 + (0.2)(10) + (0.2)(0.1)(100) = 2 + 2 + 2 = 6$ ns.

4.3.2 Simultaneous (Three Levels)

Each case pays only the time of the level where the data is found:

$$T_{eff} = H_1T_1 + (1-H_1)H_2\,T_2 + (1-H_1)(1-H_2)\,T_3$$

Same data as Numerical 3:

$$T_{eff} = (0.8)(2) + (0.2)(0.9)(10) + (0.2)(0.1)(100) = 1.6 + 1.8 + 2 = 5.4\,\text{ns}$$

(versus 6 ns hierarchical)

4.4 General Formula for n Levels ⭐

Step 1: Probability of reaching level i (missed every level above it)

$$P_1 = 1, \qquad P_i = (1-H_1)(1-H_2)\cdots(1-H_{i-1})$$

Step 2: Hierarchical, n levels (each level's time × chance of reaching it)

$$T_{eff} = \sum_{i=1}^{n} P_i\,T_i = T_1 + (1-H_1)T_2 + (1-H_1)(1-H_2)T_3 + \dots + (1-H_1)\cdots(1-H_{n-1})\,T_n$$

Step 3: Simultaneous, n levels (each level's time × chance the data is found exactly there, with $H_n = 1$)

$$T_{eff} = \sum_{i=1}^{n} P_i\,H_i\,T_i = H_1T_1 + (1-H_1)H_2T_2 + \dots + (1-H_1)\cdots(1-H_{n-1})\,T_n$$

Step 4: Nested hierarchical form (fastest by hand)

$$T_{eff} = T_1 + (1-H_1)\Big[T_2 + (1-H_2)\Big[T_3 + \dots + (1-H_{n-1})\,T_n\Big]\Big]$$

Four levels written out (Registers, L1, L2, memory):

$$T_{eff} = T_R + (1-H_R)T_{L1} + (1-H_R)(1-H_{L1})T_{L2} + (1-H_R)(1-H_{L1})(1-H_{L2})T_{mem}$$

Check with Numerical 4: $0.5 + (0.5)(2) + (0.5)(0.1)(10) + (0.5)(0.1)(0.05)(80) = 0.5 + 1 + 0.5 + 0.2 = 2.2$ ns.

4.5 Reverse Formulas — Finding the Hit Ratio

What it finds: the hit ratio needed to reach a target $T_{eff}$.

Simultaneous — from $T_{eff} = T_2 - H(T_2 - T_1)$:

$$H = \frac{T_2 - T_{eff}}{T_2 - T_1}$$

Hierarchical — from $T_{eff} = T_1 + (1-H)T_2$:

$$H = 1 - \frac{T_{eff} - T_1}{T_2}$$

Check with Numerical 5 (simultaneous): $H = (120 - 20)/(120 - 8) = 100/112 = 0.8929$.

4.6 Virtual Memory Formulas

4.6.1 TLB, No Page Fault — Derivation

What it finds: average time to get one data word when addresses must be translated.

Step 1: List the cases

• TLB hit → probability $H$, time $T_{TLB} + T_{mem}$ (translation found, then read data)
• TLB miss → probability $1-H$, time $T_{TLB} + T_{mem} + T_{mem}$ (read page table from memory, then read data)

Step 2: Probability × time

$$EAT = H\,(T_{TLB} + T_{mem}) + (1-H)\,(T_{TLB} + 2\,T_{mem})$$

Step 3: Simplify

$$EAT = T_{TLB} + T_{mem} + (1-H)\,T_{mem} = T_{TLB} + (2-H)\,T_{mem}$$

Without any TLB: every access reads the page table first.

$$EAT_{no\,TLB} = 2\,T_{mem}$$

🗣️ In simple words: everyone pays TLB + data access; only TLB misses pay one extra memory trip. Check with Numerical 6: $1 + (2 - 0.9)(50) = 56$ ns.

4.6.2 More Levels — k-Level Page Table

A TLB miss now walks $k$ tables, one memory access per level:

$$EAT = H\,(T_{TLB} + T_{mem}) + (1-H)\big(T_{TLB} + (k+1)\,T_{mem}\big)$$ $$EAT = T_{TLB} + T_{mem} + (1-H)\,k\,T_{mem}$$

• $k = 1$ gives back the formula in 4.6.1.
• Example (Numerical 6 data, 2-level table): $1 + 50 + (0.1)(2)(50) = 61$ ns.
• Without a TLB: $EAT = (k+1)\,T_{mem}$.

4.6.3 Page Faults — Derivation

Step 1: List the cases

• No fault → probability $1-p$, time $T_{mem}$
• Fault → probability $p$, time $T_{fault}$ (disk read + restart)

Step 2: Probability × time

$$EAT = (1-p)\,T_{mem} + p\,T_{fault} = T_{mem} + p\,(T_{fault} - T_{mem})$$

Step 3: Reverse — maximum allowed fault rate

$$p = \frac{EAT - T_{mem}}{T_{fault} - T_{mem}}$$

Check with Numerical 8: $p = (110 - 100)/(10{,}000{,}000 - 100) \approx 10^{-6}$.

Dirty-page variant ($d$ = fraction of victim pages that were modified and must be written back):

$$T_{fault} = (1-d)\,T_{clean} + d\,T_{dirty}$$

TLB + page fault together (simple combined model):

$$EAT = (1-p)\big[T_{TLB} + (2-H)\,T_{mem}\big] + p\,T_{fault}$$

4.7 Paging Size Formulas

What they find: how a virtual address is split and how big the page table is.

• Offset bits — must name every byte inside one page:

$$d = \log_2(\text{Page size})$$

• Page number bits and number of pages:

$$p = \text{VA bits} - d \qquad \text{Pages} = 2^{p} = \frac{\text{Virtual address space}}{\text{Page size}}$$

• Frames and frame number bits:

$$\text{Frames} = \frac{\text{Physical memory}}{\text{Page size}} \qquad f = \log_2(\text{Frames}) = \text{PA bits} - d$$

• Page table (one entry per page):

$$\text{Entries} = \text{Pages} \qquad \text{Page table size} = \text{Pages} \times \text{Entry size}$$

• More levels — multi-level page table:

$$\text{Entries per table page} = \frac{\text{Page size}}{\text{Entry size}} \qquad \text{Levels} = \left\lceil \frac{p}{\log_2(\text{Entries per table page})} \right\rceil$$

Example: 32-bit VA, 4 KB pages, 4-byte entries → $p = 20$, entries per table page $= 4096/4 = 1024 = 2^{10}$, levels $= \lceil 20/10 \rceil = 2$.

4.8 Cost and Performance Formulas

Average cost per bit (weighted average — the big cheap level dominates):

$$\bar{C} = \frac{C_1S_1 + C_2S_2 + \dots + C_nS_n}{S_1 + S_2 + \dots + S_n} = \frac{\sum C_i S_i}{\sum S_i}$$

• $C_i$ = cost per bit (or per MB) at level $i$, $S_i$ = size of level $i$

Speedup (how many times faster the hierarchy is than the slow level alone):

$$\text{Speedup} = \frac{T_{without}}{T_{with}} = \frac{T_{slowest}}{T_{eff}}$$

Percentage time saved:

$$\text{Saved} = \frac{T_{without} - T_{with}}{T_{without}} \times 100$$

Access efficiency (how close the system is to pure cache speed; ideal = 1):

$$e = \frac{T_1}{T_{eff}}$$

Example (Numerical 1): $e = 10/19 = 0.53$.

4.9 One-Look Formula Sheet

4.10 Easy Ways to Remember the Formulas 🧠

4.10.1 The Master Key — "Chance × Time, Add Them Up"

• Analogy: your daily trip to the office. 80% of days the road is clear (20 min), 20% of days there is traffic (60 min). Average = 0.8 × 20 + 0.2 × 60 = 28 min. Every memory formula works the same way.
• Exam routine (30 seconds): draw a small table with Case | Chance | Time, multiply across, add down. If you forget a formula, this rebuilds it.

4.10.2 Simultaneous vs Hierarchical — The Book Search

• Hierarchical = check the shelf first, then go to the library. If the book is not on the shelf, you have wasted shelf-checking time and still pay the library trip → miss costs $T_1 + T_2$.
• Simultaneous = send your brother to the library while you check the shelf. If the shelf fails, the library answer is already on its way → miss costs only $T_2$.
• Memory hook: "Hierarchical = Har baar cache" — every access pays the cache time. "Simultaneous = Skip" — a miss skips the cache time.
• Sanity check: hierarchical answer is always bigger than simultaneous by $(1-H)T_1$ — the wasted shelf checks.

4.10.3 The Short Form — "Sab ka T₁, Missers ka T₂"

$$T_{eff} = T_1 + (1-H)\,T_2$$

• Everyone pays $T_1$ (all accesses check the cache).
• Only the missers pay $T_2$ (only $1-H$ go down to memory).
• Same sentence as AMAT: Hit time + Miss rate × Miss penalty.
• Simultaneous short form $T_2 - H(T_2 - T_1)$ → "start slow, every hit gives a discount of $(T_2 - T_1)$" — like a shop price minus a discount on each lucky day.

4.10.4 Multi-Level — The Staircase / Waterfall

• Analogy: searching for your keys — first your pocket, then your room, then the whole house. Everyone searches the pocket; only those who fail go to the room; only those who fail again search the house.
• Rule: each level's time × the people who reached that level.
• Hook: "Keep multiplying the misses." The chance to reach the next floor is the previous misses multiplied together:

$$1 \;\rightarrow\; (1-H_1) \;\rightarrow\; (1-H_1)(1-H_2) \;\rightarrow\; (1-H_1)(1-H_2)(1-H_3)\dots$$

• Write those multipliers in front of $T_1, T_2, T_3, \dots$ and add — that is the n-level hierarchical formula.
• Simultaneous version: same multipliers, but also multiply by that level's own $H$ (data is found there), and the last level has $H = 1$.
• Nested form hook: "Open the innermost bracket first" — like peeling an onion from the inside out.

4.10.5 TLB — The Phone Diary

• Analogy: TLB = your small pocket diary of phone numbers; page table = the big phone directory kept at home (in memory).
• Number in the pocket diary (TLB hit) → just make the call → 1 memory trip.
• Not in the diary (TLB miss) → go home, look in the directory, then call → 2 memory trips.
• Hook: "Miss = one extra trip." Hence the short form "two minus H":

$$EAT = T_{TLB} + (2-H)\,T_{mem}$$

At most 2 trips; your hits cut part of the second trip.

• k-level page table = a directory spread over k cupboards → a miss costs k extra trips → $(1-H)\,k\,T_{mem}$.
• No TLB at all → always go home first → $2T_{mem}$ (or $(k+1)T_{mem}$).

4.10.6 Page Fault — "Small p, Giant Penalty"

• Analogy: a bus that is on time 999 days out of 1,000, but on the 1,000th day it breaks down and you wait a whole week. Your average trip time is ruined by that one day.
• A page fault is ~100,000× slower than memory, so even $p = 0.001$ makes the system ~100× slower.
• Hook: in $EAT = T_{mem} + p(T_{fault} - T_{mem})$, tiny p × huge penalty still dominates — that is why p must be about 1 in a million.

4.10.7 Reverse Formulas — "Gap Covered ÷ Total Gap"

$$H = \frac{T_2 - T_{eff}}{T_2 - T_1}$$

• Analogy: a road from slow ($T_2$) to fast ($T_1$). The hit ratio is how far along the road your target $T_{eff}$ has come: distance covered ÷ full distance.
• Same logic for the page fault rate: $p = (EAT - T_{mem})/(T_{fault} - T_{mem})$ — allowed extra time ÷ extra cost of one fault.

4.10.8 Paging Bits — The House Address

• Analogy: a virtual address = street number (page number) + house number on that street (offset).
• Offset = $\log_2$(page size) — you need enough house numbers for every byte in one page. Rest of the bits = page number.
• Hook: "Street changes, house number stays." Translation changes only the page number into a frame number; the offset is copied as it is.
• Page table size = Pages × Entry size — like a class register: number of students × space per line.
• Powers of 2 to know by heart: $2^{10}$ = 1 K, $2^{20}$ = 1 M, $2^{30}$ = 1 G → 4 KB = $2^{12}$, 8 KB = $2^{13}$.

4.10.9 Cost — The Doodh Patti Mix

• Analogy: mix 1 cup of expensive cream with 1,000 cups of ordinary milk — the cost per cup of the mixture is almost the cost of ordinary milk. The big cheap level dominates the average.
• That is the whole hierarchy: cost close to DRAM, speed close to cache.

4.10.10 Speedup — "Old ÷ New"

• Speedup = old time ÷ new time (bigger number on top, answer above 1).
• % saved = (old − new) ÷ old × 100.
• Efficiency = $T_1 \div T_{eff}$ — "how close you are to pure cache speed"; 1 means perfect.

4.10.11 Quick Answer Checks in the Exam ✅

• $T_{eff}$ must lie between the fastest and slowest level — if it doesn't, recheck.
• Hierarchical answer > simultaneous answer for the same data.
• All case chances must add up to 1.
• Convert ms / µs to ns before substituting (1 ms = $10^6$ ns, 1 µs = $10^3$ ns).

4.10.12 Memory Hooks at a Glance

---

SECTION 5 — Solved Numericals

🧮 Numerical 1 — Two-Level Effective Access Time

Q: Cache access time = 10 ns, main memory access time = 100 ns, hit ratio = 0.9. Find the effective access time under simultaneous access.

Step 1: Given

$$H = 0.9,\quad T_1 = 10\,\text{ns},\quad T_2 = 100\,\text{ns}$$

Step 2: Formula (simultaneous access)

$$T_{eff} = H\,T_1 + (1-H)\,T_2$$

Step 3: Substitute and solve

$$\begin{aligned} T_{eff} &= (0.9 \times 10) + (0.1 \times 100) \\ &= 9 + 10 \\ &= 19\,\text{ns} \end{aligned}$$

Step 4: Speedup over memory alone

$$\text{Speedup} = \frac{100}{19} \approx 5.26$$

Answer: 19 ns.

Interpretation: memory alone would cost 100 ns per access; the hierarchy delivers 19 ns — a 5.26× speedup from a cache far smaller than main memory.

---

🧮 Numerical 2 — Hierarchical Access (the miss pays both levels)

Q: Same values as Numerical 1, but memory is consulted only after the cache lookup fails.

Step 1: Given (same values as Numerical 1)

$$H = 0.9,\quad T_1 = 10\,\text{ns},\quad T_2 = 100\,\text{ns}$$

Step 2: Formula (hierarchical access, a miss pays the cache lookup and then memory)

$$T_{eff} = H\,T_1 + (1-H)\,(T_1 + T_2)$$

Step 3: Substitute and solve

$$\begin{aligned} T_{eff} &= (0.9 \times 10) + 0.1 \times (10 + 100) \\ &= 9 + (0.1 \times 110) \\ &= 9 + 11 \\ &= 20\,\text{ns} \end{aligned}$$

Answer: 20 ns — 1 ns more than Numerical 1, exactly the wasted cache lookup on the 10% of accesses that miss.

⚠️ Read the question carefully to identify which access model applies. This pair is a deliberate examiner trap.

---

🧮 Numerical 3 — Three-Level Hierarchy ⭐

Q: A system has L1 cache (2 ns, hit ratio 0.80), L2 cache (10 ns, hit ratio 0.90 for accesses reaching it), and main memory (100 ns). Find the effective access time under hierarchical access.

Step 1: Given

$$T_{L1} = 2\,\text{ns},\; H_{L1} = 0.80 \qquad T_{L2} = 10\,\text{ns},\; H_{L2} = 0.90 \qquad T_{mem} = 100\,\text{ns}$$

Step 2: Resolve the innermost level first (L2 together with memory below it)

$$\begin{aligned} T_{L2eff} &= T_{L2} + (1-H_{L2})\,T_{mem} \\ &= 10 + (0.10 \times 100) \\ &= 10 + 10 \\ &= 20\,\text{ns} \end{aligned}$$

Step 3: Combine with L1

$$\begin{aligned} T_{eff} &= T_{L1} + (1-H_{L1})\,T_{L2eff} \\ &= 2 + (0.20 \times 20) \\ &= 2 + 4 \\ &= 6\,\text{ns} \end{aligned}$$

Answer: 6 ns.

Access distribution worth stating:

$$\begin{aligned} \text{Served by L1} &= 80\% \\ \text{Served by L2} &= 20\% \times 90\% = 18\% \\ \text{Reached memory} &= 20\% \times 10\% = 2\% \end{aligned}$$

Only 2% of accesses ever touch DRAM — that is the entire value proposition of a multi-level hierarchy.

---

🧮 Numerical 4 — Four-Level Hierarchy Including Registers

Q: Registers 0.5 ns (hit 0.5), L1 2 ns (hit 0.9), L2 10 ns (hit 0.95), memory 80 ns. Find effective access time, hierarchical.

Step 1: Given

$$T_R = 0.5,\; H_R = 0.5 \qquad T_{L1} = 2,\; H_{L1} = 0.9 \qquad T_{L2} = 10,\; H_{L2} = 0.95 \qquad T_{mem} = 80 \quad (\text{all in ns})$$

Step 2: L2 subsystem (innermost)

$$T_{L2eff} = 10 + (0.05 \times 80) = 10 + 4 = 14\,\text{ns}$$

Step 3: L1 subsystem

$$T_{L1eff} = 2 + (0.10 \times 14) = 2 + 1.4 = 3.4\,\text{ns}$$

Step 4: Register level (outermost)

$$\begin{aligned} T_{eff} &= 0.5 + (0.50 \times 3.4) \\ &= 0.5 + 1.7 \\ &= 2.2\,\text{ns} \end{aligned}$$

Step 5: Improvement over raw memory

$$\frac{80}{2.2} \approx 36\times$$

Answer: 2.2 ns — against 80 ns for raw memory, a 36× improvement. Note the method: always resolve the innermost level first and work outward.

---

🧮 Numerical 5 — Required Hit Ratio (reverse problem)

Q: Cache = 8 ns, main memory = 120 ns. What hit ratio achieves an effective access time of 20 ns?

Step 1: Set up the weighted-average equation

$$8H + (1-H)\times 120 = 20$$

Step 2: Expand and collect the H terms

$$\begin{aligned} 8H + 120 - 120H &= 20 \\ -112H &= 20 - 120 \\ -112H &= -100 \end{aligned}$$

Step 3: Solve for H

$$H = \frac{100}{112} = 0.8929$$

Answer: 89.29% hit ratio required.

The method for every reverse problem is identical: write the weighted-average equation, expand, and solve for the unknown.

---

🧮 Numerical 6 — Virtual Memory with TLB ⭐

Q: TLB access time = 1 ns, main memory access time = 50 ns, TLB hit ratio = 90%. Assume no page faults. Find the effective memory access time.

Step 1: Given

$$T_{TLB} = 1\,\text{ns},\quad T_{mem} = 50\,\text{ns},\quad H_{TLB} = 0.90$$

Step 2: Case A, TLB hit (search TLB, get the frame number, access memory)

$$T_{hit} = T_{TLB} + T_{mem} = 1 + 50 = 51\,\text{ns}$$

Step 3: Case B, TLB miss (search TLB and fail, read the page table from memory, then access the data)

$$T_{miss} = T_{TLB} + T_{mem} + T_{mem} = 1 + 50 + 50 = 101\,\text{ns}$$

Step 4: Weighted average

$$\begin{aligned} EAT &= (0.90 \times 51) + (0.10 \times 101) \\ &= 45.9 + 10.1 \\ &= 56\,\text{ns} \end{aligned}$$

Answer: 56 ns.

The point: a TLB miss costs an extra full memory access because the page table itself lives in memory. Without any TLB, every reference would cost 100 ns — the TLB alone saves 44%.

---

🧮 Numerical 7 — Page Fault Impact ⭐

Q: Memory access time = 100 ns. A page fault takes 10 ms to service. If the page fault rate is 0.001 (1 in 1,000), find the effective access time and the slowdown.

Step 1: Given, with units converted to ns

$$T_{mem} = 100\,\text{ns},\quad p = 0.001,\quad T_{fault} = 10\,\text{ms} = 10{,}000{,}000\,\text{ns}$$

Step 2: Effective access time

$$\begin{aligned} EAT &= (1-p)\,T_{mem} + p\,T_{fault} \\ &= (0.999 \times 100) + (0.001 \times 10{,}000{,}000) \\ &= 99.9 + 10{,}000 \\ &= 10{,}099.9\,\text{ns} \approx 10.1\,\mu\text{s} \end{aligned}$$

Step 3: Slowdown

$$\frac{10{,}099.9}{100} \approx 101\times$$

Answer: ≈10.1 μs, a 101× slowdown.

Interpretation: a page fault rate of just 0.1% makes the system 101 times slower. This is why acceptable page fault rates are on the order of 1 in 10⁶ or lower, and why thrashing is catastrophic rather than merely inconvenient.

---

🧮 Numerical 8 — Acceptable Page Fault Rate (reverse)

Q: Using the values above, what page fault rate keeps the effective access time within 10% of the ideal 100 ns (i.e. at most 110 ns)?

Step 1: Set up the equation (EAT must not exceed 110 ns)

$$(1-p)(100) + p\,(10{,}000{,}000) = 110$$

Step 2: Expand and collect the p terms

$$\begin{aligned} 100 - 100p + 10{,}000{,}000p &= 110 \\ 9{,}999{,}900\,p &= 10 \end{aligned}$$

Step 3: Solve for p

$$p = \frac{10}{9{,}999{,}900} \approx 1\times 10^{-6} \quad (\text{about 1 in 1,000,000})$$

Answer: roughly one fault per million accesses. This calculation is the standard way of demonstrating just how rare page faults must be, and it is a frequently set exam problem.

---

🧮 Numerical 9 — Page Table Sizing

Q: A system has a 32-bit virtual address space, 4 KB pages, and 4-byte page table entries. Find the number of pages and the page table size.

Step 1: Virtual address space and page size

$$\text{Virtual space} = 2^{32}\,\text{bytes} = 4\,\text{GB} \qquad \text{Page size} = 4\,\text{KB} = 2^{12}\,\text{bytes}$$

Step 2: Number of pages

$$\text{Pages} = \frac{2^{32}}{2^{12}} = 2^{20} = 1{,}048{,}576$$

Step 3: Page table size

$$\begin{aligned} \text{Size} &= 2^{20} \times 4\,\text{bytes} \\ &= 4{,}194{,}304\,\text{bytes} \\ &= 4\,\text{MB} \end{aligned}$$

Answer: 1,048,576 pages; page table = 4 MB per process.

Follow-up worth adding: 4 MB per process is unacceptable when hundreds of processes run, which is precisely why real systems use multi-level page tables or inverted page tables rather than one flat table.

---

🧮 Numerical 10 — Address Splitting for Paging

Q: A 32-bit virtual address with 8 KB pages. How many bits are the page number and the offset? How many frames exist in 512 MB of physical memory?

Step 1: Offset bits (page size $8\,\text{KB} = 2^{13}$ bytes)

$$\text{Offset} = 13\,\text{bits}$$

Step 2: Page number bits

$$32 - 13 = 19\,\text{bits} \;\Rightarrow\; 2^{19} = 524{,}288\ \text{virtual pages}$$

Step 3: Number of physical frames

$$\begin{aligned} \text{Frames} &= \frac{512\,\text{MB}}{8\,\text{KB}} = \frac{512 \times 2^{20}}{8 \times 2^{10}} \\ &= \frac{536{,}870{,}912}{8{,}192} = 65{,}536 \end{aligned}$$

Step 4: Frame number bits

$$\log_2(65{,}536) = 16\,\text{bits}$$

Answer: page number 19 bits, offset 13 bits; 65,536 frames requiring 16 frame-number bits.

Note the offset is the same width in both virtual and physical addresses — only the page/frame number is translated. This is a commonly tested fact.

---

🧮 Numerical 11 — Average Cost per Bit of a Hierarchy

Q: A system has 1 MB of cache costing Rs 500 per MB and 1,000 MB of DRAM costing Rs 2 per MB. Find the average cost per MB of the combined memory system.

Step 1: Total cost

$$\begin{aligned} \text{Cache} &= 1 \times 500 = 500 \\ \text{DRAM} &= 1000 \times 2 = 2{,}000 \\ \text{Total} &= 2{,}500\ \text{rupees} \end{aligned}$$

Step 2: Total capacity

$$1 + 1000 = 1{,}001\,\text{MB}$$

Step 3: Average cost per MB

$$\bar{C} = \frac{\sum C_iS_i}{\sum S_i} = \frac{2{,}500}{1{,}001} \approx 2.50\ \text{rupees per MB}$$

Answer: Rs 2.50 per MB.

The whole hierarchy argument in one number: the system costs almost as little per MB as pure DRAM (Rs 2) while performing close to cache speed. Achieving 1,001 MB of pure cache would have cost Rs 500,500 — 200× more.

---

🧮 Numerical 12 — Speedup Delivered by the Hierarchy

Q: Without any cache, every access costs 90 ns. With a two-level cache the effective access time is 6 ns. Find the speedup and the percentage of time saved.

Step 1: Speedup

$$\text{Speedup} = \frac{T_{without}}{T_{with}} = \frac{90}{6} = 15\times$$

Step 2: Percentage of time saved

$$\begin{aligned} \text{Saved} &= \frac{90 - 6}{90} \times 100 \\ &= \frac{84}{90} \times 100 \\ &= 93.3\% \end{aligned}$$

Answer: 15× speedup; 93.3% of memory access time eliminated.

---

SECTION 6 — Exam Guidance

🎯 CSS Exam Angle

The memory hierarchy is examined in three ways:

1. The diagram question — draw the pyramid with speed, size, and cost annotated at each level. Quick, reliable marks. Always label the three trends (speed ↓, capacity ↑, cost/bit ↓ as you descend) and add the fourth that most candidates omit: frequency of access decreases.
2. The justification question — "why does a memory hierarchy work?" The answer is locality of reference, and a strong response names temporal, spatial, and sequential locality with a concrete cause for each (loops, arrays, sequential execution).
3. The numerical — effective access time across two, three, or four levels, or a virtual-memory/TLB/page-fault calculation.

Method for every multi-level numerical: resolve the innermost level first, then work outward. Attempting to compute all levels simultaneously is where candidates go wrong.

Always state the access model (simultaneous or hierarchical) you are assuming before substituting — if the question is ambiguous, say which you assume and why. Examiners reward that explicitly.

🔁 Repeated CSS Questions

1. Draw and explain the memory hierarchy, showing the speed–capacity–cost trade-off. (Very frequently repeated)
2. Why does the memory hierarchy work? Explain locality of reference with examples. (Frequently repeated)
3. Calculate the effective access time for a two-level or three-level memory hierarchy. (Numerical — frequently repeated)
4. Differentiate between cache memory and virtual memory. (Frequently repeated)
5. What is a TLB? Calculate effective access time with and without a TLB. (Numerical)
6. What is a page fault? Show numerically why the page fault rate must be extremely low. (Numerical)
7. Explain thrashing and its effect on system performance.
8. Calculate page table size given the virtual address space, page size, and entry size. (Numerical)
9. Explain the inclusion and coherence properties of a memory hierarchy.
10. Which levels of the hierarchy are managed by hardware, the compiler, and the operating system?

⚠️ MCQ Traps

• Cost per bit decreases as you go down the hierarchy, while total cost of that level may rise — the two are different quantities. Cost per bit is what falls.
• Cache is managed by hardware; virtual memory is managed by the operating system. This is the cleanest distinguishing fact between them.
• A cache miss costs tens of cycles; a page fault costs milliseconds — a difference of roughly five orders of magnitude, not a matter of degree.
• A TLB miss costs one extra memory access, not a page fault. TLB miss and page fault are different events: a TLB miss means the translation is absent; a page fault means the page is absent.
• The page offset is not translated — it is identical in the virtual and physical address. Only the page number becomes a frame number.
• Registers are managed by the compiler, not by hardware or the OS.
• Locality is a property of programs, not of hardware. The hierarchy exploits locality; it does not create it. A program with genuinely random access patterns defeats the hierarchy entirely.
• Increasing cache size does not always reduce misses proportionally — compulsory misses are unaffected by size, and gains flatten once the working set fits.
• The hierarchy provides the illusion of a large fast memory, not an actual one — the phrasing examiners look for.