We finished the previous lesson with a very concrete question: if ingestor and the aggregator both have code at address 0x400000, how is it possible that they do not tread on each other? The answer to that question is the operating system's second great job, and it goes deeper than it looks: it involves the compiler, the linker, the loader and a specific circuit inside the CPU.

In this lesson you are going to understand how several processes share a limited physical memory without invading each other, what the difference is between a logical address and a physical one, and why the solution evolved from a simple pair of registers to modern schemes. You will also see the two kinds of fragmentation with concrete calculations, and you will finish by reading the real memory map of a Meteora process, region by region. It is the lesson that lays the ground for the next one, which is the one that really explains how a modern system works.

1. The problem: shared memory without invasions
2. Logical addresses and physical addresses
3. The three address binding phases
4. Relocation with base and limit registers
5. The MMU: the translator on the critical path
6. Contiguous allocation: fixed and variable partitions
7. Allocation strategies: first, best and worst fit
8. Internal and external fragmentation, with numbers
9. Compaction and why it is almost never used
10. Segmentation
11. Classic swapping
12. The idea of paging
13. The real memory map of a Meteora process

meteo-01 has 8 GB of RAM and runs around 180 processes. The operating system has to solve five problems at once that pull in different directions:

Notice a detail that conditions everything else: protection must be checked on every memory access. Not once when the process starts, but on every mov the CPU executes, billions of times per second. That rules out any software-based solution outright: if the operating system had to validate every access, a program would run a thousand times slower.

As we already saw in 01-06 with privileged instructions, the only possible solution is for the hardware to do it. And that hardware is the MMU.

When you compile ingestor and look at where its main function is:

The CPU will execute instructions that refer to address 0x401b40. But that is not the real position in the RAM chips. It is a logical address (or virtual address): a number that only makes sense inside that process's address space.

This explains the paradox we started with: ingestor and the aggregator can both have code at 0x401b40 because each one lives in its own address space. The MMU translates that same logical address into different physical frames depending on which process is running.

You can verify it:

Both processes have their code starting at exactly 0x401000. Neither of them knows — nor needs to know — where it really is in RAM.

Translating "the variable total" into "physical byte number 3,221,225,472" can be settled at three different moments, and the choice has very different consequences:

Compile-time binding. The compiler generates absolute addresses: "load what is at position 2000". If the program is not loaded exactly where it was expected, it does not work. It is what the microcontrollers in Meteora's weather stations still do today: the firmware knows that memory starts at 0x20000000 because it is a specific board and that will never change.

Load-time binding. The compiler generates relocatable code with addresses relative to the start of the program. The loader adds the real base address. It is more flexible, but once loaded the process cannot move, because its addresses have already been rewritten.

Execution-time binding. The code keeps logical addresses and the translation happens on every access, in hardware. This makes it possible to move a process in RAM while it is running, and it is the basis of everything modern: virtual memory, copy-on-write, shared libraries and ASLR.

In fact, ASLR (Address Space Layout Randomization) is only possible with execution-time binding. See for yourself:

Two runs of the same cat with the stack at completely different addresses. The system randomizes the layout on every start so that an attacker cannot predict where anything will be. We will come back to this in module 5.

The simplest hardware scheme that solves relocation and protection at the same time uses two registers:

• Base register (or relocation register): the physical address where the process starts.
• Limit register: the size of the process's address space.

On every memory access, the hardware performs two operations:

A numerical example with ingestor:

Here is the complete mechanism of memory protection, in two lines of logic. And notice the crucial detail that connects with 01-06: the base and limit registers can only be modified with privileged instructions. If a process could change its own limit register, the protection would be worthless. That is why the kernel loads them on every context switch and the process cannot touch them.

This scheme is elegant and blazingly fast (one comparison and one addition, a handful of cycles), but it has three fatal limitations:

1. The whole process must be in RAM and in one contiguous block. If it needs 8 MB, an 8 MB contiguous gap is required.
2. It does not allow differentiated permissions. The whole space gets the same treatment: you cannot mark the code as non-writable.
3. It does not allow sharing. Two processes running the same binary need two complete copies.

