S5-2.4 Memory Organization

What this is and why it exists

Fast memory is expensive. Large memory is slow. No single technology gives you both, so machines use several at once and move data between them.

That arrangement is the memory hierarchy, and it works for one reason that is not a law of nature. Real programs come back to the same data and the same instructions.

The vocabulary

• Memory hierarchy — several levels of storage, from small and fast to large and slow.
• Primary memory — the memory the processor addresses directly.
• Auxiliary memory — the larger, slower storage behind it, such as a disk.
• Locality — the observed habit of programs to reuse recent data and nearby addresses.
• Cache — a small fast memory holding copies of recently used items.
• Associative memory — memory searched by content rather than by address.
• Hit and miss — whether the item asked for was in the cache or not.
• Direct mapping — each memory block has exactly one cache line it may occupy.
• Fully associative mapping — a block may occupy any line.
• Set-associative mapping — a block may occupy any line within one small set.
• Virtual memory — an address space larger than the physical memory, backed by disk.
• Page — a fixed-size unit of that address space.
• Page table — the record of where each page currently lives.

The mental model

Draw the pyramid once and keep it in view. Registers at the top, then cache, then main memory, then disk. Speed falls as you go down and size rises. Every idea in this topic is about moving data between two neighbouring levels.

Caching works because of locality. A program that has recently used an address is likely to use it again soon. It is also likely to use the neighbouring addresses. That is an observation about real programs, not a theorem. Without it the whole arrangement would collapse, and it is worth pausing on rather than accepting quietly.

Mapping is the design decision. When a block of memory is brought into the cache, where may it go?

Direct mapping gives each block exactly one permitted line, chosen from the address. Lookup is one comparison, so the hardware is cheap and fast. The cost is conflict: two blocks that map to the same line evict each other, even while the rest of the cache sits empty.

Fully associative mapping lets a block go anywhere. Conflicts disappear. The cost is the search, because every line must be compared at once. That is what associative memory is for, and it is expensive, which is why fully associative caches stay small.

Set-associative mapping is the compromise almost every real machine uses. The address chooses a small set, and the block may occupy any line within it. Comparing a handful of lines is affordable, and conflicts become rare. Translate one address under all three schemes and the trade between hardware cost and conflict misses becomes obvious in a way prose cannot manage.

Virtual memory is the same idea one level down. Main memory caches the disk. The address space is cut into fixed-size pages, and a page table records where each page currently is. When a program touches a page that is not in memory, the hardware raises a fault. The operating system fetches the page, and the instruction is restarted. Because the two levels are the same idea, learning the parallel saves learning it twice. The difference is the cost of a miss, which is enormous here. So the policies are more careful, and more of the work is done in software.

Memory management is where that software lives. It decides what is loaded, what is evicted, and which program may see which page. It is the point where the hardware in this topic meets the operating system you will meet elsewhere.

What you should now be able to explain or do

Draw the memory hierarchy and say what makes each level necessary. Explain why caching depends on an empirical fact rather than a proof. Translate one address under direct, fully associative and set-associative mapping. Say why set-associative mapping is the usual choice. Describe page-based address translation and explain why a page fault is handled in software while a cache miss is not.

Check yourself