Virtual 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)
In the IC2 practice exam I got a page replacement question with LRU. I was going fast, filling in the grid, until at one fault I hesitated over whom to evict. I looked at the string, saw that page 5 did not come back for a good while and threw it out. I got 6 faults and was delighted. When it was marked: 8. I had done optimal, not LRU. LRU does not look at what is coming: it looks at what has already happened and evicts the page that has gone longest without being used. Since then, when I hesitate, I say under my breath: «FIFO looks at arrival, LRU at last use, optimal at next use».
This is the guided practice for virtual memory. In the virtual memory theory you saw demand paging, the page fault, the replacement algorithms, Belady’s anomaly and the working set, with gcc and its three frames. Here we solve four problems step by step: FIFO with its queue, LRU and optimal with the same string, the effective access time with faults and an exercise in the exam format. Afterwards, in the virtual memory exercises, it is your turn.
Table of Contents
Before you start
It helps to be clear about:
- What a page fault is and that the first three faults with three empty frames are compulsory (there is nobody to evict).
- What each algorithm looks at to choose the victim: FIFO, the one that came in first; LRU, the one that has gone longest without being used; optimal, the one that will be used latest (or never).
- The formula for the effective access time: .
- What Belady’s anomaly is and that only FIFO suffers from it.
If any of them sounds shaky, go over the theory before carrying on.
On paper, draw a grid with one column per reference and one row per frame, plus an extra row at the bottom to mark F (fault) or a dot (hit). Each new page takes its victim’s frame: do not move the others.
How to solve a replacement problem
The four problems follow the same four-step method:
- Write down the reference string, the number of frames and the algorithm.
- For each reference, first ask whether it is in memory. If it is, a hit (and in LRU, note that it has just been used). If not, a fault.
- On each fault with the frames full, choose the victim with the algorithm’s criterion and write it under the column.
- Count and check: faults + hits = length of the string; the first compulsory faults are as many as the frames; optimal cannot give more faults than LRU or FIFO.
Problem 1: FIFO with its queue
Statement. A process has 3 frames and generates the reference string 1, 4, 5, 3, 1, 4, 2, 1, 4, 5, 1, 4. Apply FIFO, give the victims and count the faults.
The idea
FIFO behaves like a queue: when someone has to go, the one that came in first leaves, even if it was used a moment ago. A hit does not change anything in the queue. So as not to slip, keep the arrival queue written next to the grid.
Step by step
| Asks | In memory? | Arrival queue (first one leaves) | Victim |
|---|---|---|---|
| 1 | no | 1 | — (compulsory) |
| 4 | no | 1, 4 | — (compulsory) |
| 5 | no | 1, 4, 5 | — (compulsory) |
| 3 | no | 4, 5, 3 | 1 |
| 1 | no | 5, 3, 1 | 4 |
| 4 | no | 3, 1, 4 | 5 |
| 2 | no | 1, 4, 2 | 3 |
| 1 | yes | 1, 4, 2 | — |
| 4 | yes | 1, 4, 2 | — |
| 5 | no | 4, 2, 5 | 1 |
| 1 | no | 2, 5, 1 | 4 |
| 4 | no | 5, 1, 4 | 2 |
10 faults and 2 hits. Victims: 1, 4, 5, 3, 1, 4 and 2.
Check
- 10 + 2 = 12 references.
- The first three faults are compulsory: the three frames start empty.
- At the fifth reference of the string (the 1), FIFO evicts 4, which had been asked for very recently: that is exactly what FIFO does badly, and why it gives so many faults.
Questions you might ask
Why does a hit not change FIFO’s queue? Because FIFO only looks at when each page came in. Being used again does not «rejuvenate» it; that is what LRU does.
Would there be fewer faults with 4 frames? With this string, yes: 8. But with FIFO it is not guaranteed: there are strings where more frames give more faults. That is Belady’s anomaly.
Why do compulsory faults count as faults? Because the page was not in memory and had to be brought from disk. Having no victim does not make it free.
Moving the page that was hit to the end of the queue in FIFO. That is LRU. In FIFO, hits do not touch the queue.
Try it yourself
- Repeat FIFO with 4 frames and check that you get 8 faults.
- Which reference in the string would you have to change for FIFO to hit once more?
Problem 2: LRU versus optimal
Statement. With the same string and 3 frames, apply LRU and the optimal algorithm. Compare the faults of the three algorithms.
The idea
At each fault they look at different things: LRU looks backwards (which one have I not asked for in the longest time?) and optimal looks forwards (which one will I ask for latest, or never?). With the string written in front of you, for LRU you search to the left of the current reference and for optimal, to the right.
Step by step
LRU. We keep the pages in memory ordered from least to most recent (the first one is the victim):
| Asks | In memory? | Order of use (first = victim) | Victim |
|---|---|---|---|
| 1, 4, 5 | no | 1, 4, 5 | — (compulsory) |
| 3 | no | 4, 5, 3 | 1 |
| 1 | no | 5, 3, 1 | 4 |
| 4 | no | 3, 1, 4 | 5 |
| 2 | no | 1, 4, 2 | 3 |
| 1 | yes | 4, 2, 1 | — |
| 4 | yes | 2, 1, 4 | — |
| 5 | no | 1, 4, 5 | 2 |
| 1 | yes | 4, 5, 1 | — |
| 4 | yes | 5, 1, 4 | — |
8 faults. The difference with FIFO is at reference 10 (the 5): LRU evicts 2, which has not been used for a while, whereas FIFO evicted 1, which had just been used.
Optimal. At each fault with the frames full, we look at the string that is left from that point and evict the page that will be asked for latest (or never):
| Fault at | Frames | What is left of the string | Next use | Victim |
|---|---|---|---|---|
| the 3 (ref. 4) | 1, 4, 5 | 1, 4, 2, 1, 4, 5, 1, 4 | 1 straight away, 4 after, 5 much later | 5 |
| the 2 (ref. 7) | 1, 4, 3 | 1, 4, 5, 1, 4 | 1 and 4 straight away, 3 never | 3 |
| the 5 (ref. 10) | 1, 4, 2 | 1, 4 | 1 and 4 straight away, 2 never | 2 |
In between, everything is a hit: references 5 and 6 (1 and 4), 8 and 9 (1 and 4) and 11 and 12 (1 and 4). 6 faults: 3 compulsory and only 3 replacements.
| Algorithm | Faults | Hits | Victims |
|---|---|---|---|
| FIFO | 10 | 2 | 1, 4, 5, 3, 1, 4, 2 |
| LRU | 8 | 4 | 1, 4, 5, 3, 2 |
| Optimal | 6 | 6 | 5, 3, 2 |
Check
- 6 ≤ 8 ≤ 10: optimal is the minimum possible with 3 frames; if another algorithm gave you fewer, your optimal would be wrong.
- All three have 3 compulsory faults.
- Each optimal victim is a page asked for later than the other two (or never): check it column by column in the grid.
Questions you might ask
What if two pages are never asked for again? It makes no difference to the number of faults; to make the grid unique, break the tie with FIFO (the one that came in first leaves). Write it down if it happens in the exam.
If optimal is the best, why is it not used? Because it needs to know the future. It serves as a reference to measure how close a real algorithm gets.
Why does LRU resemble optimal? Because of locality: what has not been used for a long time will probably take a while to be used again. It is using the past as a prediction of the future.
How is LRU kept in practice? With counters or a stack of pages, which is expensive. That is why systems use approximations with the reference bit (the clock, NRU, aging).
In LRU, choosing the victim by looking forwards in the string. That is optimal. LRU only looks backwards.
Try it yourself
- Apply LRU with 4 frames. Does it improve like FIFO?
- Change the last reference (the 4) to a 3. Does any optimal fault change?
Problem 3: what a page fault costs
Statement. Memory takes 100 ns and serving a page fault, 8 ms. a) Work out the effective access time with a fault probability and . b) What maximum keeps the effective time within 110 ns (10 % slower)?
The idea
It is the same weighted mean as with the TLB, but with very uneven numbers: a fault costs 8 ms = 8,000,000 ns, eighty thousand times one access. Everything has to be in the same unit before multiplying.
Step by step
a)
b) Solve for :
One fault every 800,000 accesses, at most.
Check
- With you get 100 ns and with , 8 ms: both results lie between those extremes.
- looks small, but the EAT is multiplied by 81. If you get a «reasonable» number with that , check the units.
Questions you might ask
Why does a fault take milliseconds? Because the page has to be read from disk (and, if the victim is modified, written first). The CPU and RAM work in nanoseconds; the disk, in milliseconds.
Does anything change if half the victims are dirty? Yes: those cost two disk operations (writing the victim and reading the new page), so the mean fault service time goes up and so does the EAT. That is why the M bit exists.
How do you get such a small ? Through locality: programs work at each moment with few pages (their working set), and if those fit in their frames there are hardly any faults.
Mixing milliseconds and nanoseconds in the formula (putting 8 instead of 8,000,000). Always convert everything to the same unit before multiplying.
Try it yourself
- Work out the EAT with .
- Repeat part b) to stay within 200 ns.
Problem 4: an exercise in the exam format
In the written part and the test calculations of IC2 a page replacement question is almost certain: a string, a number of frames and one or several algorithms, with the faults and the fault rate. The full grid and the victims are marked. This exercise is original and written in that format.
Exercise. With 3 frames initially empty and the string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3: a) apply FIFO and LRU and draw the grid; b) give for each the number of faults and the fault rate; c) which one behaves better with this string and why?
| Algorithm | Faults | Fault rate |
|---|---|---|
| FIFO | ___ | ___ |
| LRU | ___ | ___ |
The idea
Two grids with the same string: do one completely before starting the other. The difference between FIFO and LRU will appear when a page that has just been used is the oldest to have arrived.
Step by step
FIFO (arrival queue, the first one leaves):
| Asks | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fault? | F | F | F | F | · | F | F | F | F | F | F | · |
| Victim | 7 | 0 | 1 | 2 | 3 | 0 | 4 |
LRU (the one gone longest without use leaves):
| Asks | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fault? | F | F | F | F | · | F | · | F | F | F | F | · |
| Victim | 7 | 1 | 2 | 3 | 0 | 4 |
| Algorithm | Faults | Fault rate |
|---|---|---|
| FIFO | 10 | 10 / 12 = 83.3 % |
| LRU | 9 | 9 / 12 = 75 % |
c) LRU is better with this string. The difference is at reference 6 (the 3): FIFO evicts 0, the first to have arrived of those left but just used; LRU evicts 1, which had gone longer without use. That is why at reference 7 (the 0 again) LRU hits and FIFO faults.
Check and how it is marked
- Faults + hits = 12 in both grids (10 + 2 and 9 + 3).
- Each FIFO victim is the first in the arrival queue at that moment; each LRU victim, the one used longest ago. Check it in two or three random columns.
Marking values the full grid (with the contents of the frames, not just the Fs), the victims, the fault rate as a fraction and the reason in part c), which must point to the reference where the algorithms part ways.
Giving only the number of faults without the grid. If one fault is wrong, without a grid there is nothing to mark.
Try it yourself
- Apply optimal to the same string. How many faults does it give?
- How many faults does FIFO give with 4 frames? Is there a Belady anomaly?
Common mistakes in this practice
- Moving the page that was hit in FIFO: hits do not change the arrival queue.
- Looking forwards in LRU: that is optimal; LRU looks at the past.
- Deciding optimal out of order: each victim is chosen at its fault, with the string left from there.
- Forgetting the compulsory faults of the first empty frames.
- Mixing units in the effective access time.
- Giving the result without a grid, or without checking faults + hits.
Check it with Python
This program applies FIFO, LRU and optimal to the strings of Problems 1, 2 and 4, prints the trace of FIFO and LRU and computes the effective access time. Do it by hand first.
# Virtual memory on paper: FIFO, LRU and optimal with a frame trace, and effective access time.
def replace(refs, nframes, alg):
frames, faults, rows = [], 0, []
for i, p in enumerate(refs):
if p in frames:
rows.append((p, list(frames), "hit", ""));
if alg == "LRU": frames.remove(p); frames.append(p) # LRU: it becomes the most recent
continue
faults += 1; victim = ""
if len(frames) == nframes:
if alg == "OPT": # the one to be used latest (or never)
future = refs[i + 1:]
victim = max(frames, key=lambda m: future.index(m) if m in future else len(future) + 1)
else: victim = frames[0] # FIFO: the oldest; LRU: the least recent
frames.remove(victim)
frames.append(p); rows.append((p, list(frames), "fault", victim))
return faults, rows
refs = [1, 4, 5, 3, 1, 4, 2, 1, 4, 5, 1, 4]
for alg in ("FIFO", "LRU", "OPT"):
f, rows = replace(refs, 3, alg)
print(f"{alg}: {f} faults, {len(refs) - f} hits; victims:", " ".join(str(v) for _, _, e, v in rows if v != ""))
if alg in ("FIFO", "LRU"):
for p, m, e, v in rows: print(f" asks {p}: frames {m} {e}{' (out ' + str(v) + ')' if v != '' else ''}")
ex = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3]
for alg in ("FIFO", "LRU"):
f, _ = replace(ex, 3, alg); print(f"exam {alg}: {f} faults, rate {f}/{len(ex)} = {f / len(ex):.2%}")
for m in (3, 4):
print(f"FIFO with {m} frames:", replace(refs, m, "FIFO")[0], "faults")
acc, serv = 100, 8_000_000 # ns: memory access and fault service (8 ms)
for p in (0.001, 0.00001):
print(f"TEA p={p}: {(1 - p) * acc + p * serv:.1f} ns")
print("maximum p to stay within 110 ns:", (110 - acc) / (serv - acc))
Output (run once):
FIFO: 10 faults, 2 hits; victims: 1 4 5 3 1 4 2 asks 1: frames [1] fault asks 4: frames [1, 4] fault asks 5: frames [1, 4, 5] fault asks 3: frames [4, 5, 3] fault (out 1) asks 1: frames [5, 3, 1] fault (out 4) asks 4: frames [3, 1, 4] fault (out 5) asks 2: frames [1, 4, 2] fault (out 3) asks 1: frames [1, 4, 2] hit asks 4: frames [1, 4, 2] hit asks 5: frames [4, 2, 5] fault (out 1) asks 1: frames [2, 5, 1] fault (out 4) asks 4: frames [5, 1, 4] fault (out 2) LRU: 8 faults, 4 hits; victims: 1 4 5 3 2 asks 1: frames [1] fault asks 4: frames [1, 4] fault asks 5: frames [1, 4, 5] fault asks 3: frames [4, 5, 3] fault (out 1) asks 1: frames [5, 3, 1] fault (out 4) asks 4: frames [3, 1, 4] fault (out 5) asks 2: frames [1, 4, 2] fault (out 3) asks 1: frames [1, 4, 2] hit asks 4: frames [4, 2, 1] hit asks 5: frames [1, 4, 5] fault (out 2) asks 1: frames [1, 4, 5] hit asks 4: frames [4, 5, 1] hit OPT: 6 faults, 6 hits; victims: 5 3 2 exam FIFO: 10 faults, rate 10/12 = 83.33% exam LRU: 9 faults, rate 9/12 = 75.00% FIFO with 3 frames: 10 faults FIFO with 4 frames: 8 faults TEA p=0.001: 8099.9 ns TEA p=1e-05: 180.0 ns maximum p to stay within 110 ns: 1.250015625195315e-06
Things to notice:
- In LRU, a hit does
frames.remove(p); frames.append(p): the page becomes the most recent. In FIFO hits do not touch the list: that is the whole difference between the two. - Optimal chooses with
future.index(m), the next use; if a page never appears again, it gets a value larger than any index and leaves first. - The LRU trace writes the frames from least to most recent, which is why the order also changes on hits.
- The maximum p, 1.25 · 10⁻⁶, comes from solving the same EAT formula.
To try your own strings, there is the page replacement simulator in the Lab, with FIFO, LRU and optimal.
Summary
- FIFO looks at arrival, LRU at last use and optimal at next use.
- The first faults with empty frames are compulsory and they count.
- Optimal always gives the minimum number of faults; between FIFO and LRU, LRU usually wins, but not always.
- EAT = (1 − p) · access + p · service, all in the same unit; p must be tiny.
- With FIFO, more frames can give more faults (Belady); with LRU and optimal, not.
- In the exam, full grid, victims and fault rate as a fraction.
Checklist: have you practised it?
- Have you done the four problems on paper before reading the step by step?
- Do you know what each algorithm looks at to choose the victim?
- Can you do the LRU grid without confusing it with optimal?
- Can you compute the EAT and solve for the maximum p?
- Have you checked the problems with the Python program or the simulator?
- Have you tried the «Try it yourself» tasks without looking at the theory?
If you answered yes to almost everything, you are ready for the virtual memory exercises, with a test on the whole topic, traces and calculations with boxes that mark themselves. See you there!
Next step: exercisesVirtual memory — exam-style exercises with page faults, FIFO, LRU and optimal traces and working sets (and the three faults I did not count in the mock exam)Did this article help you? Here is how you can support SergioLearns →
