操作系统-最佳置换算法（OPT）实现_opt最佳页面置换算法

• 算法思想
  OPT算法在每次需要进行页面置换时，会选择当前内存中包含的所有页面中，未来最长时间内不会被访问的页面进行替换。

• 算法特点
  是所有算法中耗时最短的一种算法，但是在实际情况中基本无法实现，其原因是未知未来多久哪些页面会被访问，哪些页面不会被访问，故实现起来十分困难，但可以用作其他算法优良的参考，还能起到鉴别其他算法合理性。

• 算法实现
  1）当需要进行页面置换时，对当前物理块中的所有页面进行扫描。
  2）对于每个页面，计算它在未来又一次被访问的时间节点。
  3）选择具有最长不访问时间的页面进行置换。

注：本文将一开始向空的物理块调入页面也作为缺页处理，可能会与其他文章有所不同。

#include<bits/stdc++.h>
using namespace std;
int arr[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};//测试数据
int page[3] = {7,0,1};//假设有三个物理块，可以根据实际需求进行修改
void OPT() {
	int pos[3] = {0,1,2};//记录初始位置
	int cishu = 3;//表示页面缺页的次数，初始值为3
	bool flag[3] = {false,false,false};
	for(int arr_pos = 3; arr_pos<sizeof(arr)/sizeof(arr[0]); arr_pos++) {
		bool change = true;
		flag[0] =false,flag[1] = false,flag[2] = false;
		for(int i = 0; i<3; i++) {
			cout<<"arr_pos:"<<arr_pos<<"值:"<<arr[arr_pos]<<" i: "<<i<<" 值: "<<page[i]<<endl;
			if(page[i]==arr[arr_pos])change = false; //页面有这个块号
		}
		if(change==true)continue;
		for(int i = 3; i<sizeof(arr)/sizeof(arr[0]); i++) {
			for(int j = 0; j<3; j++) {
				if(arr[i]==page[j]&&flag[j]==false) {
					pos[j] = i;
				}
			}
		}
		int now = -1;
		//找最大
		if(pos[0]<pos[1]) {
			if(pos[1]<pos[2]) {
				now = 2;
			} else {
				now = 1;
			}
		} else {
			if(pos[0]<pos[2]) {
				now = 2;
			} else {
				now = 0;
			}
		}
		page[now] = arr[arr_pos];
		cishu++;
	}
	cout<<"缺页次数："<<cishu<<" 缺页率："<<(float)cishu/(float)(sizeof(arr)/sizeof(arr[0]))<<endl;
}
int main() {
	OPT();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

实验结果如下：

本文结束，希望上述的代码对你理解OPT算法有所帮助，如有出现错误的地方，还请批评指正，谢谢
如果你对操作系统其他的页面置换算法实现存在疑问，可以查看下列博客：

• 操作系统-先进先出算法（FIFO）实现