In the previous lesson we arrived at the idea of paging and left it hanging: if all the pieces are the same size, fitting them together stops being a problem. Now it is time to deliver on that promise. This is the densest lesson in the module and probably the most profitable one in the whole course, because virtual memory is the mechanism that explains an enormous number of things you will see in production: why a process reserves 400 MB and only uses 31, why the first request to meteo-api after a deployment is slow and the following ones are not, why a server that starts paging stops responding all at once, and why the OOM killer picks what it picks.

You are going to see address translation with concrete numbers, calculate the impossible size of a flat 64-bit table, measure how much performance depends on the TLB, follow a page fault step by step, work out the replacement algorithms over one and the same reference string, and map the file 2026-08-31.dat into memory with mmap(). By the end you will be able to read free -h, vmstat and the OOM killer's trail with proper judgement.

1. Pages and frames
2. Address translation, with a complete numerical example
3. The page table and its control bits
4. Why a flat table is impossible in 64 bits
5. Multilevel tables
6. The TLB and the effective access time
7. Huge pages
8. Demand paging and the page fault
9. Page replacement algorithms
10. Frame allocation, thrashing and the working set
11. Mapped files and shared memory with mmap()
12. Copy-on-write revisited
13. Swap, swappiness and the OOM killer
14. Measuring: VSZ versus RSS, /proc/meminfo, free -h, vmstat

These two terms are the foundation of the whole vocabulary and it is worth pinning them down with no ambiguity:

Check your system's page size:

And meteo-01's numbers:

There are thirty-four billion times more possible pages than available frames. That disproportion is exactly what makes virtual memory possible: the vast majority of pages will never exist, and the ones that do exist do not all have to be in RAM at the same time.

A logical address is split into two fields:

• The offset takes as many bits as are needed to address inside a page. With 4 KB pages = 2^12 bytes, that is 12 bits.
• The page number takes the rest.

The translation has three steps:

1. Extract p and d from the logical address.
2. Look up entry p in the page table, which holds the frame number f.
3. The physical address is f × page_size + d.

The offset is never translated. A page and a frame are the same size, so the position inside the page is identical to the position inside the frame. Only which block changes, not where inside the block.

Let us work with a small logical space so that everything fits on screen: 16-bit addresses and 4 KB pages.

The ingestor's page table:

Translate the logical address 0x2A5C.

Step 1, decompose it:

The arithmetic check, which is usually faster:

Step 2, consult the table: page 2 → frame 2, present.

Step 3, assemble the physical address:

It matched the logical address by pure coincidence (page 2 happens to be in frame 2). Let us try another one.

Translate 0x105C:

Notice a revealing detail: 0x105C → 0x905C. The three right-hand hexadecimal digits do not change (05C), because they are the offset. Only the left-hand digit changes: 1 → 9, from page to frame. In hexadecimal the translation is visually obvious whenever the page size is a power of 16.

Translate 0x3200:

Here no translation is possible. The MMU raises an exception and the kernel takes over. What it does then is section 8.

Each page table entry (PTE) takes 8 bytes on x86-64 and holds far more than a frame number:

The ones that really matter, and why:

Bit P (present). It is the master switch of all virtual memory. If it is 0, any access causes a page fault. The kernel uses it for three different situations, and tells them apart with the remaining bits of the entry, which are free when P=0: page never loaded, page evicted to swap, or simply invalid address.

Bits R/W and NX. This is where the per-region protection we saw in /proc/<pid>/maps is implemented. The r-xp code region has R/W=0 (not writable); the rw-p stack and heap regions have NX=1 (not executable). That pair of bits is the W^X policy.

Bits A and D. They are special because the hardware writes them, not the operating system. Every time the CPU accesses a page it sets A=1; every time it writes it sets D=1. The kernel reads them and clears them periodically. Without them it would be impossible to implement the replacement algorithms: the kernel has no way of observing every memory access, so it needs the hardware to leave it that clue.

Bit D (dirty). It determines the cost of evicting the page. If D=0, the page has not changed since it was loaded, so it can be discarded outright (if it is needed again it is re-read from the file). If D=1, it has to be written to swap before the frame can be reused. It is exactly the distinction of pmap's Dirty column that we saw in 02-03, and the cost difference is zero versus milliseconds.

