FIFO vs Optimal Page Faults

Problem

Compare two page replacement policies on the same reference string with a fixed number of frames and return [fifo_faults, optimal_faults].

FIFO evicts the oldest loaded page, while the optimal policy evicts the page whose next use is farthest in the future, treating pages never used again as infinitely far. An empty reference string has zero faults.

Hint

The optimal victim is the resident page whose next occurrence is latest, or infinity.

Test cases

case 1

in: [[7,0,1,2,0,3,0,4,2,3,0,3,2,0,1,7,0,1],3]

expected: [12,9]

case 2

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

expected: [5,4]

case 3

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

expected: [1,1]

case 4

in: [[],3]

expected: [0,0]

case 5

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

expected: [2,2]

Starter codePython

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

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