Page Replacement Algorithms in Operating System (OS)
Page Replacement Algorithms in OS
On the paging page we saw the mapping of virtual memory to physical memory and how MMU does the paging process. But, what should happen when a new page comes is in scenerio. Which of the existing pages should be replaced and how to decide which one to replace.
On this page we will discuss all page replacement algorithms in operating system.
Page Replacement algorithms in operating system are different operational logics to decide which page should be replaced when a new page comes in the system.
Types of Page Replacement Algorithms
- FIFO – First in First Out
- LRU – Least Recently Used
- Optimal Page Replacement Algorithm
- LFU – Least Frequently Used
- MFU – Most Frequently Used
Page Fault – A page that is available (mapped) in the Logical Memory is not available (loaded) in the physical memory causes an interrupt service to be called by hardware.
In page replacement algorithms basically we will be looking for page faults, its okay if you don’t understand it now. With examples given for each algorithm you will be able to understand what a page fault is.
FIFO-First In First Out
A FIFO replacement algorithm associates with each page the time when that page was brought into memory.When a page must be replaced, the oldest page is chosen i.e. the page which was loaded first goes out thus, justifying its name FIFO.
Track is kept in a FIFO table of the following –
- Current pages in memory
- Recent Arrival coming in
- Oldest page in the memory
The idea is obvious from the name –
It might be a confusing theory, lets look with an example –
Incoming page Steam – 7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Page Size/ Frame Size = 3
Table will look like(Explanation after the table)
|Incoming Page Stream ->||7||0||1||2||0||3||0||4||2||3||0||3||2||1|
|Existing at position 1||7||7||7||2||2||2||4||4||4||0||0|
|Existing at position 2||0||0||0||3||3||3||2||2||2||1|
|Existing at position 3||1||1||1||0||0||0||3||3||3|
- Step n [Incoming Stream] – Current Stack [x,y,z]
- Current Oldest – In Red
- After Replacing – In Green
- Step 1  – Current Stack [nil,nil,nil] (Page Fault Occurs)
- Result – [7,nil,nil]
- Step 2  – Current Stack [x,y,z]
- Result – [7,0,nil] (Page Fault Occurs)
- Step 3  – Current Stack [x,y,z]
- Result – [7,0,1] (Page Fault Occurs)
- Step 4  – Current Stack -[7,0,1]
- Result – [2,0,1] (Page Fault Occurs)
- Step 5  – Current Stack [2,0,1]
- Result – [2,0,1] as 0 is already Present
- Step 6  – Current Stack [2,0,1]
- Result – [2,3,1]
- Step 7  – Current Stack [2,3,1]
- Result – [2,3,0] (Page Fault Occurs)
- Step 8  – Current Stack [2,3,0]
- Result – [4,3,0]
- Step 9  – Current Stack [4,3,0]
- Result – [4,2,0] (Page Fault Occurs)
- Step 10  – Current Stack [4,2,0]
- Result – [4,2,3] (Page Fault Occurs)
- Step 11  – Current Stack [4,2,3]
- Result – [0,2,3] (Page Fault Occurs)
- Step 12  – Current Stack [0,2,3]
- Result – [0,2,3] (3 already there)
- Step 13 [Incoming Stream] – Current Stack [0,2,3]
- Result – [0,2,3] (2 already there
- Step 14  – Current Stack [0,2,3]
- Result – [0,1,3] (Page Fault Occurs)
If you have any questions ask in the comments section, we will help.
Now page fault occurs 11 times out of 14.
So page fault ratio is 11/14.
Think – Now, one should think that increase the page size(frame size as page size = frame size) will lead to less page fault, right!! since more chances of element to be present in the queue.
But, thats not the case always. Some times by increasing the page size page fault rather increases, this type of anomaly is called belady’s Anomaly.(asked in AMCAT, CoCubes, Oracle)
Example consider the following(solve yourself for practice)
- 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
- Using 3 slots gives 9 page faults
- Using 4 slots gives 10 page faults
Least Recently Used
In this algorithm for any incoming page stream unit say X, we replace the element which is the current least recently used element in current stack.
That is, when we look to the left of the table, that we have created we choose the further most page to get replaced.
Let’s say d is incoming page and current stack is [a,b,c].
Lets assume we are at 10th iteration
- a was last entered in current stack at 4th iteration.
- b was entered at 2nd iteration
- c was entered at 7th iteration
In this case d will replace b as b is the least recently used.
But, What if !!!
b was entered at 2nd iteration and replaced by some other page on 5th and then entered current stack again at 8th iteration??
In this case b will not be least recently used but a will be and thus a will be replaced.
Trick is to look for first occurance of page towards the left of the table and whichever is the furthermost. Incoming page should replace that.
Page Reference Stream:
Total 11 Page Faults.
Optimal Page Replacement
In LRU we looked for the left further most page to replace.
In optimal we do opposite and look for right further most. Now, this is done so that there are lesser page faults as the element will not used for the longest duration of time in the future.
- The result of the discovery of Belady’s Anamoly
- Lowest page fault rate of all algorithm’s and will never suffer from belady’s Anamoly.
- Simply it replaces the pages that won’t be used for longest period of time.
- Optimal page replacement is perfect, but not possible in practice as operating system cannot know future requests.
- The use of Optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.
The image below shows the implementation of Optimal page replacement Algorithm.
Least Frequently Used
This algorithm is not for placement course.
But basically in current stack at any iteration we choose that element for replacement which has smallest count in the incoming page stream.
Most Frequently Used
This algorithm is not for placement course.
But basically in current stack at any iteration we choose that element for replacement which has highest count in the incoming page stream.
- Memory Management Introduction
- Partition Allocation Method
- Buddy- System Allocator
- Types of Paging
- Mapping Virtual address to Physical Address.
- Virtual Memory
- Demand Paging
- Implementation of Demand paging and page fault
- Page Replacement Algorithms
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging