操作系统--页面置换算法（三种置换算法） C++高效实现 附代码_三种页面置换算法代码

运行示例：

物理块大小初始化为4，待IO数据为：1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2

• 最佳置换算法
  
• 先来先服务置换算法
  
• 最近最久未使用置换算法
  

代码示例

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>

using namespace std;

class page_replacement {
private:
	//OPT数据结构
	typedef struct opt {
		int next = 99999; //与此相同的下一个数据
		int order = -1; //页面序号
	}opt;
	//FIFO数据结构
	typedef struct fifo {
		int first = -1; //最早到达页号
		int order = -1; //页面序号
	}fifo;
	//LRU数据结构
	typedef struct lru {
		int recent = 0x80;  //时间戳
		int order = -1;
	}lru;
	//int data;
	
public:
	//构造函数
	page_replacement() {
		cout << "Object is being created!" << endl;
	}//page_replacement
	//析构函数
	~page_replacement() {
		cout << "\nObject is being deleted!" << endl;
	}//~page_replacement
	void OPT();
	void FIFO();
	void LRU();
	void format(int len);
	template<typename T1, typename T2>
	void printResult(int len, int ans, int cnt, T1 &rede, T1 &elim, T2 &block_tencent);
};

array<int, 17>order = { 1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2 };
//array<int, 20>order = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 };

//格式调整
void page_replacement::format(int len) {
	for (int i = 0; i < len; i++)
		cout << "- - ";
	cout << endl;
}//format

//page函数模板
template<class T1, class T2>
void page_replacement::printResult(int len, int ans, int cnt, T1 &rede, T1 &elim, T2 &block_content) {
	cout << "物理块页面内容：" << endl;
	format(len);
	for (int i = 0; i < len; i++) {
		if (i == 0)
			cout << "  " << order[i] << " ";
		else
			cout << ": " << order[i] << " ";
	}//for
	cout << endl;
	format(len);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < block_content.size(); j++) {
			if (block_content[j][i].order == -1) {
				cout << "    ";
				continue;
			}//if
			if (j - 1 >= 0 && block_content[j - 1][i].order == -1 || j == 0)
				cout << "  " << block_content[j][i].order << " ";
			else
				cout << ": " << block_content[j][i].order << " ";
		}//for
		cout << endl;
	}//for
	format(len);
	//迭代器
	cout << "换出页面序列：        ";
	for (auto iter = elim.begin(); iter != elim.end(); iter++)
		cout << iter->order << " ";
	cout << "\n换入页面序列：";
	for (auto iter = rede.begin(); iter != rede.end(); iter++)
		cout << iter->order << " ";
	float result = (float)(ans + cnt) / len;
	cout << "\n缺页次数：" << cnt << " | 页面置换次数：" << ans;
	cout << endl << "缺页率：" << result << endl;
}//printResult

