Cache replacement policies


  • 0
    L

    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

    Additional ref: GeeksForGeeks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.