Q: Given an example that illustrates several page-replacement algorithms, and compares their page faults.

A:

1. First In First Out (FIFO)
In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

2. Optimal Page replacement
In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

3. Least Recently Used (LRU)
In this algorithm page will be replaced which is least recently used.

 

Example:

Given reference string 7 0 1 2 0 3 0 4 2 3 0 3 1 2 0

• In FIFO algorithm, the page fault is 9.


• In Optimal algorithm, the page fault is 7.


• In LRU algorithm, the page fault is 7.