Page replacement: FIFO, LRU, and optimal
With demand paging, a process's pages are loaded into physical memory frames only when they are used. When a page that is not in memory is accessed, a page fault occurs. If every frame is full, the operating system must choose a victim page to evict. The replacement policy decides which one.
Python
def fifo(refs, frames):
memory, faults = [], 0
for page in refs:
if page not in memory:
faults += 1
if len(memory) == frames:
memory.pop(0)
memory.append(page)
return faults
def lru(refs, frames):
memory, faults = [], 0
for page in refs:
if page in memory:
memory.remove(page)
else:
faults += 1
if len(memory) == frames:
memory.pop(0)
memory.append(page)
return faults
def optimal(refs, frames):
memory, faults = [], 0
for i, page in enumerate(refs):
if page in memory:
continue
faults += 1
if len(memory) == frames:
future = refs[i + 1:]
victim = max(memory, key=lambda p: future.index(p) if p in future else len(future) + 1)
memory.remove(victim)
memory.append(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(fifo(refs, 3), lru(refs, 3), optimal(refs, 3))
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo(belady, 3), fifo(belady, 4))