Let us do the calculation that justifies all the complexity that follows.

On x86-64, 48 bits of virtual address are currently in use (the top 16 are a sign extension). With 4 KB pages:

512 GB of page table. Per process. On an 8 GB machine with 180 processes, you would need 92 TB just for the tables.

It is absurd, and it is absurd for a very concrete reason: a flat table reserves an entry for every possible page, including the ones that will never exist. Remember the ingestor's memory map: the code sits at 0x400000 and the stack at 0x7ffd8b3a1000. Between them lies a chasm of 140 TB of addresses that will never be used, and a flat table would need an entry for every one of them.

The real process uses about 4,500 pages out of the 68 billion possible ones: 0.0000065 %. The data structure has to exploit that extreme sparsity.

The solution is to make the table hierarchical and sparse: split the page number into several fields, each one indexing a level, and create only the lower-level tables that are actually needed.

x86-64 uses four levels (five on the most recent CPUs). The 36-bit page number is split into four 9-bit fields:

Each level has 2^9 = 512 entries of 8 bytes = exactly 4,096 bytes, one page. That fit is no accident: each table takes up precisely one page, which makes managing them enormously simpler.

The saving is spectacular. For a process with code at the bottom and a stack at the top:

60 KB against 512 GB. A factor of eight million.

The price: one translation requires four memory accesses (one per level) plus the access to the data itself. Five accesses where there used to be one. At ~100 ns per RAM access, that would be 500 ns for every memory read: the system would be 5 times slower than with no paging at all. Unacceptable.

That is the exact reason the TLB exists.

The TLB (Translation Lookaside Buffer) is an associative cache, inside the MMU, that stores the page→frame translations used recently. It is small (between 64 and 1,536 entries on modern CPUs) and blazingly fast (under 1 ns).

The flow:

1. The CPU generates a logical address.
2. The MMU looks up the page number in the TLB.
3. TLB hit: the frame is obtained directly. Cost ≈ 0.
4. TLB miss: the four levels of tables in memory have to be walked, and then the result is inserted into the TLB.

Calculating the effective access time (EAT) is the formula you need to be able to work out:

where h is the hit rate, t_TLB the TLB lookup time, t_mem the memory access and n the number of levels.

With realistic values (t_TLB = 1 ns, t_mem = 100 ns, n = 4):

The 99 % case in detail:

The practical conclusion is blunt: at a 99 % hit rate you lose only 4 %; at 70 % you lose more than half your performance. The TLB is not a minor optimization, it is what makes paging viable at all.

And that is why the cost of a context switch we calculated in 02-01 matters so much: when cr3 changes, the previous process's TLB entries stop being valid and are invalidated. The incoming process starts with an empty TLB and a burst of misses. PCIDs (process context identifiers) mitigate this by tagging each entry with the process it belongs to, so the whole TLB does not have to be flushed.

You can see the real TLB misses:

A 0.84 % miss rate, that is to say 99.16 % hits. Perfectly healthy. If you saw a 15 % miss rate, you would have a process with a very scattered access pattern, and that is where huge pages come in.

The problem appears when a process works with enormous data sets. Take the aggregator processing a whole day of readings:

They do not fit. Walking those 17 MB causes continuous TLB misses, because the translations evict each other. And with 30 days of history it would be 124,000 pages: the TLB would be useless.

Huge pages solve this by using a larger page size: 2 MB or 1 GB on x86-64. It is achieved by stopping the hierarchy one level early (a page directory entry points directly at a 2 MB block instead of at a table).

The aggregator's 17 MB go from 4,150 TLB entries to 9. That fits with room to spare, and the TLB misses practically vanish.

On Linux there are two ways of using them:

• THP (Transparent Huge Pages): the kernel automatically promotes large regions to 2 MB pages. The 215 MB of AnonHugePages show that it is already happening. It is convenient, but it has a known cost: the khugepaged daemon compacts memory in the background and can introduce pauses. That is why many databases recommend setting it to madvise or never.
• Explicit huge pages: they are reserved at boot and the application asks for them expressly. More control, less convenience.

The rule of thumb: huge pages help when the working set is large and is traversed in a scattered way; they get in the way when memory is scarce and paging is needed, because evicting 2 MB in one go is very expensive.

Here comes the piece that turns paging into virtual memory: not all of a process's pages need to be in RAM.

Demand paging means loading nothing until it is needed. When meteo-api starts, the kernel does not read its 820 KB of code: it creates the entries with P=0 and lets page faults bring in whatever is required. This explains the figures we saw in 02-03: libssl with 12 KB out of 1,024 KB loaded.

When the CPU accesses a page with P=0:

One essential detail at the end: the instruction that faulted is executed again from scratch. The process notices nothing at all. As far as it is concerned, that memory access simply took a long time.

This is where the numbers hurt. There are two very different kinds of fault:

The difference is three to four orders of magnitude:

And now the calculation that explains why the major fault rate has to be minuscule. With a normal memory access of 100 ns and a major fault of 8 ms:

With one major fault per thousand accesses, the system runs 81 times slower. To keep the degradation below 10 % you need fewer than one fault per million accesses.

This is not an academic curiosity: it is exactly what happens to a server that starts paging. It does not degrade smoothly, it falls off a cliff. And it is the reason for the thrashing we will see in section 10.

You can see your processes' faults:

Minor faults are normal and plentiful: they are part of ordinary operation. The major ones are the ones that matter: 112 in the aggregator after 22 hours is perfectly healthy. If you saw 400,000, the process would be reading constantly from swap and that would be the problem to solve.

When a page fault occurs and there are no free frames left, somebody has to be evicted. The choice determines how many faults there will be afterwards.

We will work out all the algorithms over the same reference string, which is the only honest way of comparing them:

It evicts the page that will not be used again for the longest time. It is impossible to implement (it requires knowing the future), but it serves as a lower bound to compare against.

9 faults.

It evicts the page that has been loaded the longest, regardless of how much it is used.

15 faults. 67 % more than the optimum.

FIFO has a flaw that defies intuition: giving it more memory can increase the number of faults. With this string:

With 3 frames:

9 faults.

With 4 frames:

10 faults. More memory, more faults.

The cause: FIFO does not have the stack property (that the set of pages held with n frames is contained in the set held with n+1 frames). When you add a frame, the eviction order changes completely and it can throw out precisely what was about to be needed. LRU and OPT do have that property and are therefore free of the anomaly.

It is the main reason why pure FIFO is not used in any real system: an algorithm you cannot promise will do better with more RAM is unacceptable.

It evicts the page that has gone longest without being used. It rests on the principle of temporal locality: what has been used recently will probably be used again.

12 faults. Between the optimum (9) and FIFO (15).

LRU's problem is the cost of implementing it. It requires keeping the pages ordered by last access, and that means updating a data structure on every memory access. You would need hardware that, on every read, moved an entry to the front of a list of thousands of elements. No CPU does this, because it would be ruinously expensive.

Since exact LRU is unworkable, it is approximated using the A bit (accessed), which the hardware does maintain for free.

The clock algorithm arranges the frames in a circle with a pointer:

1. The pointer points at a candidate frame.
2. If its A bit is 0, it is evicted and the pointer advances.
3. If its A bit is 1, it gets a second chance: A is set to 0 and the pointer moves on to the next one, evicting nothing.
4. Repeat until a frame with A = 0 is found.

The intuition is exactly right: a page with A=1 has been used since the pointer's last lap, so it will probably keep being used. One with A=0 has not been touched in a whole lap: it is a good candidate.

A better variant uses two bits, A and D, which combine recent use and eviction cost:

Linux uses a refined variant: two LRU lists (active and inactive) per memory zone, with promotion between them according to accesses, plus the A bit for ageing. It is approximate LRU, with the cost amortized down to almost nothing.

And here is the practical conclusion that is usually overlooked: the difference between the best possible algorithm and a decent one is 33 %; the difference between having enough RAM and not having it is a factor of 81. Optimizing the replacement algorithm matters far less than sizing memory correctly.

