操作系统 页面置换的三种算法（OPT最佳、LRU最近未使用、FIFO先进先出（C++）_页面走向个数

算法概念

实现代码如下：
最佳置换算法OPT

#include <deque>
#include <cstdio>//cstdio是c++从C的stdio.h继承来的，两者内容都一样，只不过cstdio头文件中定义的名字被定义在命名空间std中。
//在C++中要尽量避免C风格的出现, 因此需要使用 #include <cstdio>.
#include <algorithm>//算法头文件 里面有好多种算法
#include<iostream>
using namespace std;
struct opt
{
	int value;
	int time;
};
const int maxn = 105;
int a[maxn];
int main()
{
	deque<opt>  dq;
	deque<opt>::iterator pos;
	int numyk, numqueye = 0;
	printf("请输入物理页框块数:\n");
	cin >> numyk;
	int n;
	printf("请输入页面走向个数：\n");
	cin >> n;
	printf("请输入页面号引用串，以空格隔开：\n");
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
	{
		printf("第%d次\n", i+1);
		int in;
		in = a[i];
		if (dq.size() < numyk)//存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos).value == in)//存在元素和它相同
				{
					flag = 1;
					break;
				}  //存在该元素
			if (!flag) //不存在此元素
			{
				numqueye++;
				opt temp;
				temp.value = in;
				int f = 0;
				for (int j = i + 1; j < n; j++)
					if (a[j] == in)
					{
						f = 1;
						temp.time = j - i;
						break;
					}
				if (!f)
					temp.time = n;
				dq.push_back(temp);
			}
		}
		else //不存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos).value == in)//存在该元素
				{
					flag = 1;
					break;
				}  
			if (!flag) //不存在此元素 则置换time最大的项
			{
				numqueye++;//缺页数+1
				int m = dq.front().time;
				//printf("第一个元素的下次间隔为%d\n", m);
				
				deque<opt >::iterator mp = dq.begin();  //初始化 否则有可能erase找不到对象崩溃 
				for (pos = dq.begin(); pos != dq.end(); pos++)
				{
					printf("页面%d 距离下一次出现的间隔%d\n", (*pos).value, (*pos).time);
					if ((*pos).time > m)//找队列中time最大的元素
					{
						//printf("迭代\n");
						mp = pos;//把队列中time最大的元素赋给mp
						m = (*pos).time;//更新队列中最大time的值

					}
				}
				opt temp;
				temp.value = in;
				int f = 0;
				cout << "插入" << in << "替换" << (*mp).value << endl;
				dq.erase(mp);//从队列指定的元素位置删除元素，可以指定一个范围删除。

				for (int j = i + 1; j < n; j++)//记录新插入元素的time
					if (a[j] == in)
					{
						f = 1;
						temp.time = j - i;
						break;
					}
				if (!f)
					temp.time = n;
				dq.push_back(temp);
			}
		}
		//每次之后重置 记录队列中元素的time
		cout<< "队列为";
		for (pos = dq.begin(); pos != dq.end(); pos++)
		{
			cout << (*pos).value << " ";
			int f = 0;
			for (int j = i + 1; j < n; j++)
				if (a[j] == (*pos).value)
				{
					f = 1;
					(*pos).time = j - i;
					break;
				}
			if (!f)
				(*pos).time = n;
		}cout << endl;

	}
	printf("opt缺页次数为:%d\n", numqueye);
	printf("opt缺页中断率为：%lf\n", (double)numqueye * 1.0 / n);
}
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

OPT控制台实现如下
物理页框数：3
页面走向个数：20
页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

最近最久未使用LRU
和OPT代码很类似，因为一个是向后找一个是向前找

#include <deque>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
struct opt
{
	int value; //值
	int time;  //时间
};
const int maxn = 105;
int a[maxn];
int main()
{
	deque<opt>  dq;
	deque<opt >::iterator pos;
	int numyk, numqueye = 0;
	printf("请输入物理页框块数:\n");
	cin >> numyk;
	int n;
	printf("请输入页面走向个数：\n");
	cin >> n;
	printf("请输入页面号引用串，以空格隔开：\n");
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
	{
		int in;
		in = a[i];
		if (dq.size() < numyk)//存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos).value == in)//存在元素和它相同
				{
					flag = 1;
					break;
				}  //存在该元素
			if (!flag) //不存在此元素
			{
				numqueye++;
				opt temp;
				temp.value = in;
				temp.time = 0;
				dq.push_back(temp);
			}
		}
		else //不存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos).value == in)
				{
					flag = 1;
					break;
				}  //存在该元素
			if (!flag) //不存在此元素
			{
				numqueye++;//缺页数+1
				int m = dq.front().time;
				deque<opt >::iterator mp = dq.begin();  //注意此处千万注意初始化 否则有可能erase找不到对象崩溃
				for (pos = dq.begin(); pos != dq.end(); pos++)
				{
					printf("%d %d\n", (*pos).value, (*pos).time);
					if ((*pos).time > m)
					{
						printf("迭代");
						mp = pos;//时间最大的元素的位置
						m = (*pos).time;

					}
				}
				printf("此时队列中所剩时间最长的元素为%d\n", (*mp).value);
				opt temp;
				temp.value = in;
				int f = 0;
				dq.erase(mp);
				temp.time = 0; //加进来之后
				dq.push_back(temp);
			}
		}
		//每次之后各对象的time
		for (pos = dq.begin(); pos != dq.end(); pos++)
		{
			printf("队列中的元素为 %d\n", (*pos).value);
			int f = 0;
			for (int j = i; j >= 0; j--)
				if (a[j] == (*pos).value)
				{
					(*pos).time = i - j;
					break;
				}
			printf("距离上次时间为%d\n", (*pos).time);
		}

	}
	printf("lru缺页次数为:%d\n", numqueye);
	printf("lru缺页中断率为：%lf\n", (double)numqueye * 1.0 / n);
}
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

LRU控制台实现如下
物理页框数：3
页面走向个数：20
页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1




先进先出FIFO算法
代码实现如下

#include <deque>
#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
int main()
{
	deque<int>  dq;//创建一个空容器dq 随机访问数组类型 支持两头快速插入删除
	deque<int >::iterator pos;//迭代器是一种检查容器内元素并遍历元素的数据类型。
	int numyk, numqueye = 0;
	printf("请输入物理页框块数:\n");
	cin >> numyk;
	int n;
	printf("请输入页面走向个数：\n");
	cin >> n;
	printf("请输入页面号引用串，以空格隔开：\n");
	for (int i = 0; i < n; i++)
	{
		int in;
		cin >> in;
		if (dq.size() < numyk)//存在空余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++) //遍历队列 查找deque中是否有此值
				if ((*pos) == in)
				{
					flag = 1;
					break;
				}
			if (!flag) //不存在此元素
			{
				numqueye++;
				dq.push_back(in);//放入队列 
			}

		}
		else //不存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos) == in)
				{
					flag = 1;
					break;//存在该元素
				}  
			if (!flag) //不存在此元素 则置换最先进入的项 
			{
				numqueye++;
				dq.pop_front();//最先进入的出队列 
				dq.push_back(in);//从容器尾进队列 
			}
		}

	}
	printf("fifo缺页次数为:%d\n", numqueye);
	printf("fifo缺页中断率为：%lf\n", (double)numqueye * 1.0 / n);
}
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

FIFO控制台实现如下
物理页框数：3
页面走向个数：20
页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1