Memory Without Abstraction

Picture one of the earliest computers, or a small microcontroller you might program today. It has some amount of RAM — say a few kilobytes — and those bytes are numbered, one after another, from 0 up to the last one. That numbering is not a convenience the OS invented; it is physical. Address 1000 is a specific set of wires that select a specific cell in a specific chip. When the CPU puts the number 1000 on the address bus, that exact cell responds. There is no layer in between.

In this world a program is loaded straight into those physical cells, and the addresses written into its instructions are physical addresses. If the program says "load the value at location 1000 into a register", it will read physical cell 1000 — the real one, on the real chip. The program does not have its own private view of memory that the hardware maps somewhere else. What it names is what it touches. In a very literal sense, the program IS the memory: the bytes of RAM and the bytes of the program are the same bytes.

Usually there is a sliver of the OS in there too — a handful of routines to read the keyboard, drive the screen, load the next program from tape or disk. In early machines this often lived in ROM at the very bottom or very top of the address range. But the model is otherwise as simple as it gets: one program, all the RAM, addresses that mean what they say.

Physical address

A real location in RAM, selected directly on the address bus; the byte the hardware actually reads or writes.

Physical address space

The full range of physical addresses a machine has, from 0 to the size of installed RAM minus one.

No abstraction

The program sees and names physical addresses directly — there is no translation between what the code says and what the hardware touches.

If you have ever written firmware for a microcontroller — an Arduino, a small embedded chip — you have programmed exactly this model. There is no OS deciding where your variables live; your code and the hardware registers share one flat physical space, and a wild pointer can scribble directly onto a device control register. That is not a historical curiosity. It is the baseline that everything richer is built on top of.

The moment you take this simple model seriously, three problems fall out of it — and they are not minor. They are the reasons the model could not survive contact with real, multi-program computing. Every abstraction we build in the coming chapters exists to solve one or more of these.

The first is protection, or rather the total absence of it. If a program names physical addresses directly, then nothing stops it from naming the wrong ones. A buggy loop that walks past the end of an array will happily write into the OS routines sitting at the bottom of memory, or into whatever else is there. There is no hardware asking "are you allowed to touch this?" — the address goes on the bus and the write happens. A single stray pointer can corrupt the operating system and take the whole machine down. The program is not malicious; it is just wrong, and the hardware has no way to contain the damage.

The second is relocation. When a compiler turns your program into machine code, it has to bake in actual addresses: "jump to the instruction at 100", "load the variable at 1000". But those numbers are only correct if the program is loaded at the exact spot the compiler assumed. If the program was built expecting to start at address 0 but is actually placed at address 16384 because something else already occupies the bottom of RAM, then "jump to 100" jumps to the wrong place entirely. The addresses in the code no longer match where the code physically lives.

The third problem is really a consequence of the first two: running more than one program at a time becomes almost impossible to do safely. You could load program A low and program B high, but B was probably compiled expecting to live at address 0 (relocation), and even if you fix that, nothing stops A from scribbling over B (protection). Two programs sharing one flat physical space, each convinced it owns addresses starting at zero, is a recipe for constant collision.

Protection

Preventing one program from reading or writing memory that belongs to the OS or to another program. Absent entirely in the raw model.

Relocation

Making a program run correctly regardless of where in physical memory it is loaded, even though its addresses were fixed at compile time.

Multiprogramming

Keeping several programs in memory at once so the CPU always has something to run. The goal that raw physical addressing cannot safely support.

The first real attempt to run several programs at once was blunt but effective: carve physical memory into a handful of fixed regions, called partitions, and let one program live in each. The OS keeps its own region — traditionally at the bottom — and the rest of RAM is pre-divided, often at boot time, into partitions of chosen sizes. A job that needs memory is placed into a partition big enough to hold it, and now the machine can hold several jobs at once, ready for the CPU to switch between them.

This is a genuine step forward: it makes multiprogramming possible at all. IBM mainframes of the 1960s ran exactly this scheme (the system was even called MFT — Multiprogramming with a Fixed number of Tasks). While one job waited for slow tape or disk I/O, the CPU could turn to another job sitting in a different partition, instead of sitting idle. Keeping the expensive CPU busy was the whole point.

But fixed partitions do not actually solve our two hard problems — they only make room for them. Relocation comes roaring back: a job compiled to expect addresses starting at 0 might be loaded into partition 3, which physically begins at, say, 8 MB. Every address in that job is now off by 8 MB. Early systems patched this at load time with software relocation — the loader would walk through the program and add the partition’s start address to every internal address it found. That works, but it is slow, it must happen on every load, and once a program is relocated in place you cannot easily move it again.

And protection is still wide open. Nothing about drawing lines between partitions stops the job in partition 2 from computing an address that lands in partition 1 and writing there. The partitions are a bookkeeping convention, not a fence the hardware enforces. To make partitions safe we need the hardware itself to check every address a program produces — and that is exactly the idea the next section introduces.

Fixed partition

A pre-sized region of physical memory set aside to hold one program; the number and sizes are fixed in advance.

Job queue

The line of programs waiting to be placed into a suitable partition, sometimes one queue per partition size.

Static (load-time) relocation

Fixing up a program’s baked-in addresses once, as it is loaded, by adding its partition’s start address. Simple but slow and one-shot.

Here is the elegant fix, and it is worth slowing down for, because it is the seed from which all of virtual memory grows. Add two registers to the CPU: a base register and a limit register. When the OS gives a program the CPU, it loads the base register with the physical address where that program’s memory begins, and the limit register with how long that region is. From then on the hardware does something quietly transformative on every single memory access.

The program still generates addresses as if it starts at zero — it does not know or care where it really lives. But before any such address reaches the memory bus, the hardware adds the base register to it. An address the program calls 100 becomes, physically, base + 100. This is address translation: the program works in its own coordinate system starting at 0, and the hardware transparently shifts every address into the program’s actual physical region. Relocation is now solved in hardware, automatically, on every access — no load-time patching, and the OS can even move the program and just reload the base register.

The limit register handles protection in the same breath. Before adding the base, the hardware checks that the address the program generated is less than the limit. If the program tries to reach past the end of its own region — a runaway pointer, an array overrun — the address exceeds the limit, the check fails, and the hardware traps to the OS instead of performing the access. The program is stopped; the OS and every other program are untouched. That trap is the direct ancestor of the "segmentation fault" you have surely seen.

• ▸The program generates a logical address, as if its memory started at 0.
• ▸The hardware compares it against the limit register; if it is too large, trap to the OS — the access never happens.
• ▸Otherwise the hardware adds the base register, producing the true physical address.
• ▸The physical address goes to RAM, landing safely inside the program’s own region.
• ▸On a context switch, the OS simply loads a new base and limit for the next program — instant, safe relocation.

Base register

Holds the physical start of the running program’s memory; added to every address the program generates.

Limit register

Holds the size of that region; every address is checked against it before use, giving hardware-enforced protection.

Address translation

Converting a program-relative (logical) address into a physical one on the fly. Here it is a single addition — later it becomes page tables.

Dynamic relocation

Relocating at run time via the base register rather than patching the program once at load, so the program can even be moved and simply re-based.

Base and limit registers let several programs coexist safely, but they do not create more RAM. What happens when the programs you want to run — all their memory added up — simply do not fit in physical memory at once? Early systems answered with swapping: keep some processes in RAM and park the rest on disk, shuttling whole processes back and forth as needed.

The mechanics are straightforward. When memory is full and a process needs to run that is not resident, the OS picks a victim process already in RAM, copies its entire memory image out to a reserved area on disk called the backing store — this is swapping it out — and frees that RAM. Then it copies the desired process in from disk — swapping it in — into the freed space, reloads its base and limit registers to point at the new location, and lets it run. Note how base/limit pays off again here: because relocation is dynamic, a swapped-in process can come back to a completely different physical spot and still work, so long as the OS updates its base register.

The catch is cost, and it is enormous. Disk is not a little slower than RAM; it is thousands to millions of times slower. Swapping an entire multi-megabyte process out and another one in means moving all of that data across that vast speed gap, twice. Do it occasionally and it is a reasonable way to overcommit memory. Do it constantly, because too many active processes are fighting over too little RAM, and the machine spends nearly all its time moving memory to and from disk and almost none actually computing. That pathological state has a name we will meet properly later: thrashing.

There is also something clumsy about swapping whole processes. A process might be 8 MB but only actively using a few kilobytes of it right now — yet swapping moves the entire image, all-or-nothing. That waste is a strong hint that a finer-grained approach is possible: what if we could move just the pieces of a process that are actually needed, instead of the whole thing? That question is the doorway to demand paging, and it is where Part D is heading.

Swapping

Moving an entire process between RAM and disk so that more processes can share limited physical memory over time.

Backing store

A dedicated region of fast disk (a swap area or swap file) that holds swapped-out process images.

Swap out / swap in

Copying a process’s memory image to disk to free RAM, and later copying it back so it can run again.

Thrashing (preview)

When the system spends most of its time swapping instead of computing because active memory demand far exceeds RAM.

As processes come and go — some ending, some swapped out, new ones loaded — physical memory starts to look like a street where cars keep leaving and arriving. Over time you get a patchwork of used regions with gaps of free memory scattered between them. Those gaps cause two distinct kinds of waste, and it is worth keeping them separate in your head because the distinction comes up again and again in real systems.

External fragmentation is free memory that is broken into pieces too small to use. Imagine three separate 20 KB holes scattered across RAM. You have 60 KB free in total — plenty on paper — but a new 50 KB process cannot be loaded, because there is no single contiguous 50 KB gap anywhere. The free space exists; it is just in the wrong shape. The memory is fragmented "externally", in the gaps between allocations.

Internal fragmentation is the opposite: waste inside an allocation. Recall fixed partitions — if you place a 6 MB job into an 8 MB partition, the leftover 2 MB inside that partition is unusable by anyone else, because the whole partition belongs to that one job. The waste is sealed "internally", inside a block that is bigger than what was actually needed. Any scheme that hands out memory in fixed-size chunks pays some internal fragmentation, because requests rarely land exactly on a chunk boundary.

The classic cure for external fragmentation is compaction: periodically slide all the in-use regions together toward one end of memory, sweeping the scattered holes into one big contiguous free block at the other end. It works — but it is brutally expensive. The OS must physically copy potentially every byte of in-use memory to a new location, and it must pause the affected programs while it does, updating each one’s base register to its new home afterward. On a busy machine you cannot afford to keep stopping the world to shuffle memory around.

External fragmentation

Total free memory is enough, but it is split into scattered holes, none individually large enough for the request.

Internal fragmentation

Memory wasted inside an allocation because the block handed out is larger than what was actually needed.

Compaction

Relocating in-use regions to merge scattered free holes into one large contiguous block; correct but very costly.

Placement policy

The rule for choosing which hole to use — first-fit, best-fit, worst-fit — each trading speed against how badly it fragments memory.

Step back and tally what we have. Base and limit registers gave us real protection and painless relocation — a huge win, and the conceptual heart of everything to come. Swapping let us overcommit memory. But the scorecard still has glaring failures. Memory fragments, and the only cure, compaction, is too expensive to run often. Swapping is all-or-nothing, moving whole processes when only a fraction is in use. And a single base-and-limit region forces each program’s entire memory to be one contiguous block in physical RAM, which is precisely what makes fragmentation so painful in the first place.

Every one of these failures traces back to the same root assumption: that a program’s logical addresses map, contiguously and directly, onto a single stretch of physical memory. Loosen that assumption — let a program’s address space be chopped into pieces, and let those pieces live anywhere in physical memory, or even out on disk — and the problems dissolve one after another. That single idea is the pivot the whole field turned on.

So here is the road ahead for Part D. First we make the address space a first-class idea: every process gets its own private range of addresses starting at zero, fully decoupled from where its data physically sits. Then segmentation lets that space be split into logical pieces — code, stack, heap — each separately placed and protected. Then paging, the workhorse of every modern OS, chops both the virtual and physical spaces into small fixed-size pages and maps them through page tables, defeating external fragmentation and enabling us to keep only the needed pages in RAM. That last move — demand paging — is the refined, page-level descendant of the swapping we just met, and it is what lets an 8 GB machine comfortably run programs that together ask for far more.

And this is where the payoff lands for you as a working engineer. Every process you run today gets its own virtual address space — its own clean, private, zero-based view of memory — for exactly the reasons this chapter laid bare. It is why your program cannot read the memory of the process beside it (protection, generalised). It is why the same pointer value in two processes refers to different physical bytes (relocation, generalised). It is why your 200 MB service runs fine on a box with far less free RAM (swapping and paging, refined). The tidy abstraction you have taken for granted since your very first program is the hard-won answer to the very problems you just watched break the naive model.

Address space

The private, contiguous-looking range of addresses a process sees, decoupled from physical memory. The central abstraction of Part D.

Segmentation

Splitting an address space into logical segments (code, data, stack), each placed and protected independently.

Paging

Dividing memory into small fixed-size pages mapped through page tables, defeating external fragmentation and enabling partial residency.

Demand paging

Loading only the pages a process actually touches, bringing others from disk on demand — the refined heir of swapping.