With 180 processes and 2 million frames, how many frames does each process get?

Equal allocation: frames / processes. Simple and unfair: meteo-api with 116 MB of data would get the same as an sshd using 9 MB.

Proportional allocation: hand out frames according to the size of each process.

And an important distinction:

• Local replacement: a process that faults can only steal frames from itself. Its performance is predictable but it does not take advantage of other processes' idle memory.
• Global replacement: it can steal from anybody. Better overall use, but one process's performance depends on how the others behave. Linux uses global replacement.

Here is the most important phenomenon in this section. If a process does not have enough frames for its working set, it enters a destructive cycle:

The loop feeds itself: the less CPU is used, the more processes are admitted, and the less memory is left for each one.

The symptoms are unmistakable and worth memorizing:

The combination CPU at 10 % with a load average of 40 is the diagnosis. If you saw this on meteo-01:

The data speaks for itself: 85 % %wa (I/O wait), 27 processes blocked in the b column, and si/so at around 50,000 KB/s in both directions. The system is fetching and shipping out the same pages over and over. No configuration tweak saves this: memory is missing.

The conceptual solution was formulated by Peter Denning in 1968. The working set W(t, Δ) is the set of pages referenced by a process in the last Δ references.

The rule is simple and powerful:

And when that happens, the only correct solution is to suspend processes — to reduce the degree of multiprogramming — so that the ones left have their complete working set. It is counter-intuitive but true: running fewer processes makes the system get more done.

Linux does not implement Denning's model literally, but its memory pressure handling and the OOM killer pursue the same goal: when the system cannot sustain everyone, it kills somebody instead of letting nobody make progress.

mmap() is one of the most powerful system calls in UNIX: it makes a file appear as memory.

Instead of open + read + copying into a buffer, the file is mapped into the address space and accessed as if it were an array.

What each part does and why it matters:

• mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0) asks the kernel to associate the file with a region of the address space. NULL lets the kernel pick the address; PROT_READ makes it read-only; MAP_PRIVATE means that writes (were there any) would be copy-on-write and would never reach the file.
• Nothing is read from disk at this point. The kernel merely creates page table entries with P=0. The 17 MB arrive on demand, as the loop touches them: every access to a new page causes a page fault that brings it in.
• close(fd) does not invalidate the mapping. The mapping keeps its own reference to the file. It is a detail that surprises people, and it lets you close descriptors without losing access.
• readings[i].temperature is ordinary pointer arithmetic. The compiler emits a memory access; the MMU and the kernel do the rest. There is not a single system call inside the loop.

That last point is the underlying reason for using mmap. Compare it with the read() alternative, applying what we calculated in 01-06:

The last row is especially valuable for Meteora: if the aggregator and meteo-api both map 2026-08-31.dat, the kernel's cache pages are physically shared. A single set of 17 MB in RAM serves both processes.

When mmap is not the right choice: for single-pass sequential reads of very large files, read() with a large buffer can be just as good or better, because mmap causes one page fault per 4 KB (thousands of exceptions), and because a file bigger than RAM mapped in its entirety can cause memory pressure.

With MAP_SHARED instead of MAP_PRIVATE, writes do propagate: to the file and to every process that maps it.

This is exactly the rw-s- region we saw in meteo-api's pmap in 02-03: the four workers share a single 8 MB cache. The inter-process communication mechanisms and the synchronization this demands belong to Inter-Process Communication (IPC) and Synchronization and Mutual Exclusion.

Now that you know the page table bits, the COW behind fork() that we saw in 02-01 can be explained precisely:

1. fork() copies the parent's page tables into the child.
2. In both copies, every writable page is marked R/W = 0 (read-only), and the kernel notes internally that they are COW.
3. Both processes point at the same physical frames. Zero data copied.
4. When either of them writes, the MMU detects R/W=0 and raises a protection page fault.
5. The kernel tells it apart from a genuine error (it checks that the region is COW rather than truly read-only), copies that single 4 KB page, assigns it exclusively to the writer and sets R/W=1 on it.
6. If the original frame's reference count drops to 1, the other process also gets R/W=1 back: there is nothing left to protect.

The numbers for meteo-api with its 148 MB:

