Page Replacement Approach
The page replacement approach is introduced when no frame is available for free, requiring the user to perform a search operation that is no longer used and has been freed. Users can free a frame by writing its contents to swap space and changing the page table (and every other table as well) to indicate that the page is no longer in memory as seen in figure 1.
Users will now be able to use the free frame to hold the page for which the process has failed. The user changes the page-fault administration routine to include page replacement:
- First, find the location of the desired page on the disk.
- Then find a free frame:
- If there is a free frame available, use it.
- If there is no free frame available, use the page-replacement algorithm to select a victim frame.
- Write the victim frame to the disk; change the page and frame tables as needed.
- Read the desired page into the recently free frame; change page and frame tables.
- Restart the user process.
Also check: segmentation in os
Note that, if no frame is free, two-page transfers are required: one outside and another one inside. This situation probably doubles the page-fault service time and extends the compelling access time when needed. A user can reduce this overhead by using an adjusted bit named dirty bit. At this point when this scheme is used, there is a corresponding adjusted bit of hardware on each page or frame. The adjusted bit for a page is set by the hardware whenever any word or byte in the page is written into, indicating that the page has been adjusted. At the point when we select a page for replacement, the user inspects its changed bit. If the bit is set, we know that the page has been modified since it was read in from the disk. In this case, we must write the page to the disk. If the modified bit is not set, however, the page has not been modified since it was read into memory. For this situation, we need not write the memory page to the disk: it is already there. This strategy additionally applies only to pages (e.g., pages of binary code). Such pages cannot be changed; therefore, they can be disposed of when required. This scheme can essentially reduce the time required to support a page fault because it reduces the I/O time in half if the page is not adjusted.
In other words page replacement is a process of swapping out a currently existing page from the frame of the main memory and replacing it with the required page. To achieve this task users require page replacement algorithms that decide which memory page is to be replaced. The process of replacement is sometimes called swap out or write to disk. Page replacement is performed when the requested page is not found in the main memory (page fault).
Two major aspects of virtual memory
There are two main aspects of virtual memory as represented in figure 2;
-
Frame allocation:
Frame allocation is about how many frames are to be allocated for which process.
-
Page Replacement:
The page replacement is all about determining the page number which needs to be replaced in order to make space for the requested page.
It is very important to have the optimal frame allocation and page replacement algorithm.
Also check: Demand Paging in Operating System
Need of page replacement:
Page replacement comes into action due to page-fault rates during demand-paging. We expected each page defect to be considered once when it was first referenced. If a process of ten pages actually uses only half of them, demand paging saves the I/O needed to load the five pages that are never used. We can also increase our degree of multi programming by running twice as many processes. Thus, if we had forty frames, we could run eight processes, not four that each required ten frames (five of which were never used).
If we increase the degree of multi programming, we are over-allocating memory. If we run six processes, each of which is ten pages in size, but actually uses only five pages, we have CPU usage and throughput, which are ten frames. However, it is possible that each of these processes, for a particular data set, may suddenly try to use all ten of its pages, resulting in sixty frames being required when only forty are available.
In addition, consider that system memory is not used to hold only program pages. Buffers for I/O also consume a significant amount of memory. This use may increase the stress on the memory-placement algorithm. Deciding how much memory to allocate to I/O and how much to program a page is a significant challenge. Some systems allocate a certain percentage of memory for I/O buffers, while others allow all user processes and I/O subsystems to compete for all system memory.
The over-allocation of memory appears as follows. When a user is executing a process, a page fault occurs. The operating system determines where the desired page is located on the disk, but then finds that there are no free frames in the free-frame list; All memory is in use as presented in figure 3.
The operating system has several options at this point. This user can end the process. However, demand paging is an attempt by the operating system to improve computer system usage and throughput. Users should not be aware that their processes are running on a paged system — the paging must be logically transparent to the user. So this option is not the best option. At this point the page replacement technique comes into action.
Also check: Memory fragmentation in Operating System
Page Replacement Algorithms
Page replacement algorithms in operating systems have separate operational logic to decide which page to replace when a new page arrives in the system.
Page replacement algorithm is required when:
- All frames of main memory are already occupied.
- Thus, a page would have to be changed to make a room for the required page.
Also check: optimal page replacement algorithm
Types of Page Replacement Algorithms
Various page replacement algorithms are available which are as follows;
-
Various page replacement algorithms FIFO: First Out First Out Page Replacement Algorithm – A good page replacement algorithm is one that reduces the number of page faults.
- LIFO: Last In First Out Page Replacement Algorithm-Only frame is used for page replacement during entire procedure after all the frames get occupied.
- LRU: Least Recently Used Page Replacement Algorithm- In this algorithm page will be replaced which is least recently used.
- Optimal: Optimal Page Replacement Algorithm- In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.
- Random Page: Random Page Replacement Algorithm-this algorithm randomly replaces any page.
Also check: classification of embedded systems