//最佳置换算法
void page_replacement::OPT() {
	int len = order.size();
	int cnt = 0;  //缺页次数
	int ans = 0;  //页面置换
	vector<opt>opt_arr(len);
	vector<opt>rede; //换入
	vector<opt>elim; //换出
	array<opt, 4>block_memory; //物理块
	vector<array<opt, 4>>block_content;

	//初始化opt_arr
	for (int i = 0; i < len; i++) {
		opt_arr[i].order = order[i];
		int index = 0;
		for (int j = i+1; j < len; j++) {
			index++;
			if (opt_arr[i].order == order[j]) {
				opt_arr[i].next = index;
				break;
			}//if
		}//for
		cout << index << " ";
	}//for
	cout << endl;
	//页面调用
	for (int i = 0; i < len; i++) {
		//物理块空间充足
		if (i<4) {
			block_memory[i] = opt_arr[i];
			rede.push_back(opt_arr[i]);
			block_content.push_back(block_memory);
			ans++;
			for (int j = 0; j < i; j++)
				block_memory[j].next -= 1;
			continue;
		}//if
		//物理块空间不足,需要页面置换
		else {
			//如果物理块中存在该页面，直接引用即可
			bool flag = true;
			int index = 0;
			int future = -1;
			int tmp = future;
			for (int j = 0; j < 4; j++) {
				if (block_memory[j].order == opt_arr[i].order) {
					block_memory[j].next = opt_arr[i].next;
					flag = false;
					break;
				}//if
				else {
					tmp = max(tmp, block_memory[j].next);
					if (tmp > future) {
						future = tmp;
						index = j;
					}//if
				}//else
			}//for
			if (flag) {
				//置换页面
				elim.push_back(block_memory[index]);//换出页面
				block_memory[index] = opt_arr[i];
				rede.push_back(opt_arr[i]);//换入页面
				cnt++;  //缺页次数加1
			}//if
			for (int j = 0; j < 4; j++) {
				block_memory[j].next -= 1;
			}//for
			block_content.push_back(block_memory);
		}//else
	}//for
	cout << "\n\nOPT最佳置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//OPT

//先来先服务置换算法
void page_replacement::FIFO() {
	int len = order.size();
	int ans = 0;
	int cnt = 0;
	array<fifo, 4>block;  //物理块容量为4
	vector<array<fifo, 4>>block_content;
	vector<fifo>fifo_f(len);
	vector<fifo>elim, rede;

	//初始化
	for (int i = 0; i < len; i++) {
		fifo_f[i].order = order[i];
	}//for
	//页面调用
	for (int i = 0; i < order.size(); i++) {
		//物理块空间充足
		if (i < 4) {
			block[i].order = order[i];
			block[i].first += 1;
			rede.push_back(block[i]);
			block_content.push_back(block);
			for (int j = 0; j < i; j++) {
				block[j].first += 1;
			}//for
			ans++;
			continue;
		}//if
		//物理块空间不足
		else {
			bool flag = true;
			int index = 0;
			int max_fifo = -1;
			int tmp = max_fifo;
			//计算待换出的页面
			for (int j = 0; j < 4; j++) {
				if (block[j].order == fifo_f[i].order) {
					flag = false;
					break;
				}//if
				else {
					tmp = max(tmp, block[j].first);
					if (tmp > max_fifo) {
						max_fifo = tmp;
						index = j;
					}//if
				}//else
			}//for
			//置换页面
			if (flag) {
				elim.push_back(block[index]);
				block[index] = fifo_f[i];
				rede.push_back(fifo_f[i]);
				cnt++;
				for (int j = 0; j < 4; j++) {
					if (j == index)continue;
					block[j].first += 1;
				}//for
			}//if
			block_content.push_back(block);
		}//else
	}//for
	//输出置换结果
	cout << "\n\nFIFO先来先服务置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//FIFO

//最近最久未使用置换算法
void page_replacement::LRU() {
	int len = order.size();
	int ans = 0, cnt = 0;
	array<lru, 4>block;  //物理块容量为4
	vector<array<lru, 4>>block_content;
	vector<lru>lru_r(len);
	vector<lru>elim, rede;

	//初始化LRU
	for (int i = 0; i < len; i++) {
		lru_r[i].order = order[i];
	}//for
	//页面调用
	for (int i = 0; i < len; i++) {
		//物理块空间充足
		if (i < 4) {
			block[i] = lru_r[i];
			rede.push_back(block[i]);
			block_content.push_back(block);
			ans++;
			for (int j = 0; j < i; j++)
				block[i].recent >>= 1;
			for (int j = 0; j <= i; j++)
				cout << block[j].recent << " ";
			cout << endl;
		}//if
		//物理块空间不足
		else {
			bool flag = true;
			int last_no_used = 99999;
			int tmp = last_no_used;
			int index = 0;
			for (int j = 0; j < 4; j++)
				block[j].recent >>= 1;
			for (int j = 0; j < 4; j++) {
				if (block[j].order == lru_r[i].order) {
					block[j].recent |= 0x80;
					flag = false;
					break;
				}//if
				else {
					tmp = min(tmp, block[j].recent);
					if (tmp < last_no_used) {
						last_no_used = tmp;
						index = j;
					}//if
				}//else
			}//for
			if (flag) {
				elim.push_back(block[index]);
				rede.push_back(lru_r[i]);
				block[index] = lru_r[i];
				block[index].recent |= 0x80;
				cnt++;
			}//flag
			block_content.push_back(block);
		}//else
	}//for
	//输出置换结果
	cout << "\n\nLRU最近最久未使用置换算法\n";
	printResult(len, ans, cnt, rede, elim, block_content);
}//LRU

int main() {
	page_replacement page_r;
	page_r.OPT();
	page_r.FIFO();
	page_r.LRU();
	system("pause");
	return 0;
}//main
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306