Last day I learned Dijkstra's Algorithm and today I learned two algorithms in the college which are not the kind of algorthms that I have learned so far like sorting or searching one but these are the algorithms that are used in the OS design and are simple and easy to implement.
As every CS student one day learn about the OS I too am learning about Operating Systems now a days in college and today I came along these algorithms that are called Page Replacement Algorithms but what are these?
Page Replacement Algorithms
Page Replacement Algorithms are the algorithms that are used to decide what memory pages to swap in and out of the Virtual Memory. These algorithms are used by the Operating Systems for Virtual Memory Management. A page is a block size in the memory for processes of a program. A program's processes are divided in to smaller pages and these pages are loaded into the memory from the Virtual memory when they are required.
Virtual Memory is a storage allocation scheme used by Memory Management Unit to execute processes that are not in the main memory completely. It allows to run processes that are larger than the main memory. Memory is expensive so Virtual Memory is used to reduce the cost.
Algorithms
In the memory, fixed number of pages can only be used at the same time so when a page is needed to process it is first checked in the memory block called frame. If the page is in the frame it is processed and if not a Page Replacment Algorithm is used to swap the requested page into the memory to process it.
The OS defines a Reference String which is a large set of all the pages numbers that will be processed one by one. It looks like the following.
ref_str = [7, 0, 1, 2, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
and consider that the memory can store only three pages at a time so the Algorithm will decide what page to load. There are many algorithms that are used to replace pages but I will be only writing two of them which are FIFO and POR.
First In FIrst Out (FIFO)
This page swapping algorithm does what it name says. It first looks at the first page number from the ref_str and loads that page from the virtual memory then it does the same for the second and the third page but after that when a fourth page is needed to load t check wether the page is already in the frame or not and if not it will swap the page with the one that was loaded first in the current frame.
|7|0|1|2|0|3|2|1|2|0|1|7|0|1|
--- Frames ---
|7|7|7|2| |2| | | |2|1|1| | |
|-|0|0|0| |3| | | |3|3|7| | |
|-|-|1|1| |1| | | |0|0|0| | |
As you can see first it loads 7, then 0, then 1 and after that it will load 2 but in place of 7 because 7 was the first one from the frame that was loaded in.
Page Optimal Replacement (POR)
Page Optimal Replacement algorithm will only replace the page that will not be used for the longer peroid of time. It checks the ref_str first and decides what page to replace when the time comes for the page that is not in the frame to be loaded.
|7|0|1|2|0|3|0|4|2|3|0|3|2|1|
--- Frames ---
|7|7|7|2| |2| |2| | |2| | |2|
|-|0|0|0| |0| |4| | |0| | |0|
|-|-|1|1| |3| |3| | |3| | |1|
This example shows that at frame six, the algorithm replaces one instead of 2 becasue the page one is not being used in the frame until the very last frame and other two were being used in the future. This is the most efficient page replacement algorithm but it is also difficut to implement becasue the algorithm has to know what pages will be used in the future to work properly.
zainsci