模拟实现页面置换算法（OPT、FIFO、LRU）C++代码

一、C++代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_set>
#include <ctime>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;//执行序列最大长度
const int M = 10;//内存块最大数量
int len;//执行序列长度
int seq[N];//执行序列
int sz;//内存块数量
PII flag[M];

void OPT()
{
	unordered_set<int> st;//记录所有内存块中的页面号
	int cnt = 0;//缺页中断次数
	int idx = 0;
	for (int i = 0; i < len; i++)
		if (!st.count(seq[i]))//当前要访问的页面不在内存块中
		{
			if (st.size() < sz) st.insert(seq[i]), flag[idx++] = { i, seq[i] };
			else
				for (int j = i + 1; j < len; j++)
				{
					int t = 0;
					if (st.count(seq[j]))
						for (int k = 0; k < idx; k++)
							if (flag[k].second == seq[j])
							{
								flag[k].first = j;
								t++;
								break;
							}
					if (t == 3 || j == len - 1)
					{
						sort(flag, flag + idx);
						st.erase(flag[0].second);
						st.insert(seq[i]);
						flag[0] = { i, seq[i] };
					}
				}
			cnt++;
		}
	cout << "最佳置换算法产生的缺页中断次数为 : " << cnt << "次\n";
}

void FIFO()
{
	unordered_set<int> st;
	queue<int> Q;
	int cnt = 0;
	for (int i = 0; i < len; i++)
		if (!st.count(seq[i]))
		{
			if (st.size() < sz) st.insert(seq[i]), Q.push(seq[i]);
			else
			{
				st.erase(Q.front());
				st.insert(seq[i]);
				Q.pop();
				Q.push(seq[i]);
			}
			cnt++;
		}
	cout << "先进先出置换算法产生的缺页中断次数为 : " << cnt << "次\n";
}

void LRU()
{
	unordered_set<int> st;
	int cnt = 0;
	int idx = 0;
	for (int i = 0; i < len; i++)
		if (!st.count(seq[i]))
		{
			if (st.size() < sz) st.insert(seq[i]), flag[idx++] = { i, seq[i] };
			else
			{
				sort(flag, flag + idx);
				st.erase(flag[0].second);
				st.insert(seq[i]);
				flag[0] = { i, seq[i] };
			}
			cnt++;
		}
		else
			for (int j = 0; j < idx; j++)
				if (flag[j].second == seq[i]) flag[j].first = i;
	cout << "最近最久未使用置换算法产生的缺页中断次数为 : " << cnt << "次\n";
}

int main()
{
	srand(time(0));
	len = rand() % 981 + 20;//随机产生20~1000的序列长度
	for (int i = 0; i < len; i++) seq[i] = rand() % 20;
	/*len = 20;
	seq[0] = 1, seq[1] = 2, seq[2] = 3, seq[3] = 4, seq[4] = 2
		, seq[5] = 1, seq[6] = 5, seq[7] = 6, seq[8] = 2, seq[9] = 1, seq[10] = 2
		, seq[11] = 3, seq[12] = 7, seq[13] = 6, seq[14] = 3, seq[15] = 2
		, seq[16] = 1, seq[17] = 2, seq[18] = 3, seq[19] = 6;*/
	cout << "页面执行序列 : ";
	for (int i = 0; i < len; i++) cout << seq[i] << ' ';
	for (int i = 0; i < 3; i++)
	{
		cout << endl << "请输入内存块数量 : ";
		cin >> sz;
		cout << endl;
		OPT();
		FIFO();
		LRU();
	}
	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
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

二、运行结果展示