PAGE REPLACEMENT

• When a page fault occurs, the OS loads the faulted page from disk into a page frame of memory
•  At some point, the process has used all of the page frames it is allowed to use

          -This is likely less than all of available memory

• When this happens, the OS must replace a page for each page faulted in

        - It must evict a page to free up a page frame

• The page replacement algorithm determines how this is done

          -And they come in all shapes and size

PAGE REPLACEMENT ALGORITHMS
BASIC SCHEME:

• The goal of the replacement algorithm is to reduce the fault rate by selecting the best victim page to remove
•  The best page to evict is the one never touched again

            - Will never fault on it

• Never is a long time, so picking the page closest to “never” is the next best thing
• Evicting the page that won’t be used for the longest period of time minimizes the number of page faults
• Page replacement algorithms are the techniques which decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. 
• Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages.

• When the page that was selected for replacement and was paged out, is referenced again then it has to read in from disk, and this requires for I/O completion.
•  This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
•  A page replacement algorithm looks at the limited information about accessing the pages provided by hardware, and tries to select which pages should be replaced to minimize the total number of page misses, while balancing it with the costs of primary storage and processor time of the algorithm itself.
•  There are many different page replacement algorithms.
• We evaluate an algorithm by running it on a particular string of memory reference and computing the number of page faults.

Reference String

• The string of memory references is called reference string. 
• Reference strings are generated artificially or by tracing a given system and recording the address of each memory reference.
• The latter choice produces a large number of data, where we note two things.
• For a given page size we need to consider only the page number, not the entire address.
• If we have a reference to a page p, then any immediately following references to page p will never cause a page fault.
•  Page p will be in memory after the first reference; the immediately following references will not fault.
• For example, consider the following sequence of addresses - 123,215,600,1234,76,96

If page size is 100 then the reference string is 1,2,6,12,0,0

ALGORITHMS:

FIFO PAGE REPLACEMENT
OPTIMAL PAGE REPLACEMENT
LRU PAGE REPLACEMENT
LRU APPROXIMATION PAGE REPLACEMENT
COUNTING BASED PAGE REPLACEMENT
PAGE-BUFFERING ALGORITHM