5.4.4. Page Replacement Algorithms¶
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.
5.4.4.1. Static Replacement Algorithms¶
The static paging algorithms implement the replacement policy when the frame allocation to a process is fixed.
5.4.4.1.1. First-In-First-Out (FIFO) Replacement¶
On a page fault, the frame that has been in memory the longest is replaced.

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.

5.4.4.1.2. 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.

5.4.4.1.3. Least Recently Used (LRU) Replacement¶
On a page fault, the frame that was least recently used in replaced.

5.4.4.2. LRU Approximation¶
Pages with a current copy on disk are first choice for pages to be removed when more memory is needed. To facilitate Page Replacement Algorithms, a table of valid or invalid bits (also called dirty bits) is maintained.

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