PAGE REPLACEMENT ALGORITHMS in OS

PAGE REPLACEMENT ALGORITHMS

In general, we want a page replacement algorithm with the lowest page-fault rate.

We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults on that string.

To determine the number of page faults for a particular reference string and page replacement algorithm, we also need to know the number of page frames available.

Obviously, as the number of frames available increases, the number of page faults decreases.

(Expected relationship between number of free frames allocated to a process and the number of page faults caused by it).

FIFO Page Replacement

The simplest page-replacement algorithm is a FIFO algorithm. 

When a page must be replaced, the oldest page is chosen.

We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory we insert t at the tail of the queue. 

Example: consider the reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1