Standard: Memory
In this lecture we investigate memory allocation! We begin with studying contiguous memory allocation techniques like fixed and dynamic partitioning. We then use these techniques to investigate the problem of fragmentation and setup the foundation for virtual memory!
📅 March 16, 2026
Memory
In LN13, we surveyed the full landscape of memory hardware — from SRAM registers at picosecond speeds to tape drives measured in seconds. We established the mental model of memory as a series of finite strips ("rolls of toilet paper"), each a different length, with processes coloring parts of every roll simultaneously.
Today we face the critical question: how do we actually allocate processes onto those strips? We have fast memory that is tiny (registers, cache) and slow memory that is enormous (HDDs, tape). Running processes need to live in the fast memory — RAM — but that space is limited. We need to be smart about how we place processes into it, because every decision we make about placement has consequences for performance, waste, and system stability.
Our goal is to take the memory model from last time and allocate all data — whether being used by active processes or set aside for storage — across our strips. We need to be cognizant of what data needs to be close to the CPU and just how much to move there, since the space gets smaller and smaller the faster we need it.
Since only running processes need high-speed access, we will focus on getting processes placed into main memory (RAM). The question becomes: given a finite strip of RAM, how do we fit multiple processes onto it?
The simplest answer is also the most intuitive: give each process its own contiguous block.
This is how you would naturally place things on a shelf: each item gets its own stretch of space, packed next to the previous one. Simple, predictable, fast to access. But as we will see, it comes with significant tradeoffs. There are two major techniques for contiguous allocation.
The first technique is fixed partitioning. Think of it like bar seating at a restaurant — the stools are evenly spaced and bolted to the floor. You sit in however many stools your group needs, but you cannot move them.
In the simplified model for this lecture, memory is divided into equal-sized allocation units ahead of time. If a process needs 18 KB and each unit is 16 KB, it receives 2 units (32 KB total) even though it only uses 18 KB.
Before you touch the slider, predict which direction reduces waste inside an allocated block: larger units or smaller ones.
Drag the slider to change the partition size. Watch how internal fragmentation (wasted space within partitions) changes.
Therefore, fixed-size allocation trades tracking simplicity for internal waste: smaller units reduce waste, but require more bookkeeping.
Notice what happens as you adjust the partition size: if a process is not perfectly divisible by the partition size, there is overallocation. Those wasted bytes within the allocated partitions are called internal fragmentation.
By making the partition size smaller, we can match process sizes more closely, reducing internal fragmentation. But there is a catch: as the partition size decreases, we need more partitions, and we need a data structure to track whether each partition is in use. A partition size of 1 byte would theoretically eliminate all waste — but the tracking data structure would be as large as the memory itself! We would need as much memory to manage memory as we have to use.
So increasing partition size lets us sacrifice less overhead to management, but the larger we go, the worse the internal fragmentation gets. This is a fundamental tradeoff with no perfect answer in fixed partitioning.
💡 Connection to LN13: This tradeoff echoes the memory hierarchy itself — more capacity means less speed, more speed means less capacity. Fixed partitioning makes you choose where on that spectrum to sit, and there is no universally right answer.
But wait — if we can measure the internal fragmentation, it is because we already know the size of each process. Why do we not just allocate partitions that match the process size, rather than choosing a fixed size ahead of time?
This is the logic behind dynamic partitioning. Think of it like booth seating — people slide into the booth and take up only the space they need. No wasted room.
The idea is to separate memory into regions sized to each arriving process. When a process arrives, we carve out exactly as much memory as it needs. No overallocation, no internal fragmentation. Problem solved!
...or is it?
⚠️ Watch For This: The specific mismatch to track is that total free memory can be large enough while the largest contiguous gap is still too small.
Step through process arrivals and departures. Watch gaps form between processes, then try compaction.
Therefore, dynamic partitioning fixes the "waste inside the block" problem by making it easier to create the "waste between blocks" problem.
Step through the events above and watch what happens when processes terminate. Gaps of varying sizes form between the remaining processes. Eventually, a large process arrives and gets rejected — even though the total free memory across all gaps is more than enough! The problem is that no single contiguous gap is large enough.
This problem also appears in fixed partitioning (unallocated partitions scattered between used ones), so it is not unique to dynamic partitioning. But dynamic partitioning makes it especially visible because the gap sizes are irregular.
Taking inspiration from restaurants — what if we asked everyone to slide down to fill the gaps? We could alleviate fragmentation by simply reallocating everything to pack processes together.
Compaction works — but it becomes increasingly expensive as memory gets larger. Every byte of every process must be copied. As systems get more RAM and processes get larger, compaction takes more and more time. We need a better approach: can we prevent fragmentation through smarter allocation?
We know the fragmentation problem is caused by small processes being allocated next to or between larger ones, leaving awkward gaps when the small ones terminate. What if we were smarter about which gap we choose?
Let us categorize what we have been doing: First-Fit — allocate at the first gap that is large enough, scanning from the beginning of memory. Simple and fast. But there are alternatives:
| Strategy | Description |
|---|---|
| First-Fit (FF) | Allocate at the first gap found in a linear scan from the start |
| Best-Fit (BF) | Scan all gaps, pick the smallest one that fits — minimize leftover space |
| Worst-Fit (WF) | Scan all gaps, pick the largest one — maximize leftover space |
| Next-Fit (NF) | Like First-Fit, but start scanning from where you left off last time |
Try each strategy on the same sequence of events:
🤔 Think About This: As you step through the demo, do not just ask whether the allocation succeeds. Ask which gap each strategy chooses, and why.
Select a strategy, then step through the same sequence of arrivals and departures to compare behavior.
These algorithms have been studied extensively. Based on empirical and theoretical analysis, we can generally rank them by overall performance. It should be strongly noted however that with a better understanding our your workload, these algortihms may reorder:
Based on extensive empirical study, these four algorithms can be generally ranked by overall performance (speed + fragmentation management). Before revealing the answer, think about which one you would expect to win — and which would come last.
Which is fastest overall? Which is slowest? Can you guess?
Amazing results, right? The irony of the naming — "Best-Fit" is actually worse than "Worst-Fit"! But the real question is why. In many areas of programming, trying to proactively address issues earlier almost always leads to improvement. So how did the naive First-Fit take first place, and the technique that tried its hardest to prevent fragmentation end up being the slowest?
The answer comes from understanding process behavior.
Processes with smaller memory needs are generally faster — they need less space for computation and tend to terminate quickly. Larger processes with greater needs generally run longer. This asymmetry is what causes external fragmentation: small processes allocated next to large ones leave tiny gaps when they exit, while the large processes remain.
So why does not Best-Fit help? Because it actually creates more small gaps. By always picking the smallest fitting gap, every allocation leaves a tiny sliver of leftover space. After many cycles, memory is peppered with unusable 1-2 KB gaps. Compaction has to handle far more fragments, even though each is small.
Worst-Fit does better because placing small processes in the largest gap leaves large remaining gaps — which are more likely to be useful for future large processes.
Next-Fit is not great because it distributes gaps evenly across memory without any management strategy, leading to fragmentation everywhere.
📚 Historical Note: Donald Knuth analyzed these allocation strategies in The Art of Computer Programming (1973) and established the "Fifty-Percent Rule" — under First-Fit, roughly half of all allocated blocks are adjacent to a free block. This empirical finding has held up across decades of real workloads.
And First-Fit? It works best for the same reason Multi-Level Feedback Queues were revolutionary for scheduling: it naturally sorts by behavior! Small processes appear quickly and leave quickly. They form small gaps at the front of memory (since FF always starts scanning from the beginning). This pushes larger, slower processes toward the back. Over time, memory self-organizes into a hot zone at the front (many tiny fast-turnover processes) and a cold zone at the back (stable large processes). The small processes naturally fit in the small front gaps, leaving large gaps at the back for large processes.
Less management is better in this space. Some jobs actually require less supervision to succeed.
Before using the visual below, watch two things at once: where new allocations land and what shape of free space is left behind
Each tab shows what memory looks like after many allocation cycles with that strategy. Notice the gap patterns.
Small processes churn at the front, leaving the back for large, stable processes. The memory self-organizes into a hot zone (fast turnover) and a cold zone (slow turnover) — just like MLFQ naturally sorts by burst length!
Therefore, allocator quality is really about the long-term shape of free space, not just whether one individual allocation succeeds.
Both internal and external fragmentation are direct consequences of requiring everything to be contiguous. So what if we did what the scheduler does and split a process in half? Allocate the first half in one gap and the rest somewhere else?
Wait. Before we do such a thing, consider the ramifications. Machine code relies on ISA instructions being one after another in the process address space. All the jumps, all the program counter increments — they assume sequential layout. What would your programs look like if we just split them arbitrarily?
The programmer's response is a resounding NO. Programming is already hard enough without having to write code that anticipates being sliced to pieces. But we absolutely need non-contiguous allocation to fix fragmentation!
So we need both: non-contiguous allocation for the memory hardware, and the illusion of contiguous addresses for the programmer. Can we have our cake and eat it too?
To find out, we need to reconcile how programmers and hardware each use addresses.
Let us start from the programmer's perspective and work our way down, then come up from the hardware side, and see where the disconnect lies.
When we write programs, we use variable names, function names, and line numbers. The entire toolchain you are using, including the compiler, linker, and loader, translates these into machine code with addresses — numerical labels that identify where values live and where instructions jump to.
Before stepping through the mapping, watch what stays stable for the program: names and relative relationships inside the code.
Hover over lines to see the mapping. Toggle between two completely different programs and notice: they use the exact same addresses.
Therefore, from the program's point of view, addresses behave like local labels inside one address space.
Two critical observations:
RBP-8, both start execution at 0x0000.From the programmer's perspective, addresses are just names — convenient labels for the things in our program. We use them like names at a restaurant: "Table for x, party of y."
Now consider the machine code executing on the CPU. Recall that 64-bit ISA instructions literally map onto logic gates. An address in machine code physically selects a specific location in memory hardware. Only one piece of data can occupy a given physical address at any time. Addresses are not names — they are slots.
If we mapped every program's logical addresses directly to physical memory, every program would try to occupy the same physical slots — starting at 0x0000. Data corruption. Crashes. Chaos.
Both types of addresses are just numbers. We have a guarantee from programmers that all logical addresses are entirely contained within their process. We have a hardware guarantee that every physical address slot is unique and treated equally.
If mapping logical addresses directly to physical addresses results in collisions, why do we not simply offset each process's logical addresses until they land on an unused region of physical memory? The process slides into the available space while keeping all its internal address relationships intact.
📌 Key Point: Track one number carefully: every process begins at the same logical start, but ends up with a different physical start after translation.
Before stepping through this demo, track one invariant: the program's logical address stays the same even though the physical destination changes.
All of these processes start at logical address 0x0000. Watch what happens when we map them directly to physical memory, then apply base offsets to slide each one into its own physical region.
| Process | Logical Start | Base Offset | Physical Start | Physical End | Translation |
|---|---|---|---|---|---|
P1 (sum) | 0x0000 | — | 0x0000 | 0x0027 | 0x0000 + — = 0x0000 |
P2 (product) | 0x0000 | — | 0x0000 | 0x001D | 0x0000 + — = 0x0000 |
P1' (sum copy) | 0x0000 | — | 0x0000 | 0x0027 | 0x0000 + — = 0x0000 |
P3 (parser) | 0x0000 | — | 0x0000 | 0x0017 | 0x0000 + — = 0x0000 |
P4 (shell) | 0x0000 | — | 0x0000 | 0x0023 | 0x0000 + — = 0x0000 |
Therefore, translation lets the programmer keep one coherent address space while the OS chooses a different physical placement.
The formula is beautifully simple:
physical address = logical address + base
In real systems, this simple model is usually paired with a limit/bounds check so the process cannot wander outside its assigned region.
This works because the translation is systematic: one logical region maps to a shifted physical region. The mechanism is hardware-assisted, while the operating system is responsible for setting up the mapping correctly.
This hardware offset is computed by the MMU (Memory Management Unit) — a dedicated piece of hardware that sits between the CPU and memory. Every address the CPU produces is a logical address. The MMU intercepts it, adds the base offset for the current process, and sends the translated physical address to the memory bus.
💡 Connection to LN8: The MMU is hardware we already placed on our CPU diagram — it was sitting between the CPU and memory the whole time. Now we finally see its full job description: not just protecting memory boundaries, but actively translating every single address the CPU produces.
This is the same MMU we mentioned back in LN9 when discussing CPU security — it was already there, enforcing memory boundaries. Now we see its other critical role: address translation.
Next time, we will explore the MMU in depth and discover that the simple base-offset scheme we just derived is actually the foundation of something much more powerful: Virtual Memory. Instead of one base offset per process, what if we could translate every page of a process independently? That is where non-contiguous allocation finally becomes real — without the programmer noticing a thing.
Key Takeaways: