A Quick Guide to Page Replacement Algorithm
Introduction
In this article, we will discuss the page replacement algorithm in the operating system. The page replacement algorithm is responsible for deciding which page is required to be replaced if a new page comes in.
Page fault
The page fault occurs when a running program tries to capture the memory page which is linked to the virtual address space but it doesn’t reside in the physical memory. The page fault occurs when the actual physical memory is smaller in size as compared to the virtual memory. The operating system is responsible for replacing newer pages with existing ones.
Page replacement algorithms
There are various types of page replacement algorithms and they are listed below:
First In First Out(FIFO)
The First In First Out (FIFO) is the simplest page replacement algorithm. The operating system keeps a look-up of all the pages in the memory as a queue. The oldest page lies as a front entity of the queue.
Let us take an example and see how this actually works:
Let us take a page reference as 1, 2, 3, 2, 0, 4, 8:
|
|
1 |
Miss
|
2 |
1 |
Miss
3 |
2 |
1 |
Miss
3 |
2 |
1 |
Hit
3 |
2 |
0 |
Miss
3 |
4 |
0 |
Miss
8 |
4 |
0 |
Miss
Total page faults are six
Working
Intialially all the slot were empty, when 1, 2, and 3 came they are assigned to these three empty slots. When 2 came, it was already present in the memory hence, page hit occurs for 2. After that when 0 came since it was not already present in the memory hence we need to empty a slot. Since, this algorithm is all about FIFO, so the oldest slot which is occupied by 1 shall get empty and should be occupied by 0. The next page has a value of 4 and the oldest slot so far is 2, so we should replace it with 4. The last page is 8 and it must be replaced with 3.
Optimal replacement algorithm
The optimal replacement algorithm replaces the pages that will not be used for the longest duration of time in the future.
Let us take a page reference as 1, 2, 3, 2, 0, 4, 8:
|
|
1 |
Miss
|
2 |
1 |
Miss
3 |
2 |
1 |
Miss
3 |
2 |
1 |
Hit
3 |
2 |
0 |
Miss
4 |
2 |
0 |
Miss
4 |
8 |
0 |
Miss
1, 2, 3, 2, 0, 4, 8
Working
Initially all the slots were empty, so when 1, 2 and 3 comes they occupy all the empty slots. After which 2 arrives, since 2 was already present there so there would be page hit. Then, 0 arrives it gets replaced with 1 as it occupies the longest non-used slot . Then, 4 arrives and gets replaced with 3. Then, 8 arrives it gets replaced with 2.
Least recently used algorithm
In least recently used algorithm, that page would be replaced that has been replaced less recently.
Let us take a page reference as 1, 2, 3, 2, 0, 4, 8:
|
|
1 |
Miss
|
2 |
1 |
Miss
3 |
2 |
1 |
Miss
3 |
2 |
1 |
Hit
3 |
2 |
0 |
Miss
4 |
2 |
0 |
Miss
4 |
8 |
0 |
Miss
Working
Initially all the slots were empty, so when 1, 2 and 3 comes they occupy all the empty slots. After which 2 arrives, since 2 was already present there so there would be page hit. Then, 0 arrives it gets replaced with 1 as it occupies the least recently used slot. Then, 4 arrives and gets replaced with 3. Then, 8 arrives it gets replaced with 2.
Most recently used algorithm
In this algorithm, that page would be replaced that has been used recently. Note that there are chances that Belady’s anomaly might occur in this algorithm.
Conclusion
In this article, we discussed different types of page replacement algorithms like first in first out (FIFO), Optimal page replacement algorithm, Least recently used algorithm, Most recently used algorithm (MRU). We believe that this tutorial has surely improved your operating systems knowledge.