Page Replacement: FIFO, LRU and Optimal
What an OS evicts when memory is full. FIFO, LRU and the optimal policy coded and compared on the classic reference string (15, 12 and 9 faults), plus Belady's anomaly and the loop that defeats LRU.
A page replacement algorithm chooses which resident page the OS evicts when memory is full and a page fault needs a frame. FIFO evicts the oldest page, LRU the least recently used, and optimal the page needed furthest in the future. Interviewers expect Belady's anomaly: FIFO can fault more with more frames, while LRU cannot.
When RAM is full and a page fault needs a frame, the OS must evict a page. FIFO evicts the oldest, LRU the least recently used, and the optimal policy the one needed furthest in the future, which is only usable as a yardstick. On the standard 20-reference string with 3 frames they fault 15, 12 and 9 times.
- On the standard 20-reference string with 3 frames from Silberschatz's operating systems text, FIFO faults 15 times, LRU 12 times and optimal 9 times.
- Belady's anomaly: on the string 1,2,3,4,1,2,5,1,2,3,4,5, FIFO faults rise from 9 to 10 when frames go from 3 to 4, while LRU falls from 10 to 8.
- LRU is a stack algorithm, where the pages held with n frames are always a subset of those held with n+1, so adding frames never increases its faults.
- Cycling through 4 pages with 3 frames for 40 references, both FIFO and LRU faulted on all 40, while the optimal policy faulted 16 times.
- The clock (second chance) algorithm approximates LRU with a hardware reference bit: a page with bit 1 gets it cleared and is skipped, a page with bit 0 is evicted.
01The decision
With virtual memory, a program only needs some of its pages in RAM at a time. When it touches a page that is not resident, a page fault occurs and the OS loads it from disk. If every frame is already in use, one resident page must be evicted first. If the evicted page is needed again soon, that causes another fault, and a disk read is millions of CPU cycles.
A page replacement algorithm chooses the victim. We judge algorithms by the number of page faults on a reference string, the sequence of page numbers a program touches. Fewer faults is better. The three below are the ones every course covers.
02The three policies in code
from collections import OrderedDict, deque
def fifo(refs, n):
q, s, faults = deque(), set(), 0
for r in refs:
if r not in s:
faults += 1
if len(q) == n: s.discard(q.popleft()) # evict the oldest loaded
q.append(r); s.add(r)
return faults
def lru(refs, n):
c, faults = OrderedDict(), 0
for r in refs:
if r in c: c.move_to_end(r) # mark as recently used
else:
faults += 1
if len(c) == n: c.popitem(last=False) # evict least recently used
c[r] = 1
return faults
def opt(refs, n):
mem, faults = [], 0
for i, r in enumerate(refs):
if r in mem: continue
faults += 1
if len(mem) < n: mem.append(r); continue
def next_use(m): # distance to next use
rest = refs[i + 1:]
return rest.index(m) if m in rest else float('inf')
mem[mem.index(max(mem, key=next_use))] = r # evict the furthest
return faultsFIFO needs only a queue. LRU needs to track recency on every access. Optimal needs to know the future, so it cannot be built, but it gives the lower bound to compare against.
03The textbook example
refs = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]
print(fifo(refs, 3), lru(refs, 3), opt(refs, 3)) # 15 12 9This is the reference string from Silberschatz's operating systems text and the counts match the book. FIFO faults 15 times, LRU 12 and optimal 9. LRU is closer to optimal because recent use is a decent predictor of future use (temporal locality). FIFO ignores usage: a page loaded early may be the hottest one in the program, and FIFO evicts it anyway.
04Belady's anomaly
b = [1,2,3,4,1,2,5,1,2,3,4,5]
print(fifo(b, 3), fifo(b, 4)) # 9 10
print(lru(b, 3), lru(b, 4)) # 10 8Giving FIFO a fourth frame raised faults from 9 to 10. This is Belady's anomaly. LRU does not do it: LRU with 4 frames faulted 8 times against 10 with 3. LRU belongs to the class of stack algorithms, where the set of pages held with n frames is always a subset of those held with n+1, so adding memory can never hurt. The anomaly depends on the particular reference string and is rare in practice, but it is a standard exam and interview question.
05Where LRU loses: sequential scans
loop = list(range(4)) * 10 # pages 0,1,2,3 repeated, 40 references
print(fifo(loop, 3), lru(loop, 3), opt(loop, 3)) # 40 40 16Cycling through 4 pages with 3 frames, both FIFO and LRU faulted on all 40 references. Each time the next page needed is exactly the one just evicted. Optimal faulted 16 times by keeping some pages pinned. Real systems see this when a program scans a file larger than memory, which can flush out everyone else's useful pages. This is why production kernels use variants that resist scans, such as keeping separate active and inactive lists in Linux.
06Skewed access: where LRU shines
import random
random.seed(2)
z = [min(int(random.paretovariate(1.2)), 50) for _ in range(5000)]
print(fifo(z, 10), lru(z, 10), opt(z, 10)) # 589 414 245On 5,000 references with a heavy skew toward a few pages (a Pareto distribution, which is only a stand-in for real workloads), FIFO faulted 589 times, LRU 414 and optimal 245. When access is skewed, tracking recency pays off, and LRU removes about 30% of FIFO's faults here.
07How real systems approximate LRU
True LRU would need the OS to update a timestamp or list on every memory reference, which hardware does not make visible. Real systems approximate. The common method is the clock algorithm (second chance): each page has a reference bit that the hardware sets when the page is used. Pages sit in a circle, and a pointer sweeps around. If the bit is 1, the pointer clears it and moves on. If it is 0, that page is the victim.
This gives most of LRU's benefit at almost no cost. Enhanced versions also consider a dirty bit, since evicting a modified page needs a write to disk first, so clean pages are cheaper victims.
08Common interview questions
Q: Which page replacement algorithm is best?
A: Optimal has the fewest faults but needs future knowledge. LRU is the best practical approximation when locality is strong.
Q: What is Belady's anomaly?
A: FIFO can produce more page faults when given more frames. Stack algorithms like LRU cannot.
Q: Why is LRU not used exactly?
A: Tracking exact recency on every access is too expensive. Systems use approximations like the clock algorithm.
Q: How does the clock algorithm work?
A: A pointer sweeps pages in a circle. A page with reference bit 1 gets the bit cleared and a second chance. A page with bit 0 is evicted.
Q: What workload hurts LRU?
A: A cyclic scan over more pages than fit in memory, which evicts each page just before it is needed.
Q: What is thrashing?
A: When memory is so over-committed that the system spends most of its time paging, not running programs.