What page replacement algorithm is fifo?

fifo refers to the first-in-first-out page replacement algorithm. The page that is first transferred into the memory for each replacement is the page that has the longest waiting time in the memory. Advantages: It is relatively simple to implement and does not require hardware support, so there is no need to increase the cost of the system.

The operating environment of this tutorial: Windows 10 system, Dell G3 computer.

fifo (first in, first out page replacement algorithm)

Basic idea: Prioritize the page that enters the memory earliest, That is, the page that has resided in memory the longest.

This algorithm is simple to implement. You only need to link the pages transferred into the memory into a queue according to the order, and set a pointer to always point to the earliest page. However, this algorithm is not suitable for the actual running rules of the process, because some pages are frequently accessed during the process.

Implementation process:

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. The FIFO algorithm is used for page replacement. When the process accesses page 2, page 7, which enters the memory earliest, is swapped out. Then when page 3 is accessed, the page 2, 0, 1 that first enters the memory is swapped out. As can be seen from the figure below, 12 page replacements are performed when using the FIFO algorithm.

##00777Physical Block 20 00333 222Physical Block 31000332##2√√√## Disadvantages: The FIFO algorithm will also produce an increase in the number of allocated physical blocks. The abnormal phenomenon in which the number of page faults increases instead of decreasing was discovered by Belady in 1969, so it is called the Belady anomaly, as shown in the figure below. Only the FIFO algorithm may experience Belady anomalies, while the LRU and OPT algorithms will never experience Belady anomalies. For more related knowledge, please visit the FAQ column!

Visit page	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
Physical Block 1	7	7	7	2		2	2	4	4	4	0
													##1	1			1	0	0
		##1			1								3				2	1		Missing Page No
√	√	√			√	√	√	√	√			##√	√			√	√

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