Page Replacement Algorithms in 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.
Page Fault – In simple terms, if an incoming stream item (page) is not available in any of the frames. Then page fault occurs.
A Page Fault occurs when a program running on the CPU tries to access a page that is in the address space of that program, but the requested page is currently not loaded into the main physical memory, the RAM of the system
FIFO-First In First Out
A FIFO replacement algorithm associates with each page the time when that page was brought into memory.
This is how FIFO works –
- If an incoming page is not available in any of the frames. Replacement shall be done.
- Page replaced is according to FIFO (First in First Out)
- The page that entered first must be swapped out first
- In other words, the oldest frame must be swapped out
Example
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
- Page Size/ Frame Size = 3
Table will look like(Explanation after the table)
Explanation –
- Step n [Incoming Stream] – Current Stack [x,y,z]
- Current Oldest – In Red
- After Replacing – In Green
Goes as
- Step 1 [7] – Current Stack [nil, nil, nil] (Page Fault Occurs)
- Result – [7, nil, nil]
- Step 2 [0] – Current Stack [7, nil, nil]
- Result – [7,0,nil] (Page Fault Occurs)
- Step 3 [1] – Current Stack [7, 0, nil]
- Result – [7,0,1] (Page Fault Occurs)
- Step 4 [2] – Current Stack -[7,0,1]
- Result – [2,0,1] (Page Fault Occurs)
- Step 5 [0] – Current Stack [2,0,1]
- Result – [2,0,1] as 0 is already Present
- Step 6 [3] – Current Stack [2,0,1]
- Result – [2,3,1]
- Step 7 [0] – Current Stack [2,3,1]
- Result – [2,3,0] (Page Fault Occurs)
- Step 8 [4] – Current Stack [2,3,0]
- Result – [4,3,0]
- Step 9 [2] – Current Stack [4,3,0]
- Result – [4,2,0] (Page Fault Occurs)
- Step 10 [3] – Current Stack [4,2,0]
- Result – [4,2,3] (Page Fault Occurs)
- Step 11 [0] – Current Stack [4,2,3]
- Result – [0,2,3] (Page Fault Occurs)
- Step 12 [3] – 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 [1] – Current Stack [0,2,3]
- Result – [0,1,3] (Page Fault Occurs)
If you have any questions ask in the comments section, and we will help.
Now page fault occurs 11 times out of 14.
So page fault ratio is 11/14.
Belady’s Anomaly
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, that’s not the case always. Sometimes by increasing the page size page fault rather increases, this type of anomaly is called belady’s Anomaly.(asked in AMCAT, CoCubes, Oracle)
For 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, we replace the element which is the current least recently used element in the 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 assume we are at the 10th iteration
1. a was last entered in current stack at 4th iteration.
2. b was entered at 2nd iteration
3. c was entered at 7th iteration
In this case d will replace b as b is the least recently used as was last seen in 2nd iteration
Optimal Page Replacement
In LRU we looked for the left furthermost page to replace. In optimal we do the opposite and look for right furthermost.
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.
Optimal Page Replacement Quick Facts
- 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 the 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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment