Virtual memory and page replacement — theory with gcc in three frames, FIFO, LRU and the optimal head to head (and the laptop that crawled with 40 tabs)

Deadline week. I had 40 Chrome tabs open (half of them IC2 documentation), VS Code compiling the assignment, Spotify and Teams. The laptop has 8 GB of RAM and, suddenly, everything started to stutter: the mouse froze for half a second, Spotify cut the song and the fan sounded like a hair dryer. I opened Windows Resource Monitor and saw two things: the disk at 100 % and, in the Memory tab, a column I had never looked at: hard faults per second, with four-digit numbers. The CPU, on the other hand, was almost idle. How can everything be slow if the CPU is doing nothing?

The answer is the second half of Topic 5 of IC2. In the previous topic, Memory management, we saw how paging splits RAM into frames and translates addresses. Today we take the step that changes everything: a process does not have to be entirely in RAM to run. We will see what happens when it asks for a page that is not there (the page fault), how the OS decides whom to evict (FIFO, the optimal, LRU and its approximations), why giving more memory can make things worse (Belady’s anomaly) and what was wrong with my laptop (thrashing). All with an example that keeps coming back: gcc, with 8 logical pages and only 3 frames of RAM. When you finish, you have the exam-style virtual memory exercises.

The idea: it does not have to fit whole

Until now, to run a process all its pages had to be loaded. But think about gcc: it has code to optimise, to report errors, for C++, for assembly… and a normal compilation uses a small part of it. Why fill RAM with what is not going to be used?

Virtual memory is the technique that lets a process run even though only part of its pages are in main memory; the rest stays in secondary storage, which acts as an extension of RAM. The OS moves pages between the two transparently: the programmer decides nothing and writes the program as if they had all the memory in the world.

Look at the drawing: at t = 3 gcc only has pages 1, 2 and 3 in RAM (in frames 5, 9 and 2, the same ones it used in Topic 9). The other five have an i in the page table: they are not in RAM but in the swap area, a part of the disk the OS reserves for this. All eight pages always exist on disk; RAM only holds a copy of the ones being used.

What do we gain?

• Programs bigger than RAM: a process’s logical space is no longer limited by physical memory.
• More processes at once: if each one takes only what it uses, more of them fit (a higher degree of multiprogramming, and the CPU has more to choose from).
• Faster start-up: there is no need to read the whole program before starting.
• Less I/O: what is never used is never read.

Demand paging

How does the OS decide which pages to load? The usual way is the laziest possible one: with demand paging, a page is not read from disk until the process references it for the first time.

gcc’s reference string in this article uses pages 1, 2, 3, 4, 5 and 7. With a full load all 8 pages would be read at the start; with demand paging 6 are read, each one when it is asked for, and 0 and 6 are never read. That saving is exactly what makes the idea worth it.

To know whether a page is in RAM, each page table entry has, besides the frame number, a few bits:

Bit	Set by…	What it is for
v (valid or present)	the OS, when loading or evicting the page	v = in a frame; i = on disk → accessing it is a page fault
R (reference)	the hardware, on every access	knowing what has been used recently (LRU approximations); the OS clears it periodically
M (modified, “dirty”)	the hardware, on every write	knowing whether the page must be saved to disk before evicting it
protection	the OS	what is allowed: read, write, execute

The page fault, step by step

A page fault is the interrupt (trap) the MMU raises when a process references a page whose valid bit is i. It is not a bug in the program: it is the signal that the OS has to bring that page in. Let’s look at gcc at t = 7, when it asks for page 4:

1. Reference: gcc runs an instruction that touches page 4.
2. Trap: the MMU looks at the table, sees an i and jumps to the OS kernel (what we saw in Topic 5, interrupts).
3. Find: the OS checks that the address is legal (if it were not, the process would die with a segmentation fault) and locates the page in the swap area.
4. Read: it asks the disk to copy the page into a free frame. Meanwhile, gcc becomes blocked and the CPU serves another process.
5. Update: it writes the frame number (9) into the entry and sets the bit to v.
6. Restart: gcc goes back to ready and, when its turn comes, restarts the instruction that faulted, which now finds the page.

When there is no free frame left

Step 4 assumes there is a free frame. At t = 7 gcc already has its 3 frames full (with 1, 5 and 2), so before reading someone has to be evicted: a victim page must be chosen. Who the victim is gets decided by the replacement algorithm (next section). What matters now is how much evicting it costs:

