How to understand the page replacement algorithm

Understand the page replacement algorithm: When a page fault occurs, if there is no free page in the operating system memory, the operating system must select a page in the memory and move it out of the memory to make way for the page that will be transferred in. space, and the rules used to select which pages to eliminate are called page replacement algorithms.

#During the address mapping process, if it is found that the page to be accessed is not in the memory, a page fault interrupt will occur. When a page fault occurs, if there is no free page in the operating system's memory, the operating system must select a page in the memory and move it out of the memory to make room for the page to be transferred in. The rules used to select which pages to eliminate are called Page Replacement Algorithm.

Optimal replacement algorithm (OPT)

This is an ideal page replacement algorithm, but it is actually impossible to achieve. The basic idea of ​​this algorithm is: when a page fault occurs, some pages are in memory, one of which will be accessed soon (also including the page of the next instruction), while other pages may not be accessed until 10 or 100 Or 1000 instructions before being accessed, each page can be marked with the number of instructions to be executed before the page is accessed for the first time. The optimal page replacement algorithm simply states that the page with the largest markup should be replaced. The only problem with this algorithm is that it cannot be implemented. When a page fault occurs, the operating system has no way of knowing when each page will next be accessed. Although this algorithm is not possible to implement, the optimal page replacement algorithm can be used to measure and compare the performance of achievable algorithms.

First in first out replacement algorithm (FIFO)

The simplest page replacement algorithm is the first in first out (FIFO) method. The essence of this algorithm is to always choose the page that has stayed in the main memory the longest (that is, the oldest) to replace, that is, the page that enters the memory first and exits the memory first. The reason is: the earliest page transferred into memory is more likely to be no longer used than the page that was just transferred into memory. Create a FIFO queue to store all pages in memory. Replaced pages are always placed at the head of the queue. When a page is put into memory, it is inserted at the end of the queue.

This algorithm is ideal only when accessing the address space in linear order, otherwise it is not efficient. Because those pages that are frequently accessed tend to stay in main memory the longest, and as a result they have to be replaced because they become "old".

Another disadvantage of FIFO is that it has an abnormal phenomenon, that is, when adding storage blocks, the page fault interrupt rate increases. Of course, the page direction that causes this anomaly is actually rare.

Related free learning recommendations: php programming(Video)

The above is the detailed content of How to understand the page replacement algorithm. For more information, please follow other related articles on the PHP Chinese website!