Page replacement algorithm_html/css_WEB-ITnose

Optimal replacement algorithm

The optimal replacement algorithm is an idealized algorithm that has the best performance, but in reality It's not possible (yet).

The optimal replacement algorithm is a theoretical algorithm proposed by Belady in 1966. The pages it selects for elimination will never be used in the future, and may be pages that will no longer be accessed in the longest (future) time. Using the best replacement algorithm can usually guarantee the lowest page fault rate. However, since people currently cannot predict which page among the several pages of a process's memory will no longer be accessed for the longest time in the future, this algorithm cannot be implemented, but can use this algorithm to evaluate Other algorithms. Examples are given below.

Assume that the system allocates three physical blocks to a process, and consider the following page number reference string:
7, 0, 1, 2 , 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

When the process is running, first change 7, 0 , 1 three pages are loaded into memory. Later, when the process wants to access page 2, will generate a page fault interrupt . At this time, the OS will eliminate selected page 7 based on the optimal replacement algorithm. This is because page 0 will be the 5th page visited, page 1 will be the 14th page visited, and page 7 will only need to be loaded on the 18th page visit. The next time page 0 is accessed, there is no need to generate a page fault interrupt because it is already in memory. When the process accesses page 3, it will cause page 1 to be eliminated; because, among the three existing pages 1, 2, and 0, it will be the latest to be accessed in the future. Figure 4-26 shows the permutation graph when using the optimal permutation algorithm. As can be seen from the figure, 6 page replacements occurred using the optimal replacement algorithm.

First in, first out (FIFO) page replacement algorithm

This is the earliest replacement algorithm. This algorithm always eliminates the page that enters the memory first, that is, it selects the page that has resided in the memory for the longest time and eliminates it. This algorithm is not compatible with the actual running rules of the process, because in the process, some pages are frequently accessed, and the FIFO algorithm cannot guarantee that these pages will not be eliminated.

We still use the above example, but use the FIFO algorithm for page replacement (as shown below). When the process accesses page 2 for the first time, page 7 will be swapped out because it is the first to be transferred into memory; when it accesses page 3 for the first time, page 0 will be swapped out because it is in Among the three existing pages 2, 0, and 1, it is the oldest page. As can be seen from Figure 4-27, when using the FIFO algorithm, 12 page replacements are performed, which is exactly twice as many as the optimal replacement algorithm.

Note: When 3 is replaced into the memory for the first time, it is replaced by 0 instead of 1 (although 0 has just been accessed before 3, the 0 in the memory is still Memory pages arriving earlier than 1)

Least recently used (LRU) replacement algorithm

The most recently unused (LRU) page replacement algorithm makes decisions based on the usage of the page after it is transferred into the memory. The LRU replacement algorithm selects the most recently unused pages and eliminates them. This algorithm gives each page a visit field, which is used to record the time t that has elapsed since a page was last visited. When a page needs to be eliminated, the existing page is selected The page with the largest t value, that is, the page that has not been used for the longest time, will be eliminated.

The result of page replacement using the LRU algorithm in the above example is shown in the figure. When the process accesses page 2 for the first time, page 7 is replaced because it has not been accessed for the longest time. When the process accesses page 3 for the first time, page 1 becomes the most recently unused page, so it is swapped out. The optimal replacement algorithm is based on the "backward-looking" perspective, that is, it is based on the future usage of each page; while the LRU algorithm is "forward-looking", that is, based on the previous usage of each page. There is no necessary connection between the past and future direction of the page.

This article was collected and modified by Cout_Sev

From "Computer Operating System (Third Edition)" (Xidian University Press),

Please indicate the source when reprinting.

Thank you!