Optimal page replacement algorithm: According to this algorithm, a page which is referenced farthest will be replaced first. For example, when a page fault occurs, there are pages in the memory which will be referenced after a certain number of instructions. Say if a page is referenced after a million instructions and this is the farthest page to be referenced. Then, according to optimal page replacement algorithm, this page will be replaced first. Optimal page replacement algorithm is a theoretical algorithm and cannot be implemented in real because when a page fault occurs the operating system doesn’t know when a particular page will be referenced.
Not recently used page replacement algorithm: There are two bits R for referenced and M for modified associated with a page in a page table entry. On the occasion of a page fault, pages are divided to 4 classes based on the R and M values:
- Class 0: not referenced and not modified
- Class 1: not referenced and modified
- Class 2: referenced and not modified
- Class 3: referenced and modified
According to the not recently used page replacement algorithm, a page is replaced at random from the lowest numbered non empty class.