The MMU (Memory Management Unit) is the circuit that performs that translation. On modern processors it is integrated into the CPU core itself, alongside the caches, and it is not an implementation detail: it is one of the most performance-critical pieces of the system.

Three characteristics of the MMU that are worth fixing right away:

• It acts on every access. Every mov, every instruction fetched, every push onto the stack. If the translation cost 10 ns, the system would be unusable. That is why MMUs incorporate a translation cache (the TLB) that we will see in the next lesson.
• It is hardware and cannot be bypassed. A program in user mode has no way whatsoever of accessing a physical address directly. None.
• The operating system configures it. The kernel decides which translations are valid; the MMU enforces them. It is the same division of roles we saw in 01-06: the software sets the policy, the hardware imposes the mechanism.

With base and limit, each process occupies a contiguous block. How is memory divided among them?

Memory is divided into a fixed number of partitions of predetermined size when the system boots.

Simple to implement (a four-entry table is enough), but rigid:

• If meteo-api needs 300 MB and you give it partition 1 of 1 GB, 700 MB are wasted inside the partition. Nobody else can use them.
• If the aggregator needs 4 GB, it fits in none of them, even though the free gaps add up to more than enough.
• The degree of multiprogramming is limited to the number of partitions: four processes at most.

It is the scheme of the IBM OS/MFT of the 1960s, which we saw when discussing multiprogramming in 01-02.

The system keeps a list of free gaps and gives each process exactly what it asks for. When it finishes, its space goes back to the list and is merged with the adjacent gaps.

Let us simulate a real sequence in a memory of 2,560 MB with the kernel occupying 400 MB:

The final situation: there are 1,360 MB free in total, but split across three gaps of 600, 500 and 260 MB. If a process now arrives that needs 900 MB, it does not fit, even though there is plenty. That is the problem we will get to in the section on fragmentation.

When there are several gaps a process would fit in, you have to choose. Three classic strategies:

Let us compare them on the same case. Free gaps, in this order:

Successive requests: P1 = 212 MB, P2 = 417 MB, P3 = 112 MB, P4 = 426 MB.

First fit:

Best fit:

All four requests are satisfied.

Worst fit:

Summary:

Be careful about generalizing from a single case. Best fit wins here, but the classic simulation studies conclude that:

• First fit and best fit are equivalent in space utilization, and first fit is noticeably faster because it does not walk the whole list.
• Worst fit is worse than both in almost every scenario: it systematically destroys the large gaps, which are the most valuable ones.
• Best fit has a cumulative flaw: it leaves tiny leftovers (83 MB, 88 MB) that will never be useful for anything, and the gap list grows indefinitely. It is fragmentation dressed up as efficiency.

That is why the practical consensus is first fit, or its next fit variant (start searching where the previous search ended, instead of always from the beginning), which spreads the wear more evenly.

Fragmentation is memory that exists physically but cannot be used. There are two kinds, and confusing them is one of the most frequent mistakes:

Calculating internal fragmentation. Suppose fixed partitions of 512 MB:

Almost half the allocated memory is good for nothing. And it is an invisible waste: the system reports 2,048 MB in use and that is technically true.

Calculating external fragmentation. Let us go back to the final state of the variable-partition simulation:

The 50% rule quantifies how bad this gets: in a system with variable partitions and first fit, for every N allocated blocks there are statistically 0.5·N free blocks lost to fragmentation, which means that up to a third of memory can end up unusable.

An important nuance for later: paging completely eliminates external fragmentation (because all blocks are the same size, so any gap works for any page) but introduces bounded internal fragmentation. With 4 KB pages:

Trading a third of memory for 0.09% is an excellent deal, and it is the underlying reason why every modern system pages.

The obvious solution to external fragmentation: move the processes to bring all the gaps together into one.

Now the 900 MB process does fit. Compaction is only possible with execution-time binding: if the addresses had been fixed at load time, moving a process would break it. With base and limit it is enough to copy the bytes and update the base register.

So why is it not used? Because of the cost:

And this would have to be repeated every time fragmentation built up again, which on a system with processes coming and going is constantly. On a server with 64 GB, compacting could cost seconds.