If the victim has M = 0 (clean), its copy on disk is identical and it can simply be overwritten: a single disk operation, reading the new page. If it has M = 1 (dirty), it must first be written to disk and then the new one read: two operations. The full steps are: fault → no free frames → choose a victim → if M = 1, write it → mark it as i in its table → read the new one → update its entry → restart the instruction.

That is why operating systems do precleaning: when idle, they write dirty pages to disk and set M = 0, so the next victim is more likely to be clean.

How much a fault costs: the effective access time

A RAM access takes about 100 ns; serving a page fault, about 8 ms (8,000,000 ns), because the disk is involved. If p is the probability that an access causes a fault, the effective access time is:

EAT = (1 − p) · memory access time + p · page fault service time

Let’s do the maths with one fault every 1,000 accesses (p = 0.001): EAT = 0.999 · 100 + 0.001 · 8,000,000 = 99.9 + 8,000 = 8,099.9 ns. Memory looks 81 times slower (8,099.9 / 100 ≈ 81). With one fault per million: 99.9999 + 8 ≈ 108 ns, 8 % slower.

This explains half of what was wrong with my laptop: thousands of faults per second, each one waiting milliseconds for the disk. The other half (why there were so many) comes at the end.

Page replacement algorithms

When a victim must be chosen, whom do we evict? The goal is to cause as few page faults as possible. To compare algorithms we use a reference string: the list of pages the process asks for, in order. gcc’s string in this article is this one:

The three classic algorithms get exactly the same string and the same 3 frames (empty at the start). There is something none of them can avoid: the first time each page is asked for, it faults. These are the compulsory faults, and here there are 6, one per distinct page (1, 2, 3, 5, 4 and 7). Everything above 6 is the algorithm’s fault.

FIFO: first in, first out

FIFO evicts the page that has been loaded in memory the longest. A queue is enough: pages come in at the back and the victim leaves from the front.

Read the trace column by column. In the coral cells a page comes in (fault); in the green ones, the requested page was already there (hit); in the “out” row, the victim. The first three faults fill the frames (the 1 at t = 2 is a hit). At t = 4 page 5 arrives and FIFO evicts page 1 because it came in first, at t = 0, even though gcc had used it at t = 2. Result: at t = 5 gcc asks for page 1 again and faults again. The same at t = 8: it evicts page 1, which was used at t = 5, and at t = 9 it faults with it again. Total: 11 faults out of 15 references.

t	ref	frames after	fault?	out	why that one
3	3	1 2 3	yes	—	there was a free frame left
4	5	5 2 3	yes	1	page 1 came in at t = 0, the oldest
5	1	5 1 3	yes	2	page 2 came in at t = 1
6	2	5 1 2	yes	3	page 3 came in at t = 3
7	4	4 1 2	yes	5	page 5 came in at t = 4

FIFO’s problem is plain to see: it does not look at whether a page is used, only at when it came in. A heavily used page, like gcc’s page 1 (the main loop, say), leaves just like one that is never touched again.

The optimal algorithm (OPT or MIN)

What would the best possible decision be? Evicting the page that will be needed the latest. The optimal algorithm replaces the page that will take the longest to be referenced again (or that will never be referenced again).

At t = 4 page 5 arrives with 1, 2 and 3 in memory. Looking ahead, 1 comes back at t = 5, 2 at t = 6 and 3 at t = 12: page 3 leaves. Thanks to that, at t = 5 and t = 6 it hits where FIFO missed. Total: 7 faults, only one more than the compulsory ones. It has been proved that no algorithm can produce fewer faults with the same string and the same frames.

So why doesn’t everyone use it? Because it needs to know the future: the OS does not know which pages gcc will ask for in a while. The optimal is impossible to implement in a real OS; it serves as a yardstick: an algorithm is better the closer it gets to it.

LRU: the one unused for the longest

If we cannot see the future, let’s use the recent past as a prediction. LRU (Least Recently Used) evicts the page that has gone unused for the longest. The idea relies on locality, which we will see below: what has been used recently will probably be used again soon.

At t = 4 page 5 arrives. The last uses are: page 1 at t = 2, page 2 at t = 1 and page 3 at t = 3. Page 2 leaves and page 1 stays; that is why at t = 5 LRU hits with page 1 where FIFO missed. Total: 9 faults, between FIFO (11) and the optimal (7).