And now you also understand why fork() can look cheap and then turn expensive: if the child writes all over the inherited memory, you will end up paying for the copy page by page, with one page fault per 4 KB. That is the classic complaint against fork() in huge processes, and the reason alternatives such as posix_spawn() and vfork() exist.

The swap area is the disk space where evicted anonymous pages are stored.

How to read free -h, which is where almost everybody goes wrong:

The 412 MB of free alarm a lot of people for no reason. The 4.3 GB of buff/cache are file pages the kernel keeps around in case they are needed again, and they are disposable on the spot. The memory that is really available is the 3.9 GB of available.

Free RAM is not RAM well spent. A system with free memory is wasting the chance to cache. What you want is a low free and a high available.

It controls how aggressively the kernel evicts anonymous pages rather than discarding file cache:

For meteo-01 a value of 10 would be reasonable: it is preferable to discard page cache (recoverable with a fast sequential read) rather than send meteo-api's response cache to swap (which would cause major faults right on the critical path of the requests).

An important warning: swappiness=0 does not disable swap, and disabling swap altogether is not a good idea either. With no swap, inactive anonymous pages — and on any system there are a lot of them — sit in RAM forever, and under memory pressure the kernel goes straight to the OOM killer with no intermediate options.

When there is no memory left and no frames to evict, the kernel triggers the Out Of Memory killer: it picks a process and kills it.

The choice is based on a score:

oom_score is proportional to the memory consumed, with adjustments: it penalizes large processes and those of ordinary users, and it protects root's processes and PID 1. oom_score_adj runs from −1000 (never kill it) to +1000 (kill it first) and is the part you can tune yourself:

The trail it leaves in the log:

How to read it line by line, which is what you need to be able to do when you are on call:

• aggregator invoked oom-killer: the one that triggered the OOM was the aggregator when it asked for memory. That does not necessarily make it the culprit, although here it is.
• The task table lists every process with its rss in pages. The aggregator has 1,180,221 pages × 4 KB = 4.5 GB. meteo-api has 33,785 × 4 KB = 132 MB.
• Killed process 1877 (aggregator) with anon-rss:4720884kB: the one consuming the most anonymous memory was chosen, which is the usual criterion.
• anon-rss versus file-rss: those 4.7 GB are anonymous, that is, dynamic memory with no file backing it. Killing the process frees them immediately. If it had been file-rss, killing it would have freed almost nothing.

That figure of 4.5 GB in an aggregator that under normal conditions uses 31 MB is the complete diagnosis: it is processing a whole day by loading everything into memory instead of block by block. The fix is a design fix — mmap or block-wise reading — not a configuration one.

Remember too what we saw in 02-01: when the OOM killer kills a process, that process dies from SIGKILL (signal 9), which your supervisor would detect with WIFSIGNALED(status) and WTERMSIG(status) == 9.

We close with the tools and how to read them without going wrong.

The problem with RSS, with a concrete example: if meteo-api has 4 workers and each one reports 148 MB of RSS, adding them gives 592 MB, but the real consumption may be 200 MB because they share code, libc and the /dev/shm cache. PSS solves this by dividing each shared page among those using it:

94 MB in reality against 148 MB of RSS. To account for memory on a server whose processes share a great deal, PSS is the correct metric.

/proc/meminfo gives the global picture:

The lines that really tell you something:

• MemAvailable: 3.9 GB. The only one that answers "how much memory can I use?".
• AnonPages 2.9 GB: the processes' anonymous memory. It can only go to swap.
• Cached 4 GB: file pages. Disposable on the spot.
• Dirty 28 MB: modified but not yet written to disk. If this figure climbs a lot, there is a write bottleneck. Forcing it to be flushed is what fsync() does.
• Slab 298 MB: the kernel's own data structures (inodes, dentries, task_struct). It is not process memory.

And vmstat to see the dynamics:

The critical columns for memory:

• si/so (swap in / swap out, in KB/s): the most important metric. A swpd of 512 MB with si/so at zero is harmless: they are old pages evicted long ago that nobody is asking for. What is serious is sustained si/so: that really is thrashing.
• b: processes blocked in uninterruptible I/O (the D state from 02-01).
• wa: percentage of CPU waiting on I/O.

