.. _page_replace:

Page Replacement Algoritms
----------------------------

* When there is a page fault, the referenced page must be loaded.

* If there is no available frame in memory, then one page is selected for
  replacement

* If the selected page has been modified, it must be copied back to disk
  (swapped out)

* A page replacement algorithm is said to satisfy the inclusion  property or
  is called a **stack  algorithm** if the set of pages in a k-frame memory
  is always a subset of the pages in a (k + 1) frame memory.


Static Replacement Algorithms
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The static paging algorithms implement the replacement policy when the frame
allocation to a process is fixed. 

First-In-First-Out (FIFO) Replacement 
""""""""""""""""""""""""""""""""""""""

On a page fault, the frame that has been in memory the longest is replaced.

.. figure:: fifo.png
   :align: center

--------------------

FIFO is not a stack algorithm.  In certain cases, the number of page faults
can actually increase when more frames are allocated to the process. In the
example below, there are 9 page faults for 3 frames and 10 page faults
for 4 frames.

.. figure:: stack_fail.png
   :align: center


Optimal Replacement
""""""""""""""""""""""""""""""""""""""

The Belady's optimal algorithm cheats.  It looks forward in time to see which
frame to replace on a page fault.  Thus it is not a real replacement
algorithm. It gives us a frame of reference for a given static frame access
sequence.

.. figure:: optimal.png
   :align: center

Least Recently Used (LRU) Replacement
""""""""""""""""""""""""""""""""""""""

On a page fault, the frame that was least recently used in replaced.

.. figure:: lru.png
   :align: center


LRU Approximation
^^^^^^^^^^^^^^^^^^^^^


Pages with a current copy on disk are first choice for pages to be removed
when more memory is needed.  To facilitate :ref:`page_replace`, a table of
valid or invalid bits (also called *dirty bits*) is maintained.


.. figure:: dirty_bit.png
   :align: center

* With each page table entry a valid-invalid bit is associated:

  * 1 (in-memory)

  * 0 (not-in-memory)

* Initially valid-invalid but is set to 0 on all entries.

* In idle times, dirty frame are copied to disk.

* Additional **Reference Bit**: whether the frame was recently referenced.

    The reference bits are refreshed on a periodic basis