Virtual memory and page replacement algorithms
50 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)"Count the page faults for this reference string with three frames" is the most repeated OS numerical. The interviewer is checking that you apply each replacement rule exactly and can explain why faults are so costly.
Virtual memory, demand paging and page faults
Demand paging loads a page into RAM only when the process first touches it; a page-table entry marked invalid sends the CPU to the OS as a page fault.
The program below shows how much a page fault slows memory: it computes the effective access time for four fault rates, with 200 ns memory and 8 ms to serve a fault.
Example 1 · How page faults slow down memory
mem = 200 # ns per memory accessfault = 8_000_000 # 8 ms per page fault, in nsfor p in (0.0, 0.000001, 0.0001, 0.001): eat = (1 - p) * mem + p * fault print(f"p = {p:.6f} -> EAT = {eat:.1f} ns ({eat / mem:.1f}x slower)")
# For at most 10% slowdown: (1 - p) * 200 + p * 8,000,000 <= 220max_p = (220 - mem) / (fault - mem)print(f"For under 10% slowdown, p must be below {max_p:.8f} (1 fault in {1 / max_p:.0f} accesses)")p = 0.000000 -> EAT = 200.0 ns (1.0x slower) p = 0.000001 -> EAT = 208.0 ns (1.0x slower) p = 0.000100 -> EAT = 1000.0 ns (5.0x slower) p = 0.001000 -> EAT = 8199.8 ns (41.0x slower) For under 10% slowdown, p must be below 0.00000250 (1 fault in 399990 accesses)
What this code does
- One fault in a thousand accesses makes memory about 41 times slower. A fault is 40,000 times as costly as a memory access here.
- To keep the slowdown under 10%, fewer than about 1 access in 400,000 may fault. That is why replacement policy matters so much.
Each page-table entry has a valid bit: valid means the page is in a frame, invalid means it is on disk (or not part of the process). Virtual memory lets a process use more memory than is physically free, by keeping only the pages it uses in RAM.
A fault costs milliseconds while a memory access costs nanoseconds, so even rare faults dominate: EAT = (1 − p) × memory time + p × fault time, where p is the fault rate.
Order of execution
Handle a page fault
Put the OS steps for one page fault in order.
FIFO on a worked reference string, and Belady's anomaly
Belady's anomaly is the effect that giving FIFO more frames can cause more page faults, not fewer.
The program below runs FIFO on the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with three and then four frames, and prints the queue after every reference.
Example 2 · FIFO and Belady's anomaly
def fifo(refs, frames, trace=False): queue, faults = [], 0 for page in refs: hit = page in queue if not hit: faults += 1 if len(queue) == frames: queue.pop(0) queue.append(page) if trace: print(f"ref {page}: {queue}" + ("" if hit else " fault")) return faults
refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]three = fifo(refs, 3, trace=True)print(f"FIFO, 3 frames: {three} faults")print(f"FIFO, 4 frames: {fifo(refs, 4)} faults")ref 1: [1] fault ref 2: [1, 2] fault ref 3: [1, 2, 3] fault ref 4: [2, 3, 4] fault ref 1: [3, 4, 1] fault ref 2: [4, 1, 2] fault ref 5: [1, 2, 5] fault ref 1: [1, 2, 5] ref 2: [1, 2, 5] ref 3: [2, 5, 3] fault ref 4: [5, 3, 4] fault ref 5: [5, 3, 4] FIFO, 3 frames: 9 faults FIFO, 4 frames: 10 faults
What this code does
- The queue is printed oldest-first, so the page on the left is the next victim. References to pages already in the queue are hits.
- Adding a fourth frame gives 10 faults instead of 9: Belady's anomaly. More memory made FIFO worse on this string.
A reference string is the sequence of page numbers a process touches. FIFO replacement throws out the page loaded earliest, using a simple queue, and ignores how recently or often a page is used.
On this string FIFO makes 9 faults with 3 frames but 10 with 4. LRU and Optimal never show this: they are stack algorithms, where the pages kept with n frames are always a subset of those kept with n + 1.
Predict the output
FIFO by hand
Follow the frames for a short string, 1 2 3 1 4 2, with 3 frames.
The code keeps the pages in load order, oldest first. What does it print?
Optimal and LRU on the same reference string
LRU (least recently used) replaces the page that has not been used for the longest time, using the past as a guess for the future.
The program below runs FIFO, LRU and Optimal on the classic string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames and prints the fault counts.
Example 3 · FIFO, LRU and Optimal on the classic string
def fifo(refs, frames): mem, faults = [], 0 for page in refs: if page in mem: continue faults += 1 if len(mem) == frames: mem.pop(0) # oldest loaded page out mem.append(page) return faults
def lru(refs, frames): mem, faults = [], 0 # front = least recently used for page in refs: if page in mem: # hit: move to the back mem.remove(page) mem.append(page) continue faults += 1 if len(mem) == frames: mem.pop(0) mem.append(page) return faults
def optimal(refs, frames): mem, faults = [], 0 for i, page in enumerate(refs): if page in mem: continue faults += 1 if len(mem) < frames: mem.append(page) continue rest = refs[i + 1:] next_use = lambda p: rest.index(p) if p in rest else len(refs) victim = max(range(len(mem)), key=lambda k: next_use(mem[k])) mem[victim] = page return faults
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]print("20 references, 3 frames")print("FIFO faults: ", fifo(refs, 3))print("LRU faults: ", lru(refs, 3))print("Optimal faults:", optimal(refs, 3))20 references, 3 frames FIFO faults: 15 LRU faults: 12 Optimal faults: 9
What this code does
lrukeeps pages in order of last use: a hit moves the page to the back, so the front is always the least recently used.optimallooks ahead for each page's next use and evicts the one used furthest away or never.- 15, 12 and 9 faults: Optimal is the lower bound, and LRU gets much of the way there using only the past.
Optimal (OPT or MIN) replaces the page that will not be used for the longest time in the future. It gives the fewest possible faults but needs the future, so it is only a yardstick. FIFO makes 15 faults, LRU 12 and Optimal 9.
Exact LRU needs hardware support on every access, so real systems use approximations such as the clock (second-chance) algorithm with a reference bit. Hit ratio = hits ÷ references: with 20 references and 12 faults, 8 hits give 40%.
Predict the output
Who is the victim?
Three frames hold pages 7, 0 and 1. A new page needs a frame.
Round 1 of 2
LRU: the pages are listed oldest use first. Page 7 is used again. Which page is evicted?
Thrashing and the working set
Thrashing is when a process or the whole system spends more time paging than executing, because it has fewer frames than the pages it actively uses.
The program below computes the working set, the distinct pages used in the last 10 references, at three moments of one process, and checks whether two processes fit in 6 frames.
Example 4 · Computing a working set
def working_set(refs, t, window): return sorted(set(refs[max(0, t - window):t]))
refs = [2, 6, 1, 5, 7, 7, 7, 7, 5, 1, 6, 2, 3, 4, 1, 2, 3, 4, 4, 4, 3, 4, 3, 4, 4, 4, 1, 3, 2, 3, 4, 4, 4, 3, 4, 4, 4]window = 10for t in (10, 26, 37): ws = working_set(refs, t, window) print(f"After reference {t}: WS = {ws}, size {len(ws)}")frames = 6demand = len(working_set(refs, 10, window)) + len(working_set(refs, 26, window))verdict = "thrashing risk" if demand > frames else "fits"print(f"Two processes in these phases need {demand} frames; {verdict} with {frames} frames")After reference 10: WS = [1, 2, 5, 6, 7], size 5 After reference 26: WS = [3, 4], size 2 After reference 37: WS = [2, 3, 4], size 3 Two processes in these phases need 7 frames; thrashing risk with 6 frames
What this code does
- The working set is the distinct pages in the last 10 references. Early on the process uses five pages; later it settles into a loop over pages 3 and 4.
- The OS adds the working-set sizes of all processes. If the total exceeds the free frames, it suspends a process instead of letting all of them thrash.
Thrashing makes CPU utilisation drop, a naive scheduler then admits more processes, each gets even fewer frames, and things get worse.
- Cause: total working sets are larger than the available frames.
- Symptom: a very busy paging disk and low CPU utilisation.
- Fixes: fewer processes, more RAM, or working-set or page-fault-frequency control.
- Locality: programs use a small set of pages for a while, then move on; the working set tracks that set.
The working set is the set of distinct pages used in the last Δ references. If the sum of all working-set sizes exceeds the available frames, the OS should suspend a process. Page-fault frequency control gives a process more frames when its fault rate is too high and takes frames away when it is very low.
Find the bug
Diagnose the slowdown
Each diagnosis has one wrong line. Click it.
CPU use is 5% and the paging disk is 98% busy.
Round 1 of 2Counting page faults with exact answers
Page fault is the trap raised when a process touches a page that is not in RAM; the OS loads the page from disk and restarts the instruction.
Counting page faults by hand is a table: one column per reference and one row per frame, with an F where a fault happens. The table below is FIFO on a classic string; the program after it checks every algorithm.
String 1 2 3 4 1 2 5 1 2 3 4 5, FIFO, 3 frames:ref: 1 2 3 4 1 2 5 1 2 3 4 5f1: 1 1 1 4 4 4 5 5 5 5 5 5f2: 2 2 2 1 1 1 1 1 3 3 3f3: 3 3 3 2 2 2 2 2 4 4 F F F F F F F . . F F . -> 9 faultsExample 5 · Fault counts for every algorithm and frame count
def fifo(refs, frames): mem, faults = [], 0 for page in refs: if page in mem: continue faults += 1 if len(mem) == frames: mem.pop(0) # oldest loaded page out mem.append(page) return faults
def lru(refs, frames): mem, faults = [], 0 # front = least recently used for page in refs: if page in mem: # hit: move to the back mem.remove(page) mem.append(page) continue faults += 1 if len(mem) == frames: mem.pop(0) mem.append(page) return faults
def optimal(refs, frames): mem, faults = [], 0 for i, page in enumerate(refs): if page in mem: continue faults += 1 if len(mem) < frames: mem.append(page) continue rest = refs[i + 1:] next_use = lambda p: rest.index(p) if p in rest else len(refs) victim = max(range(len(mem)), key=lambda k: next_use(mem[k])) mem[victim] = page return faults
strings = [[7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1], [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]]names = ["Classic (20 refs)", "Belady (12 refs)"]for refs, name in zip(strings, names): print(name) for f in (3, 4): print(f" {f} frames: FIFO {fifo(refs, f)}, LRU {lru(refs, f)}, OPT {optimal(refs, f)}")Classic (20 refs) 3 frames: FIFO 15, LRU 12, OPT 9 4 frames: FIFO 10, LRU 8, OPT 8 Belady (12 refs) 3 frames: FIFO 9, LRU 10, OPT 7 4 frames: FIFO 10, LRU 8, OPT 6
What this code does
- Only FIFO on the Belady string gets worse with more frames (9 → 10). LRU and OPT never increase when frames are added.
- Use this table to check your hand counts: the classic string with 3 frames gives 15, 12 and 9.
Fill the frames left to right at the start; the first n distinct pages are always faults (compulsory or cold misses). For each later fault apply the rule: FIFO removes the oldest loaded page, LRU the page whose last use is furthest back, Optimal the page whose next use is furthest ahead (or never). Faults + hits always equals the number of references.
Predict the output
Count the LRU faults
Two frames, LRU, string 3 2 3 1 2 4. Pick the fault count.
The code keeps the pages in order of use, oldest first.
Next step
Check your understanding
12 quick questions