A Dialogue on Memory Virtualization

Part I 💬 Dialogue OSTEP pp. 119–120 · ~6 min read

Virtual memory exists mostly for the programmer’s convenience; keeping programs out of each other’s memory is the second reason, not the first.

Why this matters

That ordering explains the scale of what follows. All the hardware and bookkeeping of the coming chapters exist to maintain a convenient fiction — a large private memory that no program actually has — and the fiction earns its cost because programming without it is intolerable.

The CPU is virtualized; surely that’s the end of it?

Student:So, are we done with virtualization?
Professor:No!
Student:Hey, no reason to get so excited; I was just asking a question. Students are supposed to do that, right?
Professor:Well, professors do always say that, but really they mean this: ask questions, if they are good questions, and you have actually put a little thought into them.
Student:Well, that sure takes the wind out of my sails.
Professor:Mission accomplished. In any case, we are not nearly done with virtualization! Rather, you have just seen how to virtualize the CPU, but really there is a big monster waiting in the closet: memory. Virtualizing memory is complicated and requires us to understand many more intricate details about how the hardware and OS interact.
Student:That sounds cool. Why is it so hard?
Professor:Well, there are a lot of details, and you have to keep them straight in your head to really develop a mental model of what is going on. We’ll start simple, with very basic techniques like base/bounds, and slowly add complexity to tackle new challenges, including fun topics like TLBs and multi-level page tables. Eventually, we’ll be able to describe the workings of a fully-functional modern virtual memory manager.
👹memory: the monsterin the closetbase/boundsch. 15segmentationch. 16pagingch. 18TLBsch. 19multi-levelch. 20a complete modern VM system(ch. 21–23: swapping, policies, VAX & Linux)the whole trip: virtual address (what your program sees) → physical address (where the data really lives)

The Professor’s roadmap: start simple, add complexity, tame the monster. Orange = virtual (the illusion), lime = physical (the reality) — a color pairing every diagram in the coming chapters reuses.

Student:Neat! Any tips for the poor student, inundated with all of this information and generally sleep-deprived?
Professor:For the sleep deprivation, that’s easy: sleep more (and party less). For understanding virtual memory, start with this: every address generated by a user program is a virtual address. The OS is just providing an illusion to each process, specifically that it has its own large and private memory; with some hardware help, the OS will turn these pretend virtual addresses into real physical addresses, and thus be able to locate the desired information.
Student:OK, I think I can remember that… (to self) every address from a user program is virtual, every address from a user program is virtual, every…
Professor:What are you mumbling about?
Student:Oh nothing… (awkward pause) … Anyway, why does the OS want to provide this illusion again?
Professor:Mostly ease of use: the OS will give each program the view that it has a large contiguous address space to put its code and data into; thus, as a programmer, you never have to worry about things like “where should I store this variable?” because the virtual address space of the program is large and has lots of room for that sort of thing. Life, for a programmer, becomes much more tricky if you have to worry about fitting all of your code and data into a small, crowded memory.
Student:Why else?
Professor:Well, isolation and protection are big deals, too. We don’t want one errant program to be able to read, or worse, overwrite, some other program’s memory, do we?
Student:Probably not. Unless it’s a program written by someone you don’t like.
Professor:Hmmm… I think we might need to add a class on morals and ethics to your schedule for next semester. Perhaps OS class isn’t getting the right message across.
Student:Maybe we should. But remember, it’s not me who taught us that the proper OS response to errant process behavior is to kill the offending process!

Tip: THE MANTRA — chant it like the Student does

Every address generated by a user program is a virtual address. Every pointer you’ve ever printed, every value of p in chapter 2’s mem.c (remember two processes sharing 0x200000?), every stack and heap address in every chapter ahead — virtual, all of it. The OS + hardware translate each one to a physical address on the fly. If you hold onto one idea across the next eleven chapters, hold this one.

If you remember only three things

  • The monster is in the closet because of the volume, not the difficulty. The Professor warns about details to keep straight, not about hard ideas: base and bounds is simple, and the complexity arrives by accumulation.

  • A large contiguous address space is a promise, not a fact. Never having to ask where a variable should go is the product being sold, and it is sold to every program at once.

  • Memory virtualization needs the hardware on every access. The CPU’s mechanisms borrowed hardware at moments — a trap, a timer tick — while translating an address happens on every instruction, which is why this half needs so much more machinery.

Check yourself

1.What is THE mantra the Professor hands the sleep-deprived Student?

2.Why does the OS bother providing each process a large private address space? (Two reasons from the dialogue.)

3.How does the Professor plan to tame the memory monster?

3 questions