But LRU has a practical problem: you need to know on every access which page has been used, and that is millions of times per second. There are two ways to implement it exactly:

• Counter: each entry stores the instant of its last use (the hardware copies a clock on every access) and the victim is the one with the smallest value. All entries have to be searched.
• Stack: every time a page is used, it is taken out from wherever it is and put on top; the victim is the one at the bottom. Moving the page on every access is expensive.

Both need special hardware or are painfully slow in software. That is why, in practice, LRU approximations with the R bit are used (below).

What each one looks at

At t = 7 the three algorithms have the same pages in memory (1, 2 and 5, though in different frames) and page 4 arrives. Each one asks a different question:

FIFO and LRU agree here on evicting page 5, but for different reasons: for FIFO it is the one that came in first (t = 4); for LRU, the one that has gone unused the longest (also t = 4, because it has not been asked for again since it came in). The optimal evicts page 2: neither 2 nor 5 appears again, so it does not matter which of the two (the simulator keeps the first one in frame order).

Algorithm	Victim	Faults (gcc, 3 frames)	Implementable?	Belady
FIFO	the one that came in first	11	yes, very cheap (a queue)	can suffer it
Optimal	the one that will be used the latest	7	no: it needs the future	no
LRU	the one unused for the longest	9	expensive (counter or stack on every access)	no

Belady’s anomaly

The logical thing would be to think that more frames always means fewer faults (or the same). With FIFO, not always. Belady’s anomaly is that increasing the number of frames increases the number of page faults. Look at this string with FIFO:

With 3 frames, 9 faults; with 4 frames, 10. What happened? With 4 frames pages 3 and 1 hit at t = 4 and t = 5, so FIFO does not remove them and, when page 5 arrives, it evicts page 3, which is exactly the one asked for next; from then on it chains one fault after another. With 3 frames the order of departures is different and it hits at t = 7 and t = 8.

Why don’t LRU and the optimal suffer it? Because they are stack algorithms: the set of pages they have in memory with n frames is always contained in the one they would have with n + 1. With one more frame they have everything they had before plus one, so they cannot fault more. FIFO does not have that property.

LRU approximations

Almost every processor sets the R bit to 1 when a page is accessed, and the OS can set it to 0 whenever it wants. With that cheap bit, algorithms that resemble LRU without paying its price are built.

Second chance (clock algorithm)

Second chance is FIFO plus the R bit: before evicting a page, its reference bit is checked; if it is 1, it is set to 0 and the page gets another chance. The clock version arranges the frames in a circular list with a hand:

The hand points at page 1, which has R = 1: R is set to 0 and the hand moves on. Page 4 has R = 0: it is the victim. Page 1 escaped, but now it has R = 0; if nobody uses it before the next round, it goes. If all of them had R = 1, the hand would go all the way round setting them to 0 and would end up evicting the first one: in the worst case it behaves like FIFO.

NRU: not recently used

NRU (Not Recently Used) sorts pages into four classes by the R and M bits, and picks the victim at random within the lowest non-empty class.

Class 0 (R = 0, M = 0) is the perfect victim: not used recently and no need to write it. Notice the order of classes 1 and 2: NRU would rather evict a dirty unused page (class 1) than a clean used one (class 2). Writing costs, but evicting something being used costs more, because it will fault again soon. And how can there be pages with M = 1 and R = 0? Because the OS clears R periodically, but not M (if it cleared M, it would lose the information that the page has to be written).

NFU, LFU and aging

These three use counters instead of a single bit:

• NFU (Not Frequently Used): at regular intervals (every clock tick), the OS adds each page’s R bit to its counter and clears R. The victim is the one with the lowest counter. Problem: it never forgets; a page heavily used at the start keeps a high counter even if it is no longer used.
• LFU (Least Frequently Used): each page keeps a counter of the number of references, and the one with the lowest counter is evicted. Same problem: the old weighs as much as the recent.
• Aging: fixes NFU’s memory problem. Every tick, each page’s register shifts one bit to the right and the R bit enters from the left. So the leftmost bit is the latest tick and old ones fall off the right.

