1. Optimal Replacement Algorithm (OPT) (ideal replacement algorithm): Remove pages that are never needed from main memory; if no such pages exist, select the page that does not need to be accessed for the longest time. The selected eliminated pages will never be used in the future, or pages that will no longer be accessed within the longest period of time, so that the lowest page fault rate can be guaranteed.

The best replacement algorithm can be used to evaluate other algorithms. Suppose 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, the three pages 7, 0, and 1 are loaded into the memory in sequence. When a process wants to access page 2, a page fault interrupt occurs. According to the best replacement algorithm, page 7 that needs to be transferred in the 18th access is selected to be eliminated. Then, when page 0 is accessed, there is no need to generate a page fault interrupt because it is already in the memory. When visiting page 3, page 1 will be eliminated according to the best replacement algorithm... and so on, as shown in Figure 3-26. It can be seen from the figure that the best replacement algorithm is used.

It can be seen that the number of page fault interruptions is 9 and the number of page replacements is 6.

2. First-in-first-out replacement algorithm (FIFO): It is the simplest page replacement algorithm. The basic idea of ​​this algorithm is: when a page needs to be eliminated, the page with the longest resident time in the main memory is always selected for elimination, that is, the page that enters the main memory first is eliminated first. The reason is that the page that was first transferred to the main memory will no longer be used.

The above example is still used here, and the FIFO algorithm is used for page replacement. When the process accesses page 2, it swaps out page 7 that entered the memory earliest. Then when page 3 is accessed, the page that entered the memory first among 2, 0, and 1 is swapped out. It can be seen from Figure 3-27 that 12 page replacements are performed when using the FIFO algorithm, which is exactly twice the number of the best replacement algorithm.

The FIFO algorithm also generates an abnormal phenomenon that when the number of allocated physical blocks increases but the number of page faults does not decrease, it is discovered by Belady in 1969, so it is called Belady anomaly, as shown in Figure 3-28. Only FIFO algorithm may have Belady anomaly, while LRU and OPT algorithms will never have Belady anomaly.

访问页面	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1	4	4	4	5			,5'	5
物理块2		2	2	2	1	1	1			3	3
物理块3			3	3	3	2	2			2	4
缺页否	√	√	√	√	√	√	√			√	√
		1	1	1			5	5	5	5	4	4
物理块2*		2	2	2			2	1	1	1	1	5
物理块3*			3	3			3	3	2	2	2	2
物理块4*				4			4	4	4	3	3	3
缺页否	√	√	√				√	√	√	√	√	√

Note: The "oldest" page in the memory pages will be directly overwritten by the new web page, instead of the "oldest" page being dequeued first, and then the new web page will be entered from the end of the queue.
3. The least recently used (LRU) algorithm: The basic idea of ​​this algorithm is to use the principle of locality to speculate future behavior based on the past page access history of a job during its execution. It believes that pages that have not been visited in the past period of time may not be visited again in the near future. Therefore, the essence of this algorithm is: when a page needs to be eliminated, the page that has not been used for the most recent period of time is always selected to be eliminated.

Then use the LRU algorithm to perform page replacement for the above example, as shown in Figure 3-29. When the process accesses page 2 for the first time, it replaces page 7 that has not been accessed the most recently. Then when you visit page 3, swap out page 1 that has not been used the most recently.

In fact, the LRU algorithm "looks forward" based on the previous situation of each page, while the optimal replacement algorithm "looks backward" based on the use situation of each page later.

***LRU has better performance, but requires hardware support from registers and stacks. LRU is a stack type algorithm. Theoretically, it can be proved that the Belady exception is impossible for stack algorithms. The FIFO algorithm is based on a queue, not a stack algorithm.

4. Clock replacement algorithm
The performance of the LRU algorithm is close to that of the OPT, but it is difficult to implement and has a large overhead; the FIFO algorithm is simple to implement, but has poor performance. Therefore, the designers of the operating system have tried many algorithms, trying to approach the performance of the LRU with a relatively small overhead. These algorithms are all variants of the CLOCK algorithm.

The simple CLOCK algorithm is to associate an additional bit to each frame, which is called the use bit. When a page is loaded into the main memory for the first time, the use bit of the frame is set to 1; when the page is subsequently accessed, its use bit is also set to 1. For the page replacement algorithm, the set of candidate frames for replacement is regarded as a circular buffer, and a pointer is associated with it. When a page is replaced, the pointer is set to point to the next frame in the buffer. When a page needs to be replaced, the operating system scans the buffer to find a frame where the use bit is set to 0. Whenever a frame with a usage bit of 1, the operating system resets the bit to 0; if at the beginning of this process, the usage bits of all frames in the buffer are 0, then the first encountered One frame replacement; if the used bits of all frames are 1, the pointer circulates in the buffer for a complete cycle, all used bits are set to 0, and they stay in the original position to replace the page in the frame. Because this algorithm checks the condition of each page cyclically, it is called the CLOCK algorithm, also known as the Not Recently Used (NRU) algorithm.

The performance of the CLOCK algorithm is closer to that of the LRU, and by increasing the number of bits used, the CLOCK algorithm can be made more efficient. Add a modified bit on the basis of the used bit to get an improved CLOCK replacement algorithm. In this way, each frame is in one of the following four situations:

It has not been visited recently and has not been modified (u=0, m=0).
Recently visited, but not modified (u=1, m=0).
It has not been visited recently, but has been modified (u=0, m=1).
Recently visited and modified (u=1, m=1).

The algorithm performs the following steps:

Starting from the current position of the pointer, scan the frame buffer. During this scan, no modification is made to the used bits. Select the first frame encountered (u=0, m=0) for replacement.
If step 1) fails, scan again to find (u=0, m=1) frames. The first such frame encountered is selected for replacement. In this scanning process, for each skipped frame, set its use bit to 0.
If step 2) fails, the pointer will return to its original position, and the used bits of all frames in the set are 0. Repeat step 1, and if necessary, repeat step 2. This will find a frame for replacement.

The improved CLOCK algorithm is superior to the simple CLOCK algorithm in that pages that have not changed are preferred when replacing. Since modified pages must be written back before being replaced, this saves time.