Topic - Page Replacement algorithm

Question

Consider the following page address trace generated by a cache main memory scheme and has a cache capacity of four pages:

1,6, 4,5, 1, 4, 3, 2, 1, 2, 1, 4, 6, 7, 4

Assuming the cache initially has pages 1, 2, 3, and 4, show the cache trace using the LRU (Least Recently Used) policy and FIFO (First In First Out) replacement. Contrast this with all necessary steps.

Answer 1

Page Accessed LRU Cache  FIFO Cache

1                       $[2, 3, 4, 1]$    $[1, 2, 3, 4]$
6                       $[3, 4, 1, 6]$    $[2, 3, 4, 6]$
4                       $[3, 1, 6, 4]$    $[2, 3, 4, 6]$
5                       $[1, 6, 4, 5]$    $[3, 4, 6, 5]$
1                       $[6, 4, 5, 1]$    $[4, 6, 5, 1]$
4                       $[6, 5, 1, 4]$    $[4, 6, 5, 1]$
3                       $[5, 1, 4, 3]$    $[6, 5, 1, 3]$
2                       $[1, 4, 3, 2]$    $[5, 1, 3, 2]$
1                       $[4, 3, 2, 1]$    $[5, 1, 3, 2]$
2                       $[4, 3, 1, 2]$    $[5, 1, 3, 2]$
1                       $[4, 3, 2, 1]$    $[5, 1, 3, 2]$
4                       $[3, 2, 1, 4]$    $[1, 3, 2, 4]$
6                       $[2, 1, 4, 6]$    $[3, 2, 4, 6]$
7                       $[1, 4, 6, 7]$    $[2, 4, 6, 7]$
4                       $[1, 6, 7, 4]$    $[2, 4, 6, 7]$