操作系统 | 实验五 页面置换算法_页面置换算法实验

一、实验目的

（1）加深对页面置换算法的理解。
（2）掌握几种页面置换算法的实现方法。
（3）通过实验比较各种置换算法的优劣。

二、实验内容

参考用C语言实现的先进先出算法FIFO的代码，实现最佳置换算法OPT和最近最少使用算法LRU。使得随机给出一个页面执行序列，计算不同置换算法的缺页数，缺页率和命中率。

三、数据结构

typedef struct item
{
int num; //页号
int time; //等待时间，LRU算法会用到这个属性
}Pro;
全局变量：
int pageNum = 0; //系统分配给作业的主存中的页面数
int memoryNum = 0; //可用内存页面数

1、函数以及功能

四、程序流程图

五、实验代码

#include <stdio.h>
#include <stdlib.h>

#define SYSINFO "页面置换算法" // 系统信息 
#define AUTHOR "Yrani - 依然" //作者 

/**
* 	@Author: Yrani - 依然
* 	@Date: 2022-05-2 20:20:17
* 	@LastEditTime: 2022-05-03 15:55:00
* 	@keywords: 页面置换算法、LRU、OPT、FIFO 
**/

typedef struct item
{
	int num;        //页号
	int time;        //等待时间，LRU算法会用到这个属性
} Pro;

int pageNum = 0;        //系统分配给作业的主存中的页面数
int memoryNum = 0;        //可用内存页面数

void PrintCurrentPage(Pro* page1);        //打印当前主存中的页面
int Search(int num1, Pro* memory1);    //在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int Max(Pro* memory1);
int Optimal(int num,int tag,Pro* memory1,Pro* page1);

//信息展示
void DisplayInfo()
{
	printf("★★★★★★★★★★★★★★★★★\n");
	printf("★☆☆☆☆%s☆☆☆☆☆☆★\n",SYSINFO);
	printf("☆☆☆☆☆@Author:%s☆☆☆☆★\n",AUTHOR);
	printf("★★★★★★★★★★★★★★★★★\n");
}

void PrintCurrentPage(Pro *memory1)//打印当前的页面
{
	int j = 0;

	for(j = 0; j < memoryNum; j++)
		printf("      %d     ", memory1[j].num);
	printf("\n");
}

//在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int  Search(int num1,Pro *memory1)
{
	int j;

	for(j=0; j < memoryNum; j++)
	{
		if(num1==memory1[j].num)
			return j;
	}
	return -1;
}

int Max(Pro *memory1)
{
	int max = 0;

	for(int k=1; k < memoryNum; k++)
	{
		if(memory1[k].time > memory1[max].time)
			max = k;
	}
	
	return max;
}

int Optimal(int num, int tag, Pro *memory1, Pro *page1)
{
	int k, j, min[100], min_k;
	for(k = 0; k < memoryNum; k++)
	{
		min[k] = 500;
	}
	
	for(k = 0; k < memoryNum; k++)
	{
		j = tag;
		do
		{

			j++;
			if(j>20)
				break;
		}
		while(page1[j].num != memory1[k].num);
		if(j < min[k])
		{

			min[k] = j;
		}
	}
	int max = 0;
	for(int t = 1; t < memoryNum; t++)
	{
		if(min[t] > min[max])
			max = t;
	}
	return max;
}

