Proof for optimal page replacement (OPT)

Question

I need prove that the optimal page replacement algorithm is indeed optimal, and I'm not sure exactly how to start. I thought maybe proof by contradiction, but once I formulated an alternative claim, I wasn't sure how to show that it would have equal or less page faults than OPT.

Answer 1

Is this for CSE 330 final tomorrow?

Answer 2

Longest Forward Distance (LFD)

• Replace the page whose next request is farthest (in the future)

Theorem:

• LFD (longest forward distance) is an optimal alg.

Proof:

• For contradiction, assume that LFD is not optimal
• Then there exists a finite input sequence α on which LFD is not optimal (assume that the length of α is | α| = n)
• Let OPT be an optimal solution for α such that

– OPT processes requests 1,2, …, i in the same way as LFD

– OPT processes request i+1 differently than LFD

– Any other optimal strategy processes one of the first i+1 requests differently than LDF

• Hence, OPT is the optimal solution that behaves in the same way as LFD for as long as possible --> we have i < n

• Goal: Construct OPT′ that is identical with LFD for req. 1, … , i+1

Case 1: Request i+1 does not lead to a page fault

• LFD does not change the content of the fast memory

• OPT behaves differently than LFD --> OPT replaces some page in the fast memory

– As up to request i+1, both algorithms behave in the same way, they also have the same fast memory content

– OPT therefore does not require the new page for request i+1

– Hence, OPT can also load that page later (without extra cost) --> OPT′

Case 2: Request i+1 does lead to a page fault

• LFD and OPT move the same page into the fast memory, but they evict different pages

– If OPT loads more than one page, all pages that are not required for request i+1 can also be loaded later

• Say, LFD evicts page p and OPT evicts page p’

• By the definition of LFD, p’ is required again before page p

Now, there are 2 cases:-

a) OPT keeps p in fast memory until request ℓ

– OPT could evict p at request i+1, keeping p′ instead and load p (instead of p′) back into the fast memory at request ℓ, at no extra cost, similar to LFD

b) OPT evicts p at request ℓ’ < ℓ

– OPT could evict p at request i+1, keeping p′ instead and load p while evicting p′ at request ℓ’ (switch evictions of p and p′),again, similar to LFD

ergo, OPT is not a better solution than LFD.

ie, LFD is the Optimum Page replacement Technique.

LFD is also called as Optimum Page replacement Technique(OPT).

PS: in the proof, a name 'OPT' is used just as a 'name', not be confused it as Optimum Page replacement Technique.