What is the page replacement algorithm?

During the address mapping process, if it is found in the page 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 algorithms.

Common replacement algorithms

Optimal replacement algorithm (OPT)

This is an ideal page replacement algorithm, but in practice it is impossible to implement. 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 it will be accessed after 1000 instructions. Each page can [1] 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 [1] 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.

Most recently unused (LRU) algorithm

The main difference between the FIFO algorithm and the OPT algorithm is that the FIFO algorithm uses the length of time after the page enters the memory as a replacement The basis of the OPT algorithm is the time when the page will be used in the future. If the recent past is used as an approximation of the near future, then pages that have not been used for the longest period of time in the past can be replaced. Its essence is that when a page needs to be replaced, the page that has not been used for the longest time in the previous period of time is selected to replace it. This algorithm is called the least recently used algorithm (Least Recently Used, LRU).

The LRU algorithm is related to the last time each page was used. When a page must be replaced, the LRU algorithm selects the page that has been least used in the past period of time.

The LRU algorithm is a frequently used page replacement algorithm and is considered to be quite good, but there is a problem of how to implement it.

The LRU algorithm requires the support of actual hardware.

The problem is how to determine the order of the last use time. There are two feasible methods for this:

1. Counter.

The simplest case is to make each page table entry correspond to a usage time field and add a logical clock or counter to the CPU. This clock is incremented by 1 for each memory access. Whenever a page is accessed, the contents of the clock register are copied into the usage time field of the corresponding page table entry. This way we can always keep the "time" when each page was last visited. When replacing pages, select the page with the smallest time value. In doing so, not only must the page table be looked up, but also the time in the page table must be maintained when the page table changes (due to CPU scheduling), and the problem of clock value overflow must also be taken into consideration.

2. Stack.

Use a stack to retain page numbers. Whenever a page is accessed, it is taken out of the stack and placed on top of the stack. In this way, the most used page is always placed at the top of the stack, and the least used page is placed at the bottom of the stack. Since an item needs to be removed from the middle of the stack, a two-way chain with head and tail pointers is used to connect it. In the worst case, removing a page and placing it on top of the stack requires changing 6 pointers. There is an overhead for each modification, but the page that needs to be replaced can be obtained directly without searching, because the tail pointer points to the bottom of the stack, where the page to be replaced is.

Because the implementation of the LRU algorithm requires a large amount of hardware support, it also requires a certain amount of software overhead. So what is actually implemented is a simple and effective LRU approximation algorithm.

One LRU approximation algorithm is the Not Recently Used (NUR) algorithm.

It adds a reference bit to each entry in the storage block table, and the operating system periodically sets them to 0. When a page is accessed, this bit is set by hardware. Over time, these bits can be examined to determine which pages have been used and which pages have not been used since the last time they were set to 0. The page whose bit is 0 can be eliminated because it has not been accessed in the recent period.

4) Clock replacement algorithm (approximate implementation of LRU algorithm)

5) Least used (LFU) replacement algorithm

When using the least used replacement algorithm, it should be in Each page in memory is set up with a shift register to record how often the page is accessed. The replacement algorithm selects the page that was least used in the previous period as the eviction page.

Since the memory has a high access speed, such as 100 ns, a page may be accessed thousands of times continuously within 1 ms. Therefore, it is usually not possible to directly use a counter to record the number of times a page is accessed. times, instead using a shift register method. Each time a page is accessed, the highest bit of the shift register is set to 1, and then shifted to the right every certain time (for example, 100 ns). In this way, the page that has been least used in the recent period will be the page with the smallest ΣRi.

The page access graph of the LFU replacement algorithm is exactly the same as the access graph of the LRU replacement algorithm; in other words, using such a set of hardware can implement both the LRU algorithm and the LFU algorithm. It should be pointed out that the LFU algorithm does not really reflect the page usage, because in each time interval, only one bit of the register is used to record the page usage. Therefore, accessing once is equivalent to accessing 10,000 times.

6) Working set algorithm

7) Working set clock algorithm

8) Aging algorithm (an efficient algorithm very similar to LRU)

9) NRU (Not used recently) Algorithm

10) Second chance algorithm

The basic idea of ​​the second chance algorithm is the same as FIFO, but it has been improved to avoid frequently used pages Replace it. When a replacement page is selected, its access bits are checked. If it is 0, the page is eliminated; if the access bit is 1, it is given a second chance and the next FIFO page is selected. When a page gets a second chance, its access bit is cleared to 0 and its arrival time is set to the current time. If the page has been visited during this period, position 1 is visited. Pages thus given a second chance will not be eliminated until all other pages have been eliminated (or have also been given a second chance). Therefore, if a page is used frequently, its access bit always remains 1 and it is never eliminated.

The second chance algorithm can be viewed as a circular queue. Use a pointer to indicate which page is to be eliminated next. When a block of memory is needed, the pointer advances until it finds a page whose access bit is 0. As the pointer advances, the access bit is cleared to 0. In the worst case, all access bits are 1 and the pointer goes through the entire queue for a week, giving each page a second chance. At this time, it degenerates into the FIFO algorithm.

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