I split gcc’s references from t = 0 to t = 11 into four ticks of three references and followed the three pages LRU has in memory at t = 11: 1, 4 and 7. At the end, page 1 is 1011 (11) and pages 4 and 7 are 1100 (12). The victim is the lowest value, page 1: exactly the one LRU evicts at t = 12. What aging cannot do is tell 4 from 7, which tie: LRU knows that 4 was used at t = 10 and 7 at t = 11, but aging only knows both were used in the last tick. It is an approximation.

WSClock

WSClock combines the clock with the working set (coming up next): the hand goes round a circular list and, for each page, uses the R bit, the instant of its last use (U) and a time window (Δ). If the page has R = 1, R is set to 0 and the current instant is recorded as U; if it has R = 0 and has gone more than Δ unused, it is a victim candidate (and if it is dirty, its write is scheduled and the search continues for a clean one).

Algorithm	What it keeps per page	Whom it evicts
Second chance / clock	R bit	the first page with R = 0 the hand finds
NRU	R and M bits	at random, from the lowest non-empty class
NFU	counter that adds R every tick	the one with the lowest counter
LFU	reference counter	the one with the lowest counter
Aging	shifted register with R entering from the left	the one with the lowest value
WSClock	R bit, last use U (and window Δ)	one with R = 0 and clock − U > Δ (preferably clean)

Locality and the working set

Why does all this work? Because processes do not jump at random through their pages. Locality is the tendency of a process to concentrate its accesses, for a while, on a few areas of code and data. A loop repeats the same instructions; a function uses its local variables; walking through an array moves through contiguous pages.

Look at it in gcc: from t = 0 to t = 6 it moves through pages 1, 2, 3 and 5; from t = 7 to t = 14, through 1, 3, 4 and 7. Each stretch is a locality. If the process has its whole current locality in RAM, it barely faults; when it changes locality, it faults a few times until the new one is loaded.

To measure locality we use the working set: the working set WS(t, Δ) is the set of distinct pages the process has referenced in the last Δ references (the window).

With Δ = 4, at t = 9 the window holds the references from t = 6 to t = 9 (2, 4, 7 and 1): WS = {1, 2, 4, 7} and |WS| = 4. At t = 13 the window is 4, 7, 3, 7: page 7 repeats and only counts once, so WS = {3, 4, 7} and |WS| = 3. The window is delicate: if Δ is too small, it does not cover the whole locality; if it is too large, it mixes several localities.

Real operating systems do not keep the whole window. They use a virtual clock of the process and, per page, the instant of its last use U. The exam rule is: a page is in the working set if clock − U ≤ Δ. For example, with clock = 50 and Δ = 8, a page with U = 45 is inside (50 − 45 = 5 ≤ 8) and one with U = 40, outside (10 > 8).

And now the important part: the size of gcc’s working set reaches 4 at several moments (t = 4, 6, 7, 8, 9 and 12), but gcc only has 3 frames. At those moments its locality does not fit and it has to evict pages it is about to ask for. Remember FIFO’s and LRU’s faults between t = 4 and t = 9? There they are.

Thrashing

Now multiply that by every process. Thrashing is the situation in which processes do not have enough frames for their working set and page faults chain together: the system spends more time paging than running.

The vicious circle works like this: a process faults and evicts a page of another; that other one faults shortly after and evicts one of the first; both block waiting for the disk; the CPU runs out of work and CPU use drops. A naive scheduler sees the idle CPU and admits more processes, which need more frames… and the fall speeds up. That is the curve on the left of the drawing.

The way to see it with numbers is to add up everyone’s working sets: D = Σ |WSᵢ|. If D is larger than the number of available frames, thrashing is certain. In the simulator, at t = 3, gcc needs 3 frames, spotify 3, the campus 4 and onedrive 2: D = 3 + 3 + 4 + 2 = 12, and there are only 10 free frames. They do not fit. If the OS suspends onedrive (what in Topic 6 we called medium-term scheduling), D = 10 and they just fit.

That was my laptop: 40 tabs, VS Code, Spotify and Teams with working sets that added up to more than my 8 GB. The disk at 100 %, thousands of hard faults (page faults) per second and the CPU waiting.

How does the OS avoid it?

• Working set model: give each process at least |WS| frames and, if D does not fit, suspend processes until it does.
• Page fault frequency (PFF): keep an eye on how many faults each process has.

With PFF a band is set: if a process’s fault rate goes above the upper limit, it is short of frames and is given more; if it drops below the lower limit, it has too many and some are taken away. If frames must be given and none are free, some process is suspended.