The diagnostic rule that sums up the lesson: look at si/so, not at swpd. Having swap occupied is normal; having swap in constant motion means RAM is missing.

Panicking because free is low. The right column is available. A healthy system has little free memory and a lot of cache, because idle RAM is wasted RAM.

Confusing swpd with actually paging. The fact that there are 512 MB in swap says nothing on its own: they may have been sitting there for days with nobody asking for them. What signals a problem is sustained si/so in vmstat.

Disabling swap "so the system does not slow down". With no swap, the kernel loses its intermediate tool and under memory pressure it goes straight to the OOM killer. The sensible configuration is to have swap and lower swappiness, not to remove it.

Adding up the RSS of several processes. It gives an inflated total because shared pages are counted several times. To add them up, use PSS.

Believing that the OOM killer kills the culprit. It kills whoever has the highest score, which is usually the biggest one. If the aggregator causes the shortage and meteo-api is the one holding the most memory, meteo-api dies. Protect what is critical with a negative oom_score_adj.

Enabling THP everywhere. Transparent 2 MB pages help workloads with large working sets, but khugepaged compacting memory can introduce pauses of tens of milliseconds. Databases usually recommend madvise or never for exactly this reason.

Reading a SIGSEGV as a system bug. It is the MMU doing its job: the process accessed an address with no valid translation or without the right permissions. Compare the address against /proc/<pid>/maps to find out whether it was a corrupt pointer (it falls in a gap) or a write into a read-only area.

Diagnostic tip: when you suspect a memory problem, this is the order that works: free -h (look at available), vmstat 1 (look at si/so and wa), ps -eo pid,rss,maj_flt --sort=-rss | head (who is consuming and who is faulting), pmap -x <pid> (which region is growing) and dmesg -T | grep -i oom (whether somebody has already died). Five commands and you have the whole picture.

A system has 32-bit logical addresses and 4 KB pages.

1. How many bits do the page number and the offset take? How many pages are there at most?
2. With this page table, translate the logical addresses 0x00003ABC, 0x00001234 and 0x00006000:

3. Calculate the size of a flat table with 4-byte entries. Compare it with the 64-bit case from section 4 of the lesson.
4. With a 96 % TLB hit rate, a memory access of 80 ns, a TLB lookup of 2 ns and 2 table levels, calculate the effective access time.

The aggregator generates this page reference string:

1. Calculate the page faults with 3 frames for: optimal, FIFO and LRU. Show the state of the frames at each step.
2. Repeat with 4 frames.
3. Which algorithm exhibits Belady's anomaly? Demonstrate it with your own numbers.
4. If every major fault costs 8 ms, calculate the total time lost in each case with 3 frames.

meteo-01 is responding extremely slowly. You collect this data:

1. Diagnose what is wrong with the system. Name the phenomenon and justify it with at least four pieces of evidence.
2. Why is CPU usage at 3 % if the system is crawling?
3. Identify the root cause. How much memory should the aggregator be using, given that it processes one day of readings?
4. Propose three solutions: an immediate one, a configuration one and a design one. State which is the correct one.
5. Write the piece of code that would fix the problem at its root.

Solution 1

1. Decomposing the address.

2. Translations.

0x00003ABC:

The hexadecimal shortcut: the three right-hand digits (ABC) are preserved and the left-hand ones go from 00003 to 0002C.

0x00001234:

0x00006000:

It is important to tell this case apart from page 4, which does exist but has Present = No: there the fault would be recoverable (the kernel would bring it in from swap or from the file and retry the instruction), whereas here it is a genuine program error.

3. Size of the flat table in 32 bits.

Comparison with 64 bits:

And here is the key observation of the exercise: 4 MB per process is already too much. With 180 processes that is 720 MB of tables alone, almost 9 % of meteo-01's 8 GB, and the vast majority of those entries would be empty. That is why even 32-bit systems used multilevel tables (32-bit x86 had two levels). The flat table was never viable; in 64 bits it goes from unviable to plainly absurd.

4. Effective access time.

Degradation against a pure access (80 ns): 88.4 / 80 = 1.105, that is 10.5 %.

It is worth noticing how much weight that 4 % of misses carries: it contributes 9.68 ns out of the 88.4 total, 11 % of the time, while being only 4 % of the accesses. It is the typical arithmetic of caches, and it explains why improving from 96 % to 99 % hits is worth the effort:

Solution 2

1. With 3 frames.

Optimal (evicts the page that will reappear last):

The eviction decisions: at position 4, 3 leaves (it reappears at 10, later than 1 and 2); at 7, 4 leaves (it reappears at 11); at 10, 1 leaves (it never comes back); at 11, 2 leaves (it does not come back either).

7 faults.

FIFO:

9 faults.

LRU:

10 faults.

2. With 4 frames.

Optimal:

With 4 frames, 1, 2, 3 and 4 all fit from the start. When 5 arrives, 4 is evicted, because it reappears at position 11, later than 1, 2 and 3. At position 10 the 3 is already resident, so there is no fault. At 11 the 4 has to be brought back and 1 is evicted, since it is never used again.

6 faults.

FIFO:

10 faults.

LRU:

A trace of the evictions: when 5 arrives (position 7), the order of use is 3, 4, 1, 2, so 3 leaves. At position 10 the 3 is needed and the least recently used is 4. At 11 the 4 is needed and 5 leaves. At 12 the 5 is needed and 1 leaves. Notice the pattern: the last three references all fault because LRU has just evicted exactly what is asked for next.

8 faults.

3. Belady's anomaly.

FIFO exhibits the anomaly: going from 3 to 4 frames raises the faults from 9 to 10.

The structural explanation: FIFO does not satisfy the stack property. Formally, an algorithm satisfies it if the set of resident pages with n frames is always a subset of the set with n+1 frames. LRU and OPT satisfy it because their decision depends on the reference pattern, which does not change when frames are added. FIFO decides by arrival order, and that order is completely altered by changing the number of frames: with 4 frames, pages 1 and 2 survive longer and end up being evicted just before they are needed again.

It is an important result because it breaks an intuition that seemed safe, and it is the practical reason why no real system uses pure FIFO: you cannot promise that adding RAM will improve performance.

4. Time lost with 3 frames.

An honest observation about these numbers: here LRU comes out worse than FIFO, which contradicts the general intuition. It is an artefact of this particular string, designed precisely to exhibit Belady's anomaly. With real strings, which show strong temporal locality, LRU clearly beats FIFO. It is a good reminder that a twelve-reference string proves nothing about an algorithm's general behavior; for that you need real traces of millions of references.

What the comparison does prove is the order of magnitude of the problem: 12 memory accesses that should have cost 1.2 microseconds have cost between 56 and 80 milliseconds. A factor of 50,000. When frames are missing, the replacement algorithm is the least of your worries.

Solution 3

1. Diagnosis: thrashing.

The evidence that confirms it, one item at a time:

The decisive figure is si and so both high at the same time. If there were only so, the system would be freeing memory in an orderly way. Traffic in and out simultaneously at 40 MB/s means that the same pages are being evicted and fetched back without pause: the working set does not fit in RAM and every evicted page is needed immediately afterwards. It is the exact definition of the feedback loop in the lesson's diagram.

2. Why the CPU is at 3 %.

Because there is nothing to run. Almost every process is in state D, blocked waiting for the disk to bring in a page. The r column (runnable) reads 0 or 1, while b (blocked) reads 31.

This is the most deceptive pattern of all: an almost idle CPU with the system completely stalled. Anyone looking only at CPU usage will conclude that the server is fine and go looking for the problem somewhere else. The combination to recognize instantly is low us+sy + sky-high wa + high b.

A calculation that puts a size on it: 892,104 major faults in the aggregator, at about 100 µs each with an SSD, come to 89 seconds of pure waiting. With a mechanical disk at 8 ms it would be ~2 hours of disk time.

3. Root cause.

The aggregator has 4,720,884 KB = 4.5 GB of RSS on a 7.8 GB machine. On its own it is 60 % of the total RAM. Neither meteo-api (148 MB) nor ingestor (18 MB) matters by comparison.

