What's changed: Initial version
2.2Memory and the Storage Hierarchy
Building on the FE/SG basics of cache and virtual memory, this section works through effective access time and hit-rate calculations precisely and digs deeper into the performance/reliability tradeoff between write-through and write-back. It also covers virtual memory page replacement algorithms (LRU/FIFO), page-fault calculations, and multi-level cache configurations (L1/L2/L3).
Knowing the mechanics of cache memory and virtual memory is not enough for AP's morning exam. You need to reach the level of numerical, procedural judgment: how much does effective access time change when the hit rate shifts, and which page should be evicted given a limited main-memory allocation.
2.2.1Calculating effective access time and hit rate
- Effective access time is computed as the weighted average cache time x hit rate + main memory time x (1 - hit rate). As this formula shows, effective access time can be shortened not only by making the cache itself faster but equally by raising the hit rate. In practice, engineers raise the hit rate by adding cache capacity or by designing around the locality of reference inherent in access patterns.
- Modern processors typically have multiple cache levels—L1, L2, and L3. L1, closest to the CPU, is the fastest and smallest, while L3 is the slowest and largest, applying the storage-hierarchy principle inside the cache itself. A multi-level cache is searched in order—first L1, then L2 if it misses, then L3, and finally main memory—so overall effective access time becomes a multi-level weighted average that accounts for the hit rate at each level.
2.2.2A deeper look at write-through and write-back
| Scheme | Write behavior | Advantage | Disadvantage |
|---|---|---|---|
| Write-through | Writes to the cache and main memory simultaneously | Cache and main memory always match; simple and reliable | Every write also touches main memory, so write performance is lower |
| Write-back | Writes only to the cache; reflects changes to main memory in a batch on eviction | Fewer writes to main memory, so write performance is higher | Cache and main memory become temporarily inconsistent, risking data loss on power failure, etc. |
The staples: effective access time = cache time x hit rate + main memory time x (1 - hit rate); write-through writes simultaneously, prioritizing reliability; write-back writes only to the cache, prioritizing speed at the cost of temporary inconsistency; LRU replaces the page unused for the longest time; FIFO replaces the page that entered first. Effective-access-time calculations involving multi-level caches or multiple conditions are also a recurring pattern.
Let us confirm with concrete numbers how much a hit-rate change moves effective access time. For a system with a cache access time of 5 ns and a main memory access time of 60 ns, at a 95% (0.95) hit rate, effective access time = 5 x 0.95 + 60 x 0.05 = 4.75 + 3 = 7.75 ns. If the hit rate improves by just 3 points to 98% (0.98), effective access time shrinks to 5 x 0.98 + 60 x 0.02 = 4.9 + 1.2 = 6.1 ns. Raising the hit rate by only 3 points improves effective access time by roughly 21% ((7.75 - 6.1) / 7.75), which illustrates why improving the design to raise the hit rate (more capacity, or layout that exploits locality of reference) is often more cost-effective than swapping in a faster cache component. Now consider page replacement algorithms. When virtual memory can hold only a limited number of pages in main memory, loading a new page requires evicting an existing one, and the way that eviction choice is made is the page replacement algorithm. LRU (Least Recently Used) evicts the page that has gone unreferenced for the longest time, based on the empirical heuristic (locality of reference) that recent reference history is a good predictor of future use, and it is widely used in practice. FIFO (First-In First-Out) simply evicts whichever page was loaded into main memory first; it is simple to implement, but has the weakness that a page can be evicted purely for being old, even if it is still being used frequently. A poor page-replacement choice, where an evicted page is needed again immediately and must be reloaded repeatedly, easily leads to thrashing (as covered in FE/SG: frequent page swapping that sharply degrades processing efficiency), so choosing an algorithm suited to the workload's reference pattern matters.
Trap: "if the hit rate stays the same, shortening main memory access time does not change effective access time" is wrong—the formula includes the term main memory time x (1 - hit rate), so a faster main memory lowers the cost of a miss and improves effective access time too. Also, "FIFO considers reference frequency and preferentially keeps frequently used pages" is wrong—FIFO evicts purely by arrival order and does not consider frequency at all (LRU is the one that considers frequency and recency of reference). "Write-back always immediately reflects every write to main memory too" is also wrong—that describes write-through; the essence of write-back is writing only to the cache, with main memory updated in a batch upon eviction.
2.2.3Section summary
- Effective access time = cache time x hit rate + main memory time x (1 - hit rate). A small improvement in hit rate substantially shortens effective access time
- Write-through = simultaneous writes, prioritizes reliability; write-back = writes only to the cache, prioritizes speed but has temporary inconsistency. Multi-level L1/L2/L3 caches are now standard
- LRU evicts the page unreferenced longest (grounded in locality of reference); FIFO evicts the page that arrived first (ignoring frequency). A poor replacement choice invites thrashing
Sign in to track progress — Log in.
Quick check
(just a quick review)Q1. Given a cache access time of 8 ns, a main memory access time of 88 ns, and a hit rate of 90%, what is the effective access time?
Q2. Given a limited number of pages that can be held in main memory, which page replacement algorithm preferentially evicts the page that has gone unreferenced for the longest time, based on reference history?
Q3. Which cache-memory write scheme reflects every write to main memory at the same time, keeping the cache and main memory always consistent and highly reliable, at the cost of write performance?