How the program is written matters too. Whatever breaks locality increases faults:

• Linked structures (lists, trees) whose nodes are spread over many pages.
• Interpreted languages with run-time type checking, which run a lot of interpreter code for each line.
• Very large functions, which take up many pages.
• Walking through an array by columns when it is stored by rows.

On the other hand, the stack, arrays walked in order and the compact code of a compiled language have very good locality.

Common mistakes

Check it with Python

Let’s check the three traces with a simulator. It has fixed data (gcc’s string and 3 frames), asks for nothing from the keyboard and has been run only once; the output you will see is the one from that run.

# FIFO, LRU and optimal with the same gcc reference string and 3 frames
REFS = [1, 2, 1, 3, 5, 1, 2, 4, 7, 1, 4, 7, 3, 7, 4]   # pages gcc asks for, in order
N_FRAMES = 3                                            # frames the OS gives gcc

def victim(alg, frames, t, refs, arrival, last_use):
    if alg == 'FIFO':        # the one in memory the longest (came in first)
        return min(frames, key=lambda p: arrival[p])
    if alg == 'LRU':         # the one nobody has used for the longest
        return min(frames, key=lambda p: last_use[p])
    future = refs[t + 1:]    # optimal: the one asked for again the latest (or never)
    return max(frames, key=lambda p: future.index(p) if p in future else len(future))

def simulate(alg, n_frames, refs, trace=True):
    frames = [None] * n_frames    # each position is a fixed physical frame
    arrival, last_use, faults = {}, {}, 0
    for t, p in enumerate(refs):
        out, hit = None, p in frames
        if hit:                   # hit: only the last use is noted (for LRU)
            last_use[p] = t
        else:
            faults += 1
            if None in frames:    # there is still a free frame: no victim needed
                i = frames.index(None)
            else:
                out = victim(alg, frames, t, refs, arrival, last_use)
                i = frames.index(out)   # the new one takes the victim's frame
            frames[i] = p
            arrival[p] = last_use[p] = t
        if trace:
            row = ' '.join('-' if m is None else str(m) for m in frames)
            res = 'hit' if hit else 'FAULT  '
            tail = f'out: {out}' if out is not None else ''
            print(f'{t:>2}  {p:>3}  [{row}]  {res}  {tail}'.rstrip())
    return faults

for alg in ('FIFO', 'LRU', 'OPT'):
    print(f'== {alg} with {N_FRAMES} frames ==')
    print(f"{'t':>2}  {'ref':>3}  {'frames':<7}  {'access':<7}  victim")
    f = simulate(alg, N_FRAMES, REFS)
    print(f'{alg}: {f} page faults in {len(REFS)} references\n')

The interesting part is in victim, which is where each algorithm decides. Let’s look at it up close:

def victim(alg, frames, t, refs, arrival, last_use):
    if alg == 'FIFO':        # the one in memory the longest (came in first)
        return min(frames, key=lambda p: arrival[p])
    if alg == 'LRU':         # the one nobody has used for the longest
        return min(frames, key=lambda p: last_use[p])
    future = refs[t + 1:]    # optimal: the one asked for again the latest (or never)
    return max(frames, key=lambda p: future.index(p) if p in future else len(future))

The three cases use the same idea, finding the minimum or the maximum of something:

• FIFO: min over arrival, the instant each page came in. The smallest is the oldest.
• LRU: min over last_use, the instant of the last access. That is why simulate updates last_use[p] on hits too, and arrival[p] only when the page comes in.
• Optimal: max over the position of the next appearance in future. If a page never appears again, we give it len(future), a value larger than any position, so that it becomes the favourite. If there is a tie, max keeps the first one in frame order.

Another detail: frames is a list with one position per physical frame and the new page takes the victim’s slot (frames.index(out)). That way the trace reads like the tables in the drawings: each column inside [ ] is always the same frame. This is the real output:

== FIFO with 3 frames ==
 t  ref  frames   access   victim
 0    1  [1 - -]  FAULT
 1    2  [1 2 -]  FAULT
 2    1  [1 2 -]  hit
 3    3  [1 2 3]  FAULT
 4    5  [5 2 3]  FAULT    out: 1
 5    1  [5 1 3]  FAULT    out: 2
 6    2  [5 1 2]  FAULT    out: 3
 7    4  [4 1 2]  FAULT    out: 5
 8    7  [4 7 2]  FAULT    out: 1
 9    1  [4 7 1]  FAULT    out: 2
