One, what is the page replacement algorithm
While a process is running, a page missing interrupt occurs if the page it accesses is not in memory. If there are no free pages in memory at this point, the operating system needs to select a page in memory and move it out so that the pages that need to be accessed can be brought into memory. The algorithm used to choose which page to eliminate is called the page replacement algorithm. Good page replacement algorithm has a low page replacement frequency.
Two, common page replacement algorithm
1. OPT(Optimal permutation algorithm)
Best replacement algorithm: each selection of the page will be eliminated will never be used or the longest time not to be visited pages. This ensures the lowest page loss rate.
For example, suppose the operating system allocates three memory blocks to a process, and the process then accesses 7,5,2,3,6,2,7,1,6,7,2,3,7,2,7.
As shown in the figure, in step 4, page 3 needs to be brought into memory. At this point, memory is full, so you need to select a page from 7, 5, and 2 to be eliminated. In accordance with the rules of the best replacement algorithm, search in the future. At this time, 2 and 7 will be visited successively, so the page 5 will be eliminated, that is, the page that is not visited in the longest time.
2, FIFO(first In, first out algorithm)
FIFO algorithm is the simplest page replacement algorithm. As the name suggests, each FIFO eliminated page is the first page into memory. The implementation method of FIFO is to put the pages into memory in sequence into the queue, when the need to replace the page, select the page of the head of the queue.
For example, suppose the operating system allocates three memory blocks to a process, and the process then accesses 7,5,2,3,6,2,7,1,6,7,2,3,7,2,7. The page looks like this in memory:
3. LRU(most recent unused algorithm)
LRU(Least Recently Used), each page is the most Recently unused page. Therefore, it is necessary to record the time t experienced since the next visit to the page. When a page is to be eliminated, select the page with the largest t of existing pages in memory, that is, the page that has not been used for the most recent time.
For example, suppose the operating system allocates three memory blocks to a process, and the process then accesses 7,5,2,3,6,2,7,1,6,7,2,3,7,2,7, 7. The page looks like this in memory:
As shown in the figure, page 3 needs to be brought into memory in step 4. At this time, memory is full, and one page needs to be selected from 7, 5, and 2 to be eliminated. According to LRU rules, the time elapsed since page 7 was visited last time is 3, it is the largest, so page 7 is eliminated.
4. LFU(least recently used algorithm)
LFU(Least Recently used algorithm), which is based on the idea that if a piece of data has been used infrequently in the recent past, it has little chance of being used in the future. Note the difference between LFU and LRU algorithms. LRU’s elimination rules are based on access time, while LFU is based on access number.
For example, suppose the operating system allocates three memory blocks to a process, and the process then accesses 5, 4, 5, 3, 3, 2, 5, 1, 4. The page looks like this in memory:
As shown in the figure, page 1 needs to be brought into memory in step 8. At this time, memory is full, and one page needs to be selected from 5, 2, and 3 to be eliminated. According to LFU rules, page 2 is used 1 times in a recent period, which is the smallest. So get rid of page 2.
For more technical articles, please scan the code to follow the public number.