Join waitlist
Home › Community › Operating Systems
Operating SystemsCommunity question

Belady's anomaly - why not in LRU

Asked by Keerthana S 1 month ago 2 answers 6 votes

FIFO can have more page faults with more frames, fine. why can't that happen with LRU? book just says "stack algorithm" and nothing else

2 answers

Pranav Bhat1 month agoMost voted6

Stack algorithm means the pages in memory with N frames are always a subset of the pages with N+1 frames.

LRU keeps the N most recently used pages. With N+1 frames it keeps the N+1 most recently used, which includes those N. So anything that's a hit with N frames is also a hit with N+1.

FIFO depends on load order so that subset property doesn't hold.

Neha Joshi1 month ago4

try 1,2,3,4,1,2,5,1,2,3,4,5 with FIFO. 3 frames = 9 faults, 4 frames = 10

Related questions

Go deeper

Want the full explanation, not just an answer?

Structured lessons on DSA, core CS, Java and interview skills, each ending in a quiz so you know it stuck.

Browse the lessonsTry a mock interview