Standard: Memory
In this lecture we continue looking into memory allocation. We begin with Virtual Memory and how it is used to create the illusion of infinite memory! We then investigate how this illusion is created, and maintained, by a new non-contiguous allocation technique called paging!
📅 March 23, 2026
Memory
Last time we established the critical distinction between logical addresses and physical addresses. Programmers use logical addresses — convenient labels starting at 0 — while hardware uses physical addresses — unique slots in actual memory chips. The MMU sits between these two worlds, translating one to the other so neither side has to compromise.
Let us trace the full pipeline from the code you write all the way to the physical hardware, and see exactly where the MMU draws the line.
Before stepping through the pipeline, watch one invariant: the program keeps the same logical view even when the hardware placement changes underneath it.
Step through the transformation from source code to physical memory. The MMU sits between the logical and physical worlds.
1#[no_mangle]2fn one() -> i32 {3 14}56#[no_mangle]7pub fn main() {8 one();9}
This is what you write. Line numbers, variable names, function names — all human-readable labels. The compiler turns this into machine code next.
This is the core promise of virtual memory: stable addressing for the program even when physical placement is hidden and flexible.
Step through all four phases above. Phases 1 and 2 are the logical side — what you as a programmer create and what the compiler produces. Everything uses logical addresses starting at 0x0000. Phases 3 and 4 are the physical side — where the hardware actually places your code. Notice how one() and main() end up at completely different physical locations, separated by unrelated data. Yet the call [rip + @one] instruction still works because the MMU transparently maps the logical label to its physical location. The programmer never notices.
Recall our discussion of the universal memory concept from LN13 — the theoretical ideal of a single, enormous, fast, cheap memory strip for all computation. We cannot build such hardware (yet), so we are stuck with the multi-strip, multi-speed, multi-cost reality of registers, caches, RAM, SSDs, and HDDs.
But what if, with a little more facade maintenance from our MMU, we could let programmers think and code as though they have a single infinite strip, while the physical implementation remains hidden behind the curtain?
If your MMU is sophisticated enough to maintain this illusion — supporting full logical-to-physical address translation — then you have a system that implements what is called Virtual Memory.
Virtual memory exists first to provide translation, protection, and isolation. One consequence is that the OS can also overcommit memory and move inactive data to backing storage. The core idea:
Before we go further, let us be very clear about what virtual memory is not:
⚠️ Common Misconception: Virtual memory is not inventing new space for storing things. It is not "downloading more RAM." You can only get more memory or storage by purchasing more or better hardware.
The distinction being made is that managing memory (RAM) is hard because it is limited, so we offload the things we do not pick up as often onto storage (SSD/HDD). When virtual memory says it is "placing chunks elsewhere," those chunks are placed on hardware so slow we no longer consider it readily available.
Recall the distinction between storage and memory: all ways to store computations on a system are functionally identical in their capacity to hold data. It is their speed that determines whether we call something "memory" or "storage." A cache holds things the same way an HDD does — it is just orders of magnitude faster.
As a fun aside, you can technically "download more RAM" by updating your system software to mark what would typically be storage hardware as memory. You can run programs off an HDD! The fundamental process is identical to RAM — it is just significantly slower. This is exactly what swap files and swap partitions do on modern operating systems.
Recall from LN14 that we desperately need non-contiguous allocation to fix fragmentation, but programmers refuse to restructure their code to accommodate it. Virtual memory solves this impasse: we perform non-contiguous allocation in the physical address space while maintaining the illusion of contiguous addressing in the logical address space.
To implement this, we need non-contiguous allocation techniques. We covered two contiguous techniques last time:
What if we could leverage the fundamental principles of these two techniques to build something new? Our first non-contiguous technique is best described as "virtual fixed partitioning." Its name is paging.
💡 Key Insight: Paging takes the simplicity of fixed partitioning and removes its fatal flaw — the requirement for contiguity. Pages are fixed-size (like fixed partitions) but can be placed anywhere in physical memory (unlike fixed partitions).
Usually, a system has more virtual pages than physical frames. This is by design: programmers get as much logical space as they want (the "universal memory" illusion), while the physical hardware has a finite number of frames. The MMU handles the mapping so the programmer never notices the mismatch.
Before using the paging demo, watch what changes and what stays fixed: physical frame placement changes, but each page keeps its logical identity.
Logical pages (blue) are mapped to physical frames (green). Notice there are more pages than frames — that is the whole point of virtual memory.
Therefore, paging solves the placement problem by making contiguity a property of the virtual address space, not of the underlying physical memory.
Notice the familiar tradeoff from fixed partitioning: as you adjust the page/frame size, smaller pages match process sizes better (less internal fragmentation in the last page) but require more pages to track. Larger pages waste more space in the final page but require fewer tracking entries.
The critical difference from fixed partitioning is that pages do not need to be physically contiguous. A process's pages can be scattered across physical frames in RAM, and some pages may be absent and backed by secondary storage until needed. The program still behaves as though it has one contiguous virtual space.
If we are dividing a process into pages and only loading some of them into physical frames, what happens when the CPU requests code or data that lives on an unloaded page?
Recall something critical: the assembly running on the CPU operates in logical address space. It does not know about pages, frames, or physical addresses. It just asks for "line 13" and expects to get data back.
When the MMU receives a logical address and discovers that the corresponding page is not loaded into any frame, the jig is up. The MMU declares a page fault.
💡 Connection to LN10-LN11: Notice that page faults create a scheduling problem that is structurally identical to CPU scheduling — multiple contenders competing for a limited resource, with the OS deciding who stays and who gets swapped out. The algorithms even share names: LRU, FIFO, and Working Set all appear in both domains.
As a side note, notice that this situation directly models the same management problem the CPU faces with scheduling. With CPU scheduling, multiple processes compete for a limited number of cores. With page management, multiple pages compete for a limited number of frames. There is an entirely adjacent scheduling problem dedicated to deciding which pages to evict — a direct parallel to CPU scheduling! Do not worry though; we have seen enough scheduling for one OS course.
This system only works because the hardware and OS cooperate to maintain the fiction of one coherent virtual address space. Let us take a deep dive into the exact steps involved.
Before stepping through the MMU translation, compare the fast path and the fault path: what is identical, and where does the expensive detour begin?
Watch how the MMU translates logical addresses for the CPU, and what happens when a page fault occurs.
Running code... Need data at line 13
Idle
... [1447]: "cat" ...
Storage
Step through both scenarios above. In the normal path, the MMU receives a logical address, translates it to a physical address using its page table, fetches the data from RAM, and returns it to the CPU. The CPU never knows the translation happened.
💡 Connection to LN8: The MMU we placed on our CPU diagram is doing all the heavy lifting here. In the fast path, the entire translation is invisible to software — pure hardware. Only in the fault path does the OS kernel get involved, making this a perfect division of labor between hardware (speed) and software (flexibility).
In the page fault path, the requested page is not resident. Extra steps are required: the kernel handles the fault, may need to evict some other page, reads the needed page into memory, updates the mapping, and then retries the access. The important operational detail is that the fault involves the OS and scheduler aswell as the hardware.
The MMU has dedicated hardware support for converting logical addresses to physical addresses. When paging is implemented, it consults a page table whose contents are set up by the operating system.
The architecture of the page table rests on the bits of the virtual address. Recall that the MMU is hardware — it can only see and solve problems one instruction at a time. We as OS designers think in 64-bit instruction chunks, but the hardware reasons about individual bits within those chunks. This is exactly what we are about to see.
The idea: split each logical address into two parts:
The MMU takes the page number bits, looks up the corresponding frame number in the page table, replaces the page bits with the frame bits, and keeps the offset unchanged. The result is a complete physical address.
Before you adjust the slider, predict which tradeoff will move: more page-number bits means what happens to page size and table size?
See how a 16-bit logical address is split into page number and offset bits, looked up in the page table, and translated to a physical address.
Adjust the slider to change how many bits are dedicated to the page number. Watch how this affects the number of possible pages and the size of each page:
This is the same tradeoff we saw with fixed partition sizes — but now it operates at the bit level of the instruction architecture itself.
Try the Page Fault Demo to see what happens when the page number has no corresponding valid entry. Therefore, the page table is not just a lookup map; it is also the hardware-visible record of whether a page is resident and accessible.
Let us make all of this concrete by working through a complete example on an imaginary 8-bit computer. On a real 64-bit machine the numbers are enormous, but the mechanics are identical — an 8-bit system keeps everything small enough to trace by hand.
An 8-bit instruction can reference 28 = 256 different addresses. That is the entire logical address space of this system — 256 lines, numbered 0 to 255. Every logical address the CPU can express fits in those 8 bits.
Now we must decide how many of those 8 bits to sacrifice for the page identifier. Each bit we sacrifice doubles the number of pages while halving the number of lines in each page. Watch how the binary structure of the instruction literally carves the LAS into pages:
An 8-bit system can reference 28 = 256 logical addresses — its entire logical address space. Watch how sacrificing upper bits to create a page identifier progressively divides this space.
The pattern is mechanical: the page bits count pages, the offset bits size them. No matter how we split, all 256 addresses are accounted for — we are just choosing the granularity of our pages.
Now we cross into the physical side. Let us commit to the 3-bit page scenario (8 pages of 32 lines each) and ask: how much physical memory do we need?
Each frame must be exactly 32 bytes — the same size as a page. If our physical memory is smaller than 32 bytes, we cannot even fit a single frame. If it is exactly 32 bytes, we get one frame. If it is 64 bytes, we get two. We will go with 64 bytes and see what the page table looks like.
With only 2 frames available for 8 pages, the page table has 8 rows but only 2 of them map to a frame. The other 6 are page faults — those pages live in storage until they are needed. When a translation succeeds, the 3 page bits are stripped off and replaced with however many frame bits we need (just 1 bit for 2 frames). The 5 offset bits pass through completely unchanged.
Starting from the 3-bit page scenario (8 pages, 32 lines each), we choose a physical memory size, build the page table, and translate a logical address end-to-end.
📚 Historical Note: The concept of paging was first implemented in the Atlas computer at the University of Manchester in 1961. Atlas had a one-level store that automatically moved data between a small magnetic core memory and a large drum — the first hardware-managed virtual memory system. Every modern laptop is a descendant of that idea.
This is the entire mechanism. The logical address space (256 addresses, 8 bits) is four times larger than the physical address space (64 addresses, 6 bits). The page table bridges that gap, and the offset bits that index within a page are the same bits that index within a frame — because pages and frames are the same size. That is why the offset is preserved: it does not need to be translated at all.
Key Takeaways: