5种页面置换算法的简单实现

页面置换算法

OPT

最佳置换算法

  • 缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）；
  • 优点：最佳置换算法可以保证获得最低的缺页率，性能最好
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
void opt() //最佳转换算法，往后查找
{
	printf("--------------------------------\n");
	printf("现在执行的是最佳置换算法opt：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, tot = 0, z = 0, three = 0;
	int flag[8];
	memset(flag, 0, sizeof(flag)); //初始化一个flag数组，来确定最晚出现需要替换的点
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			showdata(); 
		}
		else //当数组填充满后
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
			}
			if (z == 0)
			{
				for (int k = i + 1; k < M; k++) //从下一位向后查找 
				{
					for (j = 0; j < N; j++)
					{
						if (arr[j] == pageNum[k] && three < (N-1)) //此位先出现则标记此位
						{
							if (flag[arr[j]] == 1)
								continue;
							flag[arr[j]] = 1;							
							three++;
						}
					}
				}
				for (int l = 0; l < N; l++) //遍历确定最长时间未被访问的页面
				{
					if (flag[arr[l]] == 1)
						continue;
					else         
					{
						arr[l] = pageNum[i];
						tot++;
						showdata();
					}
				}
			}
			z = 0;
			three = 0;
			memset(flag, 0, sizeof(flag));
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("OPT缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

FIFO

先进先出算法

  • 优点：先进先出算法实现简单，是最直观的一个算法
  • 缺点：先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少
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
//FIFO先进先出算法
void fifo()
{
	printf("--------------------------------\n");
	printf("现在执行的是FIFO先进先出算法：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, z = 0, change = 0;
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (arr[j] == pageNum[i])
				z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
		}
		if (z == 0)
		{
			change++;
			arr[no++] = pageNum[i];
			showdata();
		}
		z = 0; //默认需要调度
		if (no == N) //队列已满，则归0从头开始，等效于队头出队
			no = 0;
	}
	printf("页面置换的次数为：%d\n", change);
	double rate = (double)change / M * 100;
	printf("FIFO缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

LFU

最少使用置换算法

  • 缺点：并不能真正反映出页面的真实情况
  • 优点：该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性
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
void lfu() //最不经常使用算法，使用次数最少算法
{
	printf("--------------------------------\n");
	printf("现在执行的是最不经常使用算法lfu：\n");
	int count[8], tot = 0, no = 0, z = 0, least = 100, mark = -1;
	memset(arr, -1, sizeof(arr));
	memset(count, 0, sizeof(count)); //用count数组记录访问次数，当访问次数相同时
	for (i = 0; i < M; i++)          //默认取索引较小的一位
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			count[pageNum[i]]++;
			showdata();
		}
		else
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
				{
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
					count[pageNum[i]]++;
				}
			}
			if (z == 0)
			{
				for (int k = 0; k < N; k++) //通过循环比较出目前访问次数最小的页面进程
				{
					if (count[arr[k]] < least)
					{
						least = count[arr[k]];
						mark = k;
					}
				}
				arr[mark] = pageNum[i];
				showdata();
				tot++;
				count[pageNum[i]]++;
			}
			z = 0;
			least = 100;
			mark = -1;
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("LFU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

LRU

最近最久未使用置换算法

  • 优点：由于考虑程序访问的时间局部性，一般能有较好的性能；实际应用多
  • 缺点：实现需要较多的硬件支持，会增加硬件成本
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
void lru() //最近最久未访问算法，从当前位往前查找
{
	printf("--------------------------------\n");
	printf("现在执行的是最近最久未访问算法lru：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, tot = 0, z = 0, three = 0;
	int flag[8];
	memset(flag, 0, sizeof(flag)); //初始化一个flag数组，来确定最晚出现需要替换的点
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			showdata();
		}
		else //当数组填充满后
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
			}
			if (z == 0)
			{
				for (int k = i - 1; k >= 0; k--) //从上一位向前查找 
				{
					for (j = 0; j < N; j++)
					{
						if (arr[j] == pageNum[k] && three < (N - 1)) //此位先出现则标记此位
						{
							if (flag[arr[j]] == 1)
								continue;
							flag[arr[j]] = 1;
							three++;
						}
					}
				}
				for (int l = 0; l < N; l++) //遍历确定最长时间未被访问的页面
				{
					if (flag[arr[l]] == 1)
						continue;
					else
					{
						arr[l] = pageNum[i];
						tot++;
						showdata();
					}
				}
			}
			z = 0;
			three = 0;
			memset(flag, 0, sizeof(flag));
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("LRU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

NRU

最近未用/时钟算法

  • 优点：性能和开销比较均衡
  • 缺点：未考虑页面是否被修改过
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
void nru() //clock置换算法/最近未用算法/NRU算法
{
	printf("--------------------------------\n");
	printf("现在执行的是clock置换算法nru：\n");
	int ask[10], no = 0, tot = 0, z = 0, mark = 0;
	memset(arr, -1, sizeof(arr));
	memset(ask, 0, sizeof(ask)); //ask数组标记是否访问，1代表最近访问，0代表未访问
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			ask[no] = 1; //初始化为最近访问
			arr[no++] = pageNum[i];
			tot++;
			showdata();
		}
		else
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
				{
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
					ask[j] = 1; //同时更新最近访问
				}
			}
			if (z == 0)
			{
				int k = 0;
				while (1) //通过循环找出访问位为0
				{
					for (k = 0; k < N; k++)
					{
						if (ask[k] == 0)
							goto flag;
						else if (ask[k] == 1)
							ask[k] = 0;
					}
				}
				flag:
				arr[k] = pageNum[i];
				ask[k] = 1;
				showdata();
				tot++;
			}
		}
		z = 0;
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("NRU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

代码实现(C语言)

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
#include <stdio.h>
#include <stdlib.h>

#define N 3
#define M 20
int i, j;
int arr[N];
int pageNum[M] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 };

void showdata()
{
	for (int i = 0; i < N; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//FIFO先进先出算法
void fifo()
{
	printf("--------------------------------\n");
	printf("现在执行的是FIFO先进先出算法：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, z = 0, change = 0;
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (arr[j] == pageNum[i])
				z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
		}
		if (z == 0)
		{
			change++;
			arr[no++] = pageNum[i];
			showdata();
		}
		z = 0; //默认需要调度
		if (no == N) //队列已满，则归0从头开始，等效于队头出队
			no = 0;
	}
	printf("页面置换的次数为：%d\n", change);
	double rate = (double)change / M * 100;
	printf("FIFO缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

void opt() //最佳转换算法，往后查找
{
	printf("--------------------------------\n");
	printf("现在执行的是最佳置换算法opt：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, tot = 0, z = 0, three = 0;
	int flag[8];
	memset(flag, 0, sizeof(flag)); //初始化一个flag数组，来确定最晚出现需要替换的点
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			showdata(); 
		}
		else //当数组填充满后
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
			}
			if (z == 0)
			{
				for (int k = i + 1; k < M; k++) //从下一位向后查找 
				{
					for (j = 0; j < N; j++)
					{
						if (arr[j] == pageNum[k] && three < (N-1)) //此位先出现则标记此位
						{
							if (flag[arr[j]] == 1)
								continue;
							flag[arr[j]] = 1;							
							three++;
						}
					}
				}
				for (int l = 0; l < N; l++) //遍历确定最长时间未被访问的页面
				{
					if (flag[arr[l]] == 1)
						continue;
					else         
					{
						arr[l] = pageNum[i];
						tot++;
						showdata();
					}
				}
			}
			z = 0;
			three = 0;
			memset(flag, 0, sizeof(flag));
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("OPT缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

void lru() //最近最久未访问算法，从当前位往前查找
{
	printf("--------------------------------\n");
	printf("现在执行的是最近最久未访问算法lru：\n");
	memset(arr, -1, sizeof(arr));
	int no = 0, tot = 0, z = 0, three = 0;
	int flag[8];
	memset(flag, 0, sizeof(flag)); //初始化一个flag数组，来确定最晚出现需要替换的点
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			showdata();
		}
		else //当数组填充满后
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
			}
			if (z == 0)
			{
				for (int k = i - 1; k >= 0; k--) //从上一位向前查找 
				{
					for (j = 0; j < N; j++)
					{
						if (arr[j] == pageNum[k] && three < (N - 1)) //此位先出现则标记此位
						{
							if (flag[arr[j]] == 1)
								continue;
							flag[arr[j]] = 1;
							three++;
						}
					}
				}
				for (int l = 0; l < N; l++) //遍历确定最长时间未被访问的页面
				{
					if (flag[arr[l]] == 1)
						continue;
					else
					{
						arr[l] = pageNum[i];
						tot++;
						showdata();
					}
				}
			}
			z = 0;
			three = 0;
			memset(flag, 0, sizeof(flag));
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("LRU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

void lfu() //最不经常使用算法，使用次数最少算法
{
	printf("--------------------------------\n");
	printf("现在执行的是最不经常使用算法lfu：\n");
	int count[8], tot = 0, no = 0, z = 0, least = 100, mark = -1;
	memset(arr, -1, sizeof(arr));
	memset(count, 0, sizeof(count)); //用count数组记录访问次数，当访问次数相同时
	for (i = 0; i < M; i++)          //默认取索引较小的一位
	{
		if (no < N) //填充空数组 
		{
			arr[no++] = pageNum[i];
			tot++;
			count[pageNum[i]]++;
			showdata();
		}
		else
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
				{
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
					count[pageNum[i]]++;
				}
			}
			if (z == 0)
			{
				for (int k = 0; k < N; k++) //通过循环比较出目前访问次数最小的页面进程
				{
					if (count[arr[k]] < least)
					{
						least = count[arr[k]];
						mark = k;
					}
				}
				arr[mark] = pageNum[i];
				showdata();
				tot++;
				count[pageNum[i]]++;
			}
			z = 0;
			least = 100;
			mark = -1;
		}
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("LFU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

void nru() //clock置换算法/最近未用算法/NRU算法
{
	printf("--------------------------------\n");
	printf("现在执行的是clock置换算法nru：\n");
	int ask[10], no = 0, tot = 0, z = 0, mark = 0;
	memset(arr, -1, sizeof(arr));
	memset(ask, 0, sizeof(ask)); //ask数组标记是否访问，1代表最近访问，0代表未访问
	for (i = 0; i < M; i++)
	{
		if (no < N) //填充空数组 
		{
			ask[no] = 1; //初始化为最近访问
			arr[no++] = pageNum[i];
			tot++;
			showdata();
		}
		else
		{
			for (j = 0; j < N; j++)
			{
				if (arr[j] == pageNum[i])
				{
					z = 1; //如果队列里已经存在此进程，则无需再进行页面调度
					ask[j] = 1; //同时更新最近访问
				}
			}
			if (z == 0)
			{
				int k = 0;
				while (1) //通过循环找出访问位为0
				{
					for (k = 0; k < N; k++)
					{
						if (ask[k] == 0)
							goto flag;
						else if (ask[k] == 1)
							ask[k] = 0;
					}
				}
				flag:
				arr[k] = pageNum[i];
				ask[k] = 1;
				showdata();
				tot++;
			}
		}
		z = 0;
	}
	printf("页面置换的次数为：%d\n", tot);
	double rate = (double)tot / M * 100;
	printf("NRU缺页率为：%.2lf%%\n", rate);
	printf("--------------------------------\n");
}

int main()
{
	fifo(); //先进先出算法
	opt(); //最佳转换算法
	lru(); //最近最久未使用
	lfu(); //最不经常使用算法
	nru(); //clock置换算法

	return 0;
}