Page Replacement Optimal vs LRU Comparison

Problem

Compare the number of page faults produced by the optimal and LRU replacement policies.

pages is the reference string and capacity is the number of frames. Optimal (Belady) evicts the page whose next use is farthest in the future; LRU evicts the least recently used page.

Return [optimal_faults, lru_faults]. A non-positive capacity faults on every reference.

Hint

The optimal policy needs knowledge of future references, so it is only a benchmark.

Test cases

case 1

in: [[1,2,3,4,1,2,5,1,2,3,4,5],3]

expected: [7,10]

case 2

in: [[1,2,1],1]

expected: [3,3]

case 3

in: [[1,2,3],3]

expected: [3,3]

case 4

in: [[7],1]

expected: [1,1]

case 5

in: [[],2]

expected: [0,0]

Starter codePython

def page_fault_counts(pages, capacity):
    # Your code here
    pass

5 test cases · run your code against them in the editor