How much it should be using:

And at 24 bytes per reading, those 4.5 GB amount to some 196 million readings: more than 270 days of data. The diagnosis is immediate: the aggregator is loading the entire history into memory instead of the one day it needs to process, most likely because of a readdir over /var/lib/meteora/readings/ with no date filter, accumulating everything into an in-memory structure.

4. Three solutions.

Immediate (get the server back now):

It frees 4.5 GB instantly. The system stops paging within seconds. It is a plaster, not a cure: it will happen again on the next run.

Configuration (contain the damage):

With MemoryMax=512M (a cgroup limit, the subject of 06-02), an aggregator that tries to go past 512 MB dies on its own without dragging the rest of the system down. This turns a system-wide outage into an isolated failure, which is exactly what you want. It does not fix the bug, but it contains it.

Design (the correct one):

Process as a stream, not by loading everything. Two valid variants: read in blocks with read(), or map the day's file with mmap() and let demand paging manage the memory.

5. The code that fixes it.

The mmap() version, which applies directly what the lesson covered:

Why this fixes the problem at its root:

• One day per run. The path is built from the date it is given: loading the whole history by accident is impossible.
• The accumulators have a fixed size: 64 × 24 × 32 bytes = 48 KB, independent of the volume of data. This is the heart of the fix: the process's memory no longer grows with the input.
• mmap consumes no RSS of its own. The mapped pages belong to the kernel's page cache, which is disposable under memory pressure (they are clean and file-backed, as we saw in 02-03). If RAM runs short, the kernel discards them without writing anything and re-reads them later. Compared with the 4.5 GB of anonymous memory in the previous version — which could only go to swap — this changes the system's behavior under pressure completely.
• madvise(MADV_SEQUENTIAL) tells the kernel that access will be sequential. The kernel turns on aggressive read-ahead and discards the pages already walked sooner. It is a small optimization to write and a very effective one on full traversals.

The resulting consumption:

A reduction by a factor of 140, and not a single anonymous page that could drag the system into thrashing.

Paging divides the logical space into pages and physical memory into frames of the same size, and translates every address by separating the page number from the offset — which is never translated. Each table entry carries the frame plus a set of control bits that govern everything: P enables virtual memory, R/W and NX implement W^X, and A and D, written by the hardware, are the only clue the kernel has for deciding who to evict and at what cost.

A flat table in 64 bits would take 512 GB per process, so tables are multilevel and sparse: four levels of 9 bits, each table occupying exactly one page, and 60 KB in practice instead of 512 GB. The price is four memory accesses per translation, and that is why the TLB exists: at a 99 % hit rate you lose 4 % of your performance, at 70 % you lose more than half. Huge pages cut 4,150 TLB entries down to 9 for the aggregator's 17 MB, at the cost of internal fragmentation and a coarse eviction granularity.

Demand paging means nothing is loaded until it is touched, which explains libc with only 44 % of its code in RAM. A minor fault costs microseconds and is normal; a major fault costs milliseconds, and with one per thousand accesses the system runs 81 times slower. The replacement algorithms — optimal as a bound, FIFO with its Belady's anomaly, LRU unworkable in its exact form, and the clock as a cheap approximation using the A bit — move within a margin of 33 %, far less than having enough RAM matters. When the working set does not fit, thrashing appears: CPU at 3 %, wa at 88 % and the system at a standstill.

And all of this can be touched with your own hands: mmap() turns 4,219 system calls into one and lets two processes physically share the same 2026-08-31.dat; the copy-on-write behind fork() is simply R/W=0 plus a protection fault; swappiness decides what gets sacrificed first; and the OOM killer leaves a trail in dmesg that you read process by process. The rule that sums up the operational side: look at available and not at free, look at si/so and not at swpd, and add up PSS and not RSS.

With this we close memory. What remains is the other great resource the operating system administers, and the one that has appeared in every major fault in this lesson: storage. How much that disk access we have been counting in milliseconds really costs, why an SSD changes all the rules, how requests are ordered to minimize head movement and what RAID configuration /var/lib/meteora deserves. That is what we will see in Storage Management.