In Virtual memory management, demostrate one of the page replacement algorithms.

 

Optimal permutation algorithm (OPT): remove pages that are never needed from main memory; if no such pages exist, select the pages that are not needed for the longest time. The selected obsolete page will never be used in the future, or will not be visited for the longest time, so as to ensure the minimum page missing rate.

The best permutation algorithm can be used to evaluate other algorithms. Assume that the system allocates three physical blocks to a process, and consider the following page number reference strings:

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 load the 7, 0, and 1 pages into memory. When the process wants to visit page 2, there is a page missing interrupt. According to the best replacement algorithm, select Page 7 that needs to be transferred in for the 18th visit to be eliminated. Then, when visiting page 0, there is no need to generate a page missing interrupt because it is already in 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 permutation algorithm is used.

As you can see, the number of page missing interrupts is 9, and the number of page replacement is 6.

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			2			2				7
Physical block 2		0	0	0		0		4			0			0				0
Physical block 3			1	1		3		3			3			1				1
Missing page	Y		Y	Y		Y		Y			Y			Y				Y