10    4  [4 7 1]  hit
11    7  [4 7 1]  hit
12    3  [3 7 1]  FAULT    out: 4
13    7  [3 7 1]  hit
14    4  [3 4 1]  FAULT    out: 7
FIFO: 11 page faults in 15 references

== LRU with 3 frames ==
 t  ref  frames   access   victim
 0    1  [1 - -]  FAULT
 1    2  [1 2 -]  FAULT
 2    1  [1 2 -]  hit
 3    3  [1 2 3]  FAULT
 4    5  [1 5 3]  FAULT    out: 2
 5    1  [1 5 3]  hit
 6    2  [1 5 2]  FAULT    out: 3
 7    4  [1 4 2]  FAULT    out: 5
 8    7  [7 4 2]  FAULT    out: 1
 9    1  [7 4 1]  FAULT    out: 2
10    4  [7 4 1]  hit
11    7  [7 4 1]  hit
12    3  [7 4 3]  FAULT    out: 1
13    7  [7 4 3]  hit
14    4  [7 4 3]  hit
LRU: 9 page faults in 15 references

== OPT with 3 frames ==
 t  ref  frames   access   victim
 0    1  [1 - -]  FAULT
 1    2  [1 2 -]  FAULT
 2    1  [1 2 -]  hit
 3    3  [1 2 3]  FAULT
 4    5  [1 2 5]  FAULT    out: 3
 5    1  [1 2 5]  hit
 6    2  [1 2 5]  hit
 7    4  [1 4 5]  FAULT    out: 2
 8    7  [1 4 7]  FAULT    out: 5
 9    1  [1 4 7]  hit
10    4  [1 4 7]  hit
11    7  [1 4 7]  hit
12    3  [3 4 7]  FAULT    out: 1
13    7  [3 4 7]  hit
14    4  [3 4 7]  hit
OPT: 7 page faults in 15 references

What to notice:

1. In FIFO, t = 4 and t = 5: it evicts page 1 and, right after, gcc asks for it again (out: 1 and then FAULT with page 1). That is the flaw of not looking at use.
2. In LRU, t = 5: hit with page 1. LRU kept it because it had been used at t = 2, later than page 2.
3. In the optimal, t = 5 and t = 6: two hits in a row, because at t = 4 it evicted page 3, which did not come back until t = 12.
4. All three start with the same 3 faults (t = 0, 1 and 3) and the same hit at t = 2: the frames are not full yet and there is no victim.
5. The totals, 11, 9 and 7, match what we counted in the traces: FIFO has 4 faults more than the optimal and LRU, 2.

The second simulator checks Belady’s anomaly with FIFO and works out gcc’s working set with Δ = 4:

# Belady's anomaly with FIFO and gcc's working set with a window Δ
from collections import deque

def fifo(n_frames, refs):
    frames, queue, marks = set(), deque(), ''   # queue: order of arrival in memory
    for p in refs:
        if p in frames:
            marks += '.'                         # hit
            continue
        marks += 'F'                             # page fault
        if len(frames) == n_frames:              # no free frame: the oldest leaves
            frames.discard(queue.popleft())
        frames.add(p)
        queue.append(p)
    return marks

BELADY = [3, 1, 4, 2, 3, 1, 5, 3, 1, 4, 2, 5]
for n in (3, 4):
    m = fifo(n, BELADY)
    print(f'FIFO, {n} frames: {" ".join(m)}  -> {m.count("F")} faults')

REFS = [1, 2, 1, 3, 5, 1, 2, 4, 7, 1, 4, 7, 3, 7, 4]   # gcc's string from the first simulator
DELTA = 4                                               # window: the last 4 references
print(f"\n{'t':>2}  {'ref':>3}  {'WS(t, Δ=4)':<12}  |WS|")
sizes = []
for t, p in enumerate(REFS):
    window = REFS[max(0, t - DELTA + 1):t + 1]       # references t-Δ+1 … t
    ws = sorted(set(window))                         # distinct pages = working set
    sizes.append(len(ws))
    print(f'{t:>2}  {p:>3}  {str(ws):<12}  {len(ws):>4}')

OTHERS = {'spotify': 3, 'campus': 4, 'onedrive': 2}  # |WS| of the other processes
FREE = 10                                            # frames left for the four
for t in (3, 9):
    D = sizes[t] + sum(OTHERS.values())
    print(f't = {t}: D = {sizes[t]} + 3 + 4 + 2 = {D} frames -> ' + ('fit' if D <= FREE else 'do NOT fit: thrashing'))

This time FIFO is programmed with a deque (double-ended queue) for the order of arrival: popleft() takes out the oldest in constant time and the set quickly answers “is it already in memory?”. For the working set, the window is a slice of the string, REFS[max(0, t - DELTA + 1):t + 1], and set removes repeats (the max avoids negative indices in the first instants). The output:

FIFO, 3 frames: F F F F F F F . . F F .  -> 9 faults
FIFO, 4 frames: F F F F . . F F F F F F  -> 10 faults

 t  ref  WS(t, Δ=4)    |WS|
 0    1  [1]              1
 1    2  [1, 2]           2
 2    1  [1, 2]           2
 3    3  [1, 2, 3]        3
 4    5  [1, 2, 3, 5]     4
 5    1  [1, 3, 5]        3
 6    2  [1, 2, 3, 5]     4
 7    4  [1, 2, 4, 5]     4
 8    7  [1, 2, 4, 7]     4
 9    1  [1, 2, 4, 7]     4
10    4  [1, 4, 7]        3
11    7  [1, 4, 7]        3
12    3  [1, 3, 4, 7]     4
13    7  [3, 4, 7]        3
14    4  [3, 4, 7]        3
t = 3: D = 3 + 3 + 4 + 2 = 12 frames -> do NOT fit: thrashing
t = 9: D = 4 + 3 + 4 + 2 = 13 frames -> do NOT fit: thrashing

What to notice:

1. The first two lines: 9 faults with 3 frames and 10 with 4. That is Belady’s anomaly, with data.
2. With 4 frames t = 4 and t = 5 hit (. .), but then six faults in a row follow: by not removing 3 and 1 earlier, it evicts them at a bad moment later.
3. In the table, t = 5: the window is 1, 3, 5, 1. Page 2 (asked for at t = 1) has already left and page 1 repeats, so |WS| drops from 4 to 3.
4. |WS| reaches 4 at t = 4, 6, 7, 8, 9 and 12, above gcc’s 3 frames.
5. The last two lines: even though gcc at t = 3 only needs 3 frames, D = 12 exceeds the 10 free ones. With all those processes inside, there is thrashing.

And to try your own reference strings, the Lab’s page replacement simulator traces FIFO, LRU and the optimal algorithm frame by frame and flags Belady’s anomaly.

Summary

Concept	Key idea
Virtual memory	the process does not have to be whole in RAM; the disk (swap) acts as an extension
Demand paging	a page is read from disk the first time it is asked for
Page fault	trap because of bit i: find, (victim), read, update and restart the instruction
M bit	dirty victim = 2 I/Os; clean = 1; precleaning
EAT	(1 − p) · access + p · fault service; p has to be tiny
FIFO / LRU / optimal	arrival / last use / next use: 11, 9 and 7 faults in the example
Belady’s anomaly	with FIFO, more frames can give more faults; LRU and the optimal do not suffer it
LRU approximations	clock, NRU, NFU, LFU, aging and WSClock, with the R bit and counters
Working set	distinct pages of the last Δ references; inside if clock − U ≤ Δ
Thrashing	Σ |WS| > frames: chained faults; avoided with the WS model, PFF or suspending processes

Three ideas to take away:

1. Virtual memory works thanks to locality: each process only needs a few pages at a time.
2. A replacement algorithm is good the more it resembles the optimal; LRU tries by looking at the past and its approximations make it cheap with the R bit.
3. If the working sets do not fit in RAM, no algorithm saves you: there is thrashing and the solution is to get processes out of the way.

Ready to check it? First, in the virtual memory guided practice we do the FIFO, LRU and optimal traces and the effective time with page faults step by step; then, in the exam-style virtual memory exercises you have a quiz with every exam format, FIFO, LRU and optimal traces with boxes that mark themselves, open questions and the cheat sheet. And after that comes the last topic of IC2: files.

Next step: practiceVirtual memory — practice with guided problems step by step: FIFO with its queue, LRU versus optimal, what a fault costs and an exercise in the exam format (and the LRU victim I picked by looking into the future)

Did this article help you? Here is how you can support SergioLearns →