⏪Previous Next⏩

· Each process is allocated frames (memory) which hold the process’s pages (data)

· Frames are filled with pages as needed – this is called demand paging

· Over-allocation of memory is prevented by modifying the page-fault service routine to replace pages

· The job of the page replacement algorithm is to decide which page gets victimized to make room for a new page

· Page replacement completes separation of logical and physical memory

In an operating system that uses paging for memory management, a page replacement algorithm is needed to decide which page needs to be replaced when new page comes in.

Page Fault – A page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.

Since actual physical memory is much smaller than virtual memory, page faults happen. In case of page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce the number of page faults.

Page Replacement Algorithms in Operating Systems

FIFO Page Replacement Algorithm
LRU Page Replacement Algorithm
Optimal Page Replacement Algorithm
Random Page Replacement Algorithm

FIFO Page Replacement Algorithm-

As the name suggests, this algorithm works on the principle of “First in First out“.
It replaces the oldest page that has been present in the main memory for the longest time.
It is implemented by keeping track of all the pages in a queue.

· Example using 4 frames:

Reference #	1	2	3	4	5	6	7	8	9	10	11	12
Page referenced	1	2	3	4	1	2	5	1	2	3	4	5
Frames _ = faulting page	1	1	1	1	1	1	5	5	5	5	4	4
		2	2	2	2	2	2	1	1	1	1	5
			3	3	3	3	3	3	2	2	2	2
				4	4	4	4	4	4	3	3	3

· Analysis: 12 page references, 10 page faults, 6 page replacements. Page faults per number of frames = 10/4 = 2.5

Belady’s anomaly – Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.

LRU Page Replacement Algorithm-

As the name suggests, this algorithm works on the principle of “Least Recently Used“.
It replaces the page that has not been referred by the CPU for the longest time.
Example using 4 frames:

Page referenced	1	2	3	4	1	2	5	1	2	3	4	5
Frames _ = faulting page	1	1	1	1	1	1	1	1	1	1	1	5
		2	2	2	2	2	2	2	2	2	2	2
			3	3	3	3	5	5	5	5	4	4
				4	4	4	4	4	4	3	3	3

· Analysis: 12 page references, 8 page faults, 4 page replacements. Page faults per number of frames = 8/4 = 2

Optimal Page Replacement Algorithm-

This algorithm replaces the page that will not be referred by the CPU in future for the longest time.
It is practically impossible to implement this algorithm.
This is because the pages that will not be used in future for the longest time can not be predicted.
However, it is the best known algorithm and gives the least number of page faults.
Hence, it is used as a performance measure criterion for other algorithms.

· Example using 4 frames:

Reference #	1	2	3	4	5	6	7	8	9	10	11	12
Page referenced	1	2	3	4	1	2	5	1	2	3	4	5
Frames _ = faulting page	1	1	1	1	1	1	1	1	1	1	4	4
		2	2	2	2	2	2	2	2	2	2	2
			3	3	3	3	3	3	3	3	3	3
				4	4	4	5	5	5	5	5	5

· Analysis: 12 page references, 6 page faults, 2 page replacements. Page faults per number of frames = 6/4 = 1.5

Random Page Replacement Algorithm-

As the name suggests, this algorithm randomly replaces any page.
So, this algorithm may behave like any other algorithm like FIFO, LIFO, LRU, Optimal etc.