Page Replacement Algorithms in Operating Systems (OS) | Core CS

What is Page Replacement Algorithm and why it is needed?

One of the techniques which are used for memory management is paging. In paging, processes are divided into pages and main memory is divided into frames. Pages of a process are loaded into frames of main memory when required.

Page Replacement Algorithm is used when a page fault occurs. Page Fault means the page referenced by the CPU is not present in the main memory.

When the CPU generates the reference of a page, if there is any vacant frame available in the main memory then the page is loaded in that vacant frame. In another case, if there is no vacant frame available in the main memory, it is required to replace one of the pages in the main memory with the page referenced by the CPU.

Page Replacement Algorithm is used to decide which page will be replaced to allocate memory to the current referenced page.

Different Page Replacement Algorithms suggest different ways to decide which page is to be replaced. The main objective of these algorithms is to reduce the number of page faults.

Page Replacement Algorithms

First In First Out (FIFO) -This algorithm is similar to the operations of the queue. All the pages are stored in the queue in the order they are allocated frames in the main memory. The one which is allocated first stays in the front of the queue. The one which is allocated the memory first is replaced first. The one which is at the front of the queue is removed at the time of replacement.

Example: Consider the Pages referenced by the CPU in the order are 6, 7, 8, 9, 6, 7, 1, 6, 7, 8, 9, 1

• As in the above figure shown, Let there are 3 frames in the memory.
• 6, 7, 8 are allocated to the vacant slots as they are not in memory.
• When 9 comes page fault occurs, it replaces 6 which is the oldest in memory or front element of the queue.
• Then 6 comes (Page Fault), it replaces 7 which is the oldest page in memory now.
• Similarly, 7 replaces 8, 1 replaces 9.
• Then 6 comes which is already in memory (Page Hit).
• Then 7 comes (Page Hit).
• Then 8 replaces 6, 9 replaces 7. Then 1 comes (Page Hit).

        Number of Page Faults = 9

• While using the First In First Out algorithm, the number of page faults increases by increasing the number of frames. This phenomenon is called Belady's Anomaly.
• Let's take the same above order of pages with 4 frames.

• In the above picture shown, it can be seen that the number of page faults is 10.
• There were 9 page faults with 3 frames and 10 page faults with 4 frames.
• The number of page faults increased by increasing the number of frames.

Optimal Page Replacement - In this algorithm, the page which would be used after the longest interval is replaced. In other words, the page which is farthest to come in the upcoming sequence is replaced.

Example: Consider the Pages referenced by the CPU in the order are 6, 7, 8, 9, 6, 7, 1, 6, 7, 8, 9, 1, 7, 9, 6

• First, all the frames are empty. 6, 7, 8 are allocated to the frames (Page Fault).
• Now, 9 comes and replaces 8 as it is the farthest in the upcoming sequence. 6 and 7 would come earlier than that so not replaced.
• Then, 6 comes which is already present (Page Hit).
• Then 7 comes (Page Hit).
• Then 1 replaces 9 similarly (Page Fault).
• Then 6 comes (Page Hit), 7 comes (Page Hit).
• Then 8 replaces 6 (Page Fault) and 9 replaces 8 (Page Fault).
• Then 1, 7, 9 come respectively which are already present in the memory.
• Then 6 replaces 9 (Page Fault), it can also replace 7 and 1 as no other page is present in the upcoming sequence.

        The number of Page Faults = 8

• This is the most optimal algorithm but is impractical because it is impossible to predict the upcoming page references.

Least Recently Used - This algorithm works on previous data. The page which is used the earliest is replaced or which appears the earliest in the sequence is replaced.

Example: Consider the Pages referenced by the CPU in the order are 6, 7, 8, 9, 6, 7, 1, 6, 7, 8, 9, 1, 7, 9, 6

• First, all the frames are empty. 6, 7, 8 are allocated to the frames (Page Fault).
• Now, 9 comes and replaces 6 which is used the earliest (Page Fault).
• Then, 6 replaces 7, 7 replaces 8, 1 replaces 9 (Page Fault).
• Then 6 comes which is already present (Page Hit).
• Then 7 comes (Page Hit).
• Then 8 replaces 1, 9 replaces 6, 1 replaces 7, and 7 replaces 8 (Page Fault).
• Then 9 comes (Page Hit).
• Then 6 replaces 1 (Page Fault).

        The number of Page Faults = 12