CREATE OWN LIBRARY
Page Replacement
Page replacement Introduction
When page replacement will occur?
Page replacement is needed when a page fault occurs and memory is full i.e. no free frames in memory.
Problem can occur due to page replacement:
While it would be possible to pick a random page to replace at each page fault, system performance is much better if a page is not heavily used is chosen but if the heavily used page is removed, it will probably have to be brought back in quickly, resulting in extra overhead and another page fault will occur.
Real life problem of page replacement:
The most common page replacement problem is in a Web server. The server can keep a certain number of heavily used Web pages in its memory cache. However, when the memory cache is full and a new page is referenced, a decision has to be made on which Web page to replace.
The considerations are similar to pages of logical memory, except that the Web pages are never modified in the cache, so there is always a fresh copy ‘‘on disk.’’ In a virtual memory system, pages in the main memory may be either clean or dirty(modified).
Hence it is important to replace a page that is not likely to be referenced in the immediate future. But how does the virtual memory manager know which page is not likely to be referenced in the immediate future?
Solution:
So, to replace always a better page from the main memory, where the replaced page has no chance to become back quickly and may not cause a page fault again (overhead), we used some algorithms, which is called a page replacement algorithm.
1. Optimal
4. FIFO
7. Random Page Replacement Algorithm
There are many different page-replacement algorithms. Every operating system probably has its own replacement scheme. How do we select a particular replacement algorithm? In general, we want the one with the lowest page-fault rate.
What is Reference String:
We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references is called a reference string.
Example:
0 1 2 1 3 1 6 7 ........ means CPU first generated address for 0-page, then 1, 2, 1 in this order.
What is Demand paging:
When a process going to execute, we are not going to load any page until is required. So, Pages are loaded only when they are demanded during program execution. Pages that never accessed are thus never loaded into physical memory.
As we know apart from the frame number each entry of the page contains:
1. Reference bit
2. Cache Disable
3. Dirty bit
4. Present/Absent bit
5. Permission bit
For more details of each page entry please follow chapter: Number of information at page entry
In the above page entry information, three information are page replacement algorithm uses
1. Reference bit: The reference bit is important at the time of the page replacement algorithm. It is used to identify how many times this page is referred at the time of execution that helps to know when the last time this page is referred. It is set by MMU when a page read/write.
2. Dirty Bit: It is used to track which page is modified when it resides in the main memory. Set when the page is written also called modified bit.
3. Present/Absent (Valid/invalid) bit: It is used to see a page is present at the main memory frame or not.