Conclusion: compaction works, but the cure is worse than the disease. The real solution was to change the premise: if the problem is requiring a process to occupy a contiguous block, let us drop that requirement. That is paging.

Before we get to paging there was an intermediate attempt with a different motivation: making memory reflect how the programmer sees the program.

A program is not a uniform block of bytes. It is a set of logical pieces: the code, the global data, the stack, the heap, each library. Segmentation gives each one its own space, with its own size and its own permissions.

A segmented address has two parts:

And the translation uses a per-process segment table, with one base and one limit per segment:

Translating <2, 0x1000> (segment 2, offset 4096):

Translating <1, 0x3000> (offset 12,288 in the 8 KB data segment):

The advantages of segmentation over plain base and limit are real:

• Per-segment protection. The code segment is r-x: an attempt to write to it fails. This is exactly what stops a buffer overflow from overwriting instructions.
• Natural sharing. Segment 4 (libc) can point to the same physical base in 180 processes. A single copy of the library in RAM.
• Independent growth. The heap can grow without having to move the stack.
• It matches the structure of the program, which makes life easier for the linker and the debugger.

But it keeps the original sin: each segment is still contiguous in physical memory, so external fragmentation persists. It is only reduced, because segments are smaller than an entire process.

On x86-64 segmentation exists but is essentially disabled: the code and data segments span the whole address space (the flat model), and only the FS and GS registers survive, used for thread-local storage and for per-CPU data in the kernel. History chose paging.

The last piece of the classic scheme: what to do if the active processes do not all fit in RAM?

Swapping consists of moving an entire process out to disk and bringing it back when its turn to run comes around. It is the job of the medium-term scheduler we mentioned in 02-02.

The cost is brutal. With a mechanical disk at 100 MB/s:

Twenty seconds during which the aggregator does not exist. With an NVMe SSD at 3,000 MB/s it would drop to 0.67 seconds, better but still wildly out of proportion compared with the microseconds of a context switch.

That is why swapping entire processes is practically dead. What modern systems do is swap individual 4 KB pages, not whole processes: if the aggregator has 1 GB but is only actively using 30 MB, the inactive pages are evicted and the rest stays. That is already virtual memory, and it is the central topic of the next lesson.

Even so, classic swapping is still alive in one specific case: hibernation. When you suspend a laptop to disk, the system writes all of RAM to the swap area. It is exactly the same mechanism, applied to the whole machine.

Let us recap the central problem. External fragmentation exists because we require a process's space to be contiguous in physical memory. Compaction tries to fix the symptom. Paging attacks the cause:

What if a process did not have to be contiguous in physical memory?

The idea, in three steps:

1. Divide physical memory into equal, small chunks called frames, typically 4 KB.
2. Divide each process's logical space into chunks of the same size called pages.
3. Place each page in any free frame, regardless of order. A per-process page table records which page is in which frame.

The consequences are enormous:

That last point is the one that has to be solved well, and it is not trivial: if every memory access requires consulting the page table, which is also in memory, every access would cost twice as much. The solution is the TLB, and the whole mechanism — multilevel tables, status bits, page faults, replacement algorithms — is what we will develop in detail in Virtual Memory and Paging.

For now, keep the central idea: paging works because it makes block sizes uniform. When all the pieces are the same, the problem of fitting them together disappears.

Everything above stops being theory as soon as you read /proc/<pid>/maps. Let us look at ingestor's:

The format of each line, field by field:

• Range: starting and ending logical addresses (end not included).
• Permissions: r read, w write, x execute, and p private (copy-on-write) or s shared.
• Offset: at what point in the file this mapping starts.
• Device and inode: which file has been mapped (00:00 and 0 if it is not a file).

Now the interpretation region by region, which is where all the learning is:

Five observations that deserve attention:

1. No region is both writable and executable. That strict separation is called W^X (write xor execute) and it is a fundamental defense: even if an attacker manages to inject code into the heap or the stack, they will not be able to execute it because those regions do not have the x bit. It is a direct application of the per-region protection we saw in segmentation, implemented here on top of pages. It will come back in module 5.

2. The binary occupies four regions, not one. The ELF loader splits the sections according to their permissions, precisely because of the point above.

3. libc appears with the same four-region structure, and its r-xp parts are physically shared with the system's other 179 processes. A single copy of libc's code in RAM serves them all. Here is the sharing that segmentation promised, achieved with paging.

4. [vdso] is a brilliant trick. The kernel maps a small piece of its own code into every process's space so that very frequent calls like gettimeofday() or clock_gettime() are resolved without crossing into kernel mode. Remember the cost of a syscall we calculated in 01-06: between 50 and 500 ns. The vDSO reduces it to a few nanoseconds, and that is why it exists.

5. The stack is at 0x7ffd... and the code at 0x0040..., with a chasm between the two. That enormous gap costs nothing: they are logical addresses with no translation assigned, and they consume not a single byte of RAM. Reserving address space is free; only the physical memory actually backing it costs anything.

pmap presents the same thing with the sizes already worked out, which is more convenient day to day:

The three numeric columns say very different things, and confusing them leads to wrong diagnoses:

• Kbytes: reserved address space. It is the sum that gives you ps's VSZ.
• RSS: how much of that is actually in RAM. Look at libc.so.6: it reserves 1,568 KB of code but only 692 KB are loaded. The rest are libc functions this process has never called, and which therefore have never been fetched from disk.
• Dirty: modified pages, which cannot be discarded without being written somewhere first. Code is never dirty (it is never modified), so it can be evicted at no cost: if it is needed again, it is re-read from the binary.

That distinction between clean and dirty pages is what governs what gets evicted first when memory runs short, and it is one of the keys to the next lesson.

Confusing internal with external fragmentation. Mnemonic: internal is inside what you were given (there is spare room in your block); external is outside, between other people's blocks (there is room but not in a single piece). Fixed partitions and paging produce internal fragmentation; variable partitions and segmentation, external.

Believing that VSZ is the memory a process uses. It is not. A process can reserve 100 GB of address space on an 8 GB machine without a problem, because addresses are free. The real memory is RSS, and even then with caveats: libc's shared pages are counted in the RSS of every process that uses it, so adding up the RSS values gives a total far above the installed RAM.

Thinking that best fit is the best. The name misleads. It leaves useless crumbs and forces you to walk the entire gap list. First fit is just as good in utilization and considerably faster.

Assuming that segmentation and paging are mutually exclusive alternatives. Historically they were combined: 32-bit x86 did segmentation and paging (the address went through the segment table and the result through the page table). On x86-64 segmentation was reduced to a flat model, but it did not disappear entirely: FS and GS are still used.

Misreading a "segmentation fault". The message is historical and confusing: today it almost always means an access to an address with no valid translation in the page table, not to a segment out of bounds. To diagnose it, compare the failing address with the regions in /proc/<pid>/maps: if it falls in a gap, it is a corrupt pointer; if it falls in an r--p region and it was a write, it is an attempt to write to read-only memory (typically, modifying a string literal).

Practical tip: when a process "uses a lot of memory", the right order of investigation is pmap -x <pid> to see which region is growing. If [heap] grows, it is malloc without free. If separate [anon] regions grow, they are large blocks mapped with mmap. If [stack] grows, there is runaway recursion. Each case has a different cause and a different fix, and the map tells you without touching the code.

meteo-01 has the following free gaps, in this order in memory:

These requests arrive, in order: A = 230 MB, B = 140 MB, C = 310 MB, D = 190 MB.

1. Work out the allocation with first fit, best fit and worst fit.
2. For each strategy, state how many requests are satisfied and what the resulting external fragmentation is.
3. Which would have worked best? Can you conclude from this which is superior in general?

The four Meteora processes need: ingestor 180 MB, aggregator 490 MB, meteo-api 300 MB, backup 60 MB.

1. Calculate the total internal fragmentation with fixed 512 MB partitions.
2. Calculate the total internal fragmentation with 4 KB paging, assuming each process has 15 memory regions.
3. Compare the two results in absolute value and as a percentage.
4. Explain why paging does not produce external fragmentation.

This is the summarized map of meteo-api after 22 hours of running:

1. Which region dominates consumption and what does it probably represent?
2. The libssl.so.3 region reserves 1,024 KB but has only 12 KB in RAM. Is that a problem? Why does it happen?
3. The mode of /dev/shm/meteora-cache is rw-s-. What does the s mean and what does it imply?
4. If the system urgently needed to free memory, which pages of this process could it evict without writing anything to disk? Work out how many KB that is.
5. Given this data, would you say meteo-api has a memory leak? Justify what check you would run.

Solution 1

First fit (the first gap it fits in, scanning from H1):

4 of 4 satisfied. Final gaps: 10, 170, 10, 60, 180 = 430 MB free, largest block 180 MB.

Best fit (the smallest gap it fits in):

4 of 4 satisfied. Final gaps: 10, 210, 20, 10, 180 = 430 MB free, largest block 210 MB.

Worst fit (the largest gap):

3 of 4 satisfied. C goes unserved despite there being 930 MB free before the attempt.

Summary:

3. Analysis. First fit and best fit tie on requests served; best fit leaves the largest contiguous block slightly bigger (210 against 180), which gives it a marginal advantage for a future request.

Worst fit fails, and its failure is instructive: by handing the 400 MB gap to a 230 MB request, it destroyed the only gap that C (310 MB) would later have fitted in. That is the fundamental criticism of worst fit: it systematically consumes the scarcest resource, which is the large gaps.

Can we conclude which is superior in general? No. This exercise shows one specific sequence. Changing the order of the requests reverses the result: if C arrived first, worst fit would serve it without trouble. Valid conclusions come from simulations over thousands of random sequences, and those say that first fit and best fit are statistically equivalent in utilization, that first fit is faster — it does not walk the whole list — and that worst fit is systematically inferior. First fit wins on speed, not on utilization.

Solution 2

1. Fixed 512 MB partitions.

Almost half. And notice how uneven the distribution is: the aggregator (490 MB) wastes only 22 MB, while backup (60 MB) wastes 452 MB. Internal fragmentation with fixed partitions punishes small processes disproportionately, and they are the majority on any real system.

2. 4 KB paging with 15 regions per process.

The key to the calculation: within a region, every page is full except the last one, which on average is half full.

3. Comparison.

The difference is not one of degree, it is one of nature. And the reason is purely arithmetic: the waste from internal fragmentation is proportional to the size of the allocation block. With 512 MB blocks you waste up to 512 MB per process; with 4 KB blocks you waste at most 4 KB per region. Reducing the block by a factor of 131,072 reduces the waste in the same proportion.

This also explains why huge pages (2 MB) are not free: they improve the TLB but multiply internal fragmentation by 512. We will see it in the next lesson.

4. Why paging does not produce external fragmentation.

External fragmentation appears when there is enough free memory but not in a contiguous block of the required size. It needs two conditions at once:

1. That requests have different sizes.
2. That the allocation must be contiguous.

Paging eliminates both:

• All units are exactly the same size (4 KB), so any free frame works for any page. There is no such thing as "it does not fit": if there is a free frame, the page fits in it.
• Contiguity is not required: pages 0, 1, 2 and 3 of a process can be in frames 847, 12, 5,301 and 92. The page table takes care of making the process see a continuous space.

Put precisely: with paging, if there are N free frames, any request of up to N pages can be satisfied, no matter where those frames are. That guarantee is impossible with contiguous allocation, and it is the reason why the need to compact also disappears.

Solution 3

1. The dominant region.

118,784 KB = 116 MB, 88% of the process's total RSS (118,784 out of 135,140). It is anonymous memory — not backed by any file — writable, private, and with RSS = Kbytes = Dirty: it is entirely in RAM and entirely modified.

The fact that it starts at 0x1a40000, just above the binary, indicates that it is the heap expanded with brk (or a large malloc arena). Given its size and the fact that this is meteo-api, the most likely thing is a response cache or a set of readings loaded into memory to serve queries without touching /var/lib/meteora/readings/.

A useful contrast: 116 MB at 24 bytes per Reading is about 5.07 million readings, close to seven days of data at 800 readings per second.

2. The libssl.so.3 region with 12 KB out of 1,024 KB.

It is not a problem at all: it is exactly what should happen.

It happens because of demand paging: when a library is mapped, the kernel does not read its code from disk. It only creates the page table entries, marked as not present. A page is fetched from disk only when the process tries to execute it and a page fault occurs.

meteo-api has used 12 KB (three pages) of OpenSSL. Everything else — encryption algorithms it does not use, certificate management functions, compatibility code — has never been touched and therefore has never occupied RAM.

The aggregate saving is enormous: if 20 processes map libssl and each one uses a few different pages, the real consumption is a tiny fraction of the nominal 20 × 1,024 KB. And since the code is read-only, the pages that do get loaded are shared among them all.

3. The rw-s- mode.

The s means shared, as opposed to the p for private that all the others carry. The difference is fundamental:

Since it sits on /dev/shm/ (an in-RAM file system), this is memory shared between processes: probably the four meteo-api workers we saw in the pstree in 02-01 share a single 8 MB cache instead of having four copies.

An important implication: writing there from several processes at once requires synchronization. Without it, two workers updating the same entry would corrupt it. That is precisely the territory of module 3.

4. Pages that can be evicted without writing to disk.

They are the clean pages (Dirty = 0) backed by a file: if they are needed again, they are re-read from the original binary, so discarding them is free.

Only 692 KB out of 135 MB. And there is the uncomfortable lesson: 99.5% of this process's memory is anonymous and dirty, so freeing it requires writing it to the swap area, with the disk cost that entails. If meteo-01 had no swap configured, that memory would be simply unreclaimable and the system would have to resort to the OOM killer.

An extra note about the 512 KB in /dev/shm: since they live in tmpfs, they have no disk backing; they can only go to swap, never be discarded.

5. Is there a memory leak?

With this data you cannot say. A single snapshot does not distinguish a legitimate cache from a leak: both look the same, as a large, dirty, anonymous region.

The right check is to measure the evolution over time:

How to interpret the resulting series:

A calculation that gives you your bearings from the outset: 116 MB after 22 hours is about 5.3 MB/hour. If that rate were constant, in a week it would be 890 MB and in a month 3.8 GB, which on an 8 GB machine would end in the OOM killer. The fact that the answer depends on whether that rate holds or flattens out is exactly why you have to measure twice.

Complementary checks: repeated pmap -x to see which region is growing; sudo cat /proc/1901/status | grep VmPeak to find the historical maximum; and, in the code, to review whether the cache has an eviction policy or grows without limit, which is the most frequent cause of this profile.

Managing memory means solving relocation, protection, sharing, logical organization and capacity all at once, and under a very harsh constraint: protection must be checked on every access, which forces it to be solved in hardware.

The key piece is the separation between logical and physical addresses. Binding them at execution time — rather than at compile or load time — is what allows the MMU to translate on every access, allows a process to move, makes ASLR possible and lets two processes use the same address 0x401000 without treading on each other. The minimal scheme that achieves this is the base and limit registers: one comparison and one addition, complete protection, and impossible to bypass because they can only be loaded from kernel mode.

Contiguous allocation — fixed or variable partitions, with first, best or worst fit — works but runs into fragmentation: internal (up to 49.7% of the allocated space in our calculation with 512 MB partitions) or external (up to a third of memory, by the 50% rule). Compaction solves it, but it would cost 40 ms every time, so it is not a solution. Segmentation brought the best of contiguous allocation — per-region permissions and sharing — without curing external fragmentation, and swapping entire processes died as soon as the numbers were run: 20 seconds for a 1 GB aggregator.

The way out was not to improve contiguous allocation but to abandon the contiguity requirement. If all the pieces are the same size, fitting them together stops being a problem: that is paging. And all of this stops being theory when you read /proc/<pid>/maps and pmap -x, where you see shared, non-writable code, libc with only 44% of its code actually loaded, W^X protecting the stack and the heap, and the difference between Kbytes, RSS and Dirty that decides what can be evicted and what cannot.

The big part is still to come: how paging really works. How an address is translated with a page number and an offset, why a flat 64-bit table would be impossible and how multilevel tables fix it, what the TLB is and how much performance depends on it, what happens exactly when a page is not in RAM, which page to evict when there is no room left and why a system can enter thrashing and stop making progress. All of that, plus mmap() mapping 2026-08-31.dat into memory, is in Virtual Memory and Paging.