UNISA Chatter – Operating System Concepts: Part 16 ... Page Replacement revisited

  • Article

See UNISA – Summary of 2010 Posts for a list of related UNISA posts.

This is one of the final exam preparation posts and looks at some of the common deadlock avoidance approach algorithms and reviews the associated assignment from this year as an example. If you are not studying at UNISA, you should probably skip this post Smile

We covered three main algorithms, namely:

  • FIFO … First-in-first-out, which picks the oldest page as the victim, similar to a queue.
  • LRU … Least-recently-used, which picks the page that has not been used for the longest period of time as the victim.
  • MFU … Most frequently used algorithm picks the page with the lowest usage count as the next victim. Two special cases exist for the LRU:
      • Second chance … pick a page as a victim on the second strike only.
      • Enhance second chance … base the victim selection on both the recently used and dirty (modified) state.
  • Optimal … The crystal ball algorithm where the intention is to find the optimal page replacement strategy to minimise the page faults. For this algorithm we effectively have to look into the future, which is not always a possible feature.

Test data presented in our assignment 2, additional examples:

  1. Sequence of memory references is 10,11,104,170,73,309,185,245,246,123,320
  2. 380 word program
  3. Page size is 50 words

Some facts we can feed into Excel:

  • 380/50 = 7 pages and 60% of page 8
  • Internal fragmentation is therefore 40% or 20 words
  • Pages 0 – 7 are split up into 50 word pages as shown below on the first table
  • The sequence of memory references result in page access 0,0,2,3,1,6,3,4,4,2,6 which can be simplified to 0,2,3,1,6,3,4,2,6
  • Taking three examples as shown with the red arrows:
    •   10 –> page 0
    • 309 –> page 6
    • 185 –> page 3

The FIFI, LRU and Optimal algorithms result in page faults (shown in red) and page replacement as shown. The most efficient, as expected, is the Optimal algorithm, followed by FIFO.

Hope this helps … from now until Wednesday it will be a matter of re-absorbing all the theory.