Understanding LRU Competitiveness Theorem

The Lemma states that if a page is ejected by the LRU algorithm after being touched in a request sequence, there is a fault in the offline algorithm. The Theorem extends this to show that for any segment where LRU incurs k faults, the offline algorithm also has a fault. The proof involves examining different cases of page ejections and cache entries, ultimately proving LRU's k-competitiveness.

• LRU
• Competitiveness Theorem
• Algorithm
• Offline
• Page Ejection

barajas_m Follow

Uploaded on Nov 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. LRU is k-competitive

2. Lemma Consider a sequence of requests. LRU ejects P P . . . . . . Lemma: In any request sequence, if P is touched and the at some point later LRU ejects P, then even the offline algorithm has a fault between the time P is touched and when it is ejected.

3. Lemma Proof: If P is rejected by the LRU, it means right now there are in the cache k-1 pages that were accessed after P was accessed, and a new page is now being accessed together k+1. By the pigeonhole principle, even the offline algorithm will need to eject someone in this subsequence.

4. Theorem Theorem: For any sequence segment where LRU has k faults, the offline algorithm has a fault. Proof: Consider the sequence of requests: P k LRU faults subsequence

5. Cases: 1. P ejected in subsequence . P ejected by LRU P In this case, by lemma, there is one fault by offline algorithm.

6. Cases: 2. There exist a Q in , that is ejected twice. Q Q ejected by LRU P This means that between the first and second ejection Q had to enter the cache. In this case, by lemma, there is one fault by offline algorithm.

7. Cases: 3. P is not ejected in , and no one is ejected twice. P It means: Entering , there are k-1 pages other than P and P. k different pages are ejected, but not P. Therefore, there has to be a page that entered the cache in and was ejected by LRU in . By lemma, there is one fault by offline algorithm.

8. Conclude Every subsequence where LRU has k faults, necessarily has at least one fault by the offline algorithm. Therefore: LRU is k-competitive.