int main()
{
	int i = 0;
	int curmemory = 0;        //调入主存中的页面个数
	int missNum = 0;        //缺页次数
	float missRate = 0.0;        //缺页率
	char c;                //得到用户的输入字符，来选择相应的置换算法

	Pro* page = NULL;            //作业页面集
	Pro* memory = NULL;        //内存页面集
	
	DisplayInfo(); 
	
	printf("输入系统分配给作业的主存中的页面数:");
	scanf("%d", &pageNum);
	printf("输入内存页面数:");
	scanf("%d", &memoryNum);

	page = (Pro*)malloc(sizeof(Pro)*pageNum);
	memory = (Pro*)malloc(sizeof(Pro)*memoryNum);

	for(i = 0; i < pageNum; i++)
	{
		printf("第 %d 个页面号为:", i);
		scanf("%d", &page[i].num);
		page[i].time=0;            //等待时间开始默认为0
	}

	do
	{
		for(i = 0; i < memoryNum; i++)      //初始化内存中页面
		{
			memory[i].num = -1;                //页面为空用-1表示
			memory[i].time = -1;                //
		}

		printf("*****f:FIFO页面置换*****\n");
		printf("*****o:OPT页面置换*****\n");
		printf("*****l:LRU页面置换*****\n");
		printf("*****请选择操作类型(f,o,l),按其它键结束******\n");
		fflush(stdin);
		scanf("%c", &c);

		i = 0;
		curmemory = 0;

		if(c == 'f')            //FIFO页面置换
		{
			missNum = 0;

			printf("FIFO页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0; i < memoryNum; i++)
			{
				printf("物理块号%d  ",i+1);
			}
			printf("\n===============================================================\n");
			for(i=0; i<pageNum; i++)
			{
				if(Search(page[i].num,memory) < 0)//若在主存中没有找到该页面
				{
					missNum ++;
					if(memory[curmemory].num > -1)
					{
						printf("   %d      ", memory[curmemory].num);
					} 
					else
					{
						printf("          ");
					}
					memory[curmemory].num = page[i].num;
					PrintCurrentPage(memory);
					curmemory = (curmemory + 1) % memoryNum;
					printf("===============================================================\n");
				}
			}//end for
			missRate = (float)missNum / pageNum;
			printf("缺页次数：%d   缺页率:  %f\n", missNum, missRate);

		}//end if

		if(c == 'o')            //OPT页面置换
		{
			missNum = 0;

			printf("OPT页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0;  i< memoryNum; i++)
			{
				printf("物理块号%d  ", i+1);
			}
			printf("\n===============================================================\n");
			for(i = 0; i < pageNum; i++)
			{
				if(Search(page[i].num,memory) < 0)//若在主存中没有找到该页面
				{
					if(i < memoryNum)
						curmemory = i;
					else
						curmemory = Optimal(page[i].num,i,memory,page);
					missNum ++;
					if(memory[curmemory].num > -1)
					{
						printf("   %d      ",memory[curmemory].num);
					}
					else
					{
						printf("          ");
					}
					memory[curmemory].num = page[i].num;
					PrintCurrentPage(memory);
					curmemory = (curmemory+1) % memoryNum;
					printf("===============================================================\n");
				}
			}//end for
			missRate = (float)missNum / pageNum;
			printf("缺页次数：%d   缺页率:  %.2f%%\n", missNum, missRate*100);


		}//end if

		if(c=='l')            //LRU页面置换
		{
			missNum = 0;

			printf("LRU页面置换情况:   \n");
			printf("置换的页面号  ");
			for(i = 0; i < memoryNum; i++)
			{
				printf("物理块号%d  ", i+1);
			}
			printf("\n===============================================================\n");
			for(i =0; i < pageNum; i++)
			{
				for(int j=0; j<memoryNum; j++)
				{
					if(memory[j].num>=0)
						memory[j].time++;
				}
				if(Search(page[i].num,memory)<0)//若在主存中没有找到该页面
				{
					missNum ++;
					//    Printf("%d \n",curmemory);
					if(i<3)
						curmemory = i;
					else
						curmemory = Max(memory);
					if(memory[curmemory].num>-1)
					{
						printf("   %d      ",memory[curmemory].num);
					}
					else
					{
						printf("          ");
					}
					memory[curmemory].num=page[i].num;
					memory[curmemory].time = 0;
					PrintCurrentPage(memory);
					curmemory = (curmemory+1)%memoryNum;
					printf("===============================================================\n");
				}
				else
				{
					curmemory = Search(page[i].num,memory);
					memory[curmemory].time=0;
					curmemory = (curmemory+1)%memoryNum;
				}

			}//end for
			missRate = (float)missNum/pageNum;
			printf("缺页次数：%d   缺页率:  %.2f%%\n", missNum, missRate*100);



		}//end if

	}while(c=='f'||c=='l'||c=='o');
	
	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
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

六、实验结果

系统信息展示

输入页面序列数

输入内存页面数

输入20个页面号

首先选择FIFO算法

OPT页面置换算法

LRU页面置换算法

按其他键退出即可

七、实验体会总结

总结与体会：

1. 通过本次实验加深了我对页面置换算法的理解，本次实验中的页面置换算法有
   FIFO（先进先出置换算法）、LRU（最近最少使用页面置换算法）、OPT（最佳置换算法）。
2. FIFO算法的核心思想是置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。
3. LRU算法的核心思想是置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。LRU算法普偏地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。
4. OPT算法的核心思想是置换以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低。缺点：该算法需要依据以后各业的使用情况，而当一个进程还未运行完成是，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。
5. 这三种算法对比：OPT > LRU > FIFO 但是OPT算法是不能实现的，但该算法仍然有意义，可以作为其他算法优劣的一个标准。
6. 此次实验难度相较于前面几次难度较大，代码较难调试，还是需要多加思考和练习。