# Cache replacement policies

• In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs, and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.

The most common page replacement algorithms are FIFO, LRU, Optimal Page Replacement Algorithm.

Given a sequence 3, 4, 1, 0, 1, 7, 5, 3, 5,4, 8 and number of page slots as three what would be the number of page faults and resulting page stack for each of these three algorithms?

Explanation:

1. FIFO (First In First Out)
3 4 1 0 1 7 5 3 5 4 8
3 3 3 0 0 0 0 3 3 3 3
_ 4 4 4 4 7 7 7 7 4 4
_ _ 1 1 1 1 5 5 5 5 8
F F F F _ F F F_ F F = 9 page faults and [3, 4, 8] as final stack

2. LRU (Least Recently Used)
3 4 1 0 1 7 5 3 5 4 8
3 3 3 0 0 0 5 5 5 3 8
_ 4 4 4 4 7 7 7 7 4 4
_ _ 1 1 1 1 1 3 1 5 5
F F F F _ F F F_ F F = 9 page faults and [8, 4, 5] as final stack

3. Optimal Page Replacement (Look Ahead)
3 4 1 0 1 7 5 3 5 4 8
3 3 3 3 3 3 3 3 3 3 8
_ 4 4 0 0 7 7 7 7 4 4
_ _ 1 1 1 1 5 5 5 5 5
F F F F _F F _ _ F F = 8 page faults and [8, 4, 5] as final stack