虚拟内存页面置换算法（OPT、FIFO、LRU）模拟与实现_页面置换算法的模拟

作者：Monodyee | 2024-02-29 03:18:12

踩

页面置换算法的模拟

前言

需要调入新页面时，选择内存中哪个物理页面被置换，称为置换策略。页面置换算法的目标：把未来不再使用的或短期内较少使用的页面调出，通常应在局部性原理指导下依据过去的统计数据进行预测，减少缺页次数。

一、常用的页面置换算法

1）最佳置换算法(OPT)：置换时淘汰“未来不再使用的”或“在离当前最远位置上出现的”页面。

2）先进先出置换算法(FIFO)：置换时淘汰最先进入内存的页面，即选择驻留在内存时间最长的页面被置换。

3）最近最久未用置换算法(LRU)：置换时淘汰最近一段时间最久没有使用的页面，即选择上次使用距当前最远的页面淘汰。

4）时钟算法(Clock)：也称最近未使用算法(NRU, Not Recently Used)，它是 LRU 和 FIFO 的折衷。

二、实验内容

(1)假设每个页面中可存放 10 条指令，分配给一作业的内存块（页框）数为 4。

(2)用 C 语言模拟一作业的执行过程，该作业共有 320 条指令，即它的地址空间为 32 页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时须记录缺页的次数，并将相应页调入内存;如果 4 个内存块中均已装入该作业，则需进行页面置换;最后显示其物理地址，并转下一条指令。在所有 320 条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

(3)置换算法请分别考虑 OPT、FIFO 和 LRU 算法。

(4) 测试用例(作业中指令序列)按下述原则生成:

通过随机数产生一个指令序列，共 320 条指令。
① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；

具体的实施方法是：
① 在[0, 319]的指令地址之间随机选取一起点 m；
② 顺序执行一条指令，即执行地址为 m+1 的指令；
③ 在前地址[0, m+1]中随机选取一条指令并执行，该指令的地址为 m1;
④ 顺序执行一条指令，其地址为 m1+1;
⑤ 在后地址[m1+2, 319]中随机选取一条指令并执行；
⑥ 重复上述步骤①~⑤，直到执行 320 条指令。

将指令序列变换为页地址流
假设：
① 页面大小为 1K；
② 用户内存容量为 4 页；
③用户虚存容量为 32K；

在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：
第 0 条~第 9 条指令为第 0 页(对应虚存地址为[0,9]);
第 10 条~第 19 条指令为第 1 页(对应虚存地址为[10,19]);
……
第 310 条~第 319 条指令为第 31 页(对应虚存地址为[310,319]);
按以上方式，用户指令可组成 32 页。

三、教材中对四种算法替换行为的描述

4种页面替换算法的行为

四、C语言代码

#include <stdio.h>
#include <stdlib.h>
int value;//输入value值以确定用户选择的算法 
int count[4];//用于LRU算法，存储最近访问的4个页面，count[0]代表最久未使用或修改的页面号 
int fifo;//用于FIFO算法 
int lru;//用于LRU算法 
double count_OPT = 0; //缺页次数
double count_FIFO = 0; //缺页次数
double count_LRU = 0; //缺页次数
int instrAddr[320]; //指令地址流 数组0123456789...319
int pageAddr[320]; //页地址流数组00000000001111111111222222222233333333...31(10),不是顺序的 
typedef struct Data //数据域
{
    int page; //装进的用户虚存页号
    int block; //块号
}data;

typedef struct BlockNode //单向循环链表
{
    Data data;
    struct BlockNode *next;
    
} Block, *BlockList;

//定义内存块
BlockList block1;
BlockList block2;
BlockList block3;
BlockList block4;

void init() //初始化
{
    block1 = new Block;
    block2 = new Block;
    block3 = (Block*)malloc(sizeof(Block));
    block4 = (BlockList)malloc(sizeof(Block));
//malloc函数用于在内存开辟了一段地址，而这段地址的首地址存在返回的那个指针变量里，由于不知道到底这段地址有多长，
//可以存什么变量，所以它的类型是空的，你可以强制类型转换，使其变成确定长度，固定存放一种数据类型的地址，
//而不管它是哪种类型，其首地址还是原来那个，还是存在一个指针变量中，指针变量就是放指针的嘛，指针是一个地址，
//指针变量是一个我们定义的，用来放那个地址的变量。

//获取Block的字段长度，然后强转为BlockList类型。block4变量就代表地址长度和Block一样所占内存空间同样大小的BlockList

    block1->data.page = -1;
    block2->data.page = -1;
    block3->data.page = -1;
    block4->data.page = -1;

    block1->data.block = 0;
    block2->data.block = 1;
    block3->data.block = 2;
    block4->data.block = 3;

    block1->next = block2;
    block2->next = block3;
    block3->next = block4;
    block4->next = block1;

    for(int i = 0; i < 320; i++) //初始化地址流
    {
        int m = rand() % 320;//随机数0~319 
        instrAddr[i] = m ;//存入随机数0~319 
        pageAddr[i] = instrAddr[i] / 10;// 存入指令所在的页面号 
    }
    printf("初始化成功！\n");
}
//pos为所调用页在地址流中的位置
void OPT(int pageNum, int instrAddr, int pos) //最佳置换算法(OPT)
{
    BlockList p = block1;
    for(int i = 0; i < 4; i++) //遍历所有内存块，若不进行任何操作则遍历结束时候仍指向block1
    {
        if(p->data.page == -1) //块为空闲
        {
            p->data.page = pageNum;
            count_OPT++; //缺页次数+1
//            printf("-------------------------------\n");
//            printf("|               %d              |\n",p->data.block);
//            printf("-------------------------------\n");
//            printf("|       访问第 %d 条指令   %d   |\n", pos,instrAddr);
//            printf("-------------------------------\n");
//            for( int n=0; n<10; n++ )
//            printf("|        十条指令之%d %d        |\n",n,instrAddr/10*10+n);
//            printf("-------------------------------\n");
//            printf("|   物理地址：第 %d 块第 %d 条   |\n", p->data.block+1, instrAddr % 10+1);
//            printf("-------------------------------\n\n");
            printf("访问第 %d 条指令   ", pos);
            printf("指令地址：%d \n", instrAddr);
            printf("指令未存在于内存！页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
			"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);
            return; 
        }
        if(p->data.page == pageNum)//新访问的指令存在于内存中 
        {
            printf("访问第 %d 条指令   ", pos);
            printf("指令地址：%d \n", instrAddr);
            printf("指令已存在于内存中！无需进行页面置换！\n用户指令第%d页第%d条的物理地址为："
			"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);

            return;
        }
        p = p->next;
    }

    //OPT置换策略 
    int allBlockPage[4]; //记录当前页地址

    for(int i = 0; i < 4; i++)
    {
        allBlockPage[i] = p->data.page;
        p = p->next;
    }

    int nextAddr[4]; //记录页地址下次出现的位置

    for(int i = 0; i < 4; i++)
    {
        for(int j = pos; j < 320; j++)
        {
            if(allBlockPage[i] == pageAddr[j]) //找到第一个位置即停止
            {
                nextAddr[i] = j;
                break;
            }
        }
    }

    int temp = 0; //页地址
    int blockPos; //内存块的地址

    for(int i = 0; i < 4; i++)//选出四个页面中距离下次访问到存在于这四个页面中的指令最远的页面的地址下标 
    {
        if(nextAddr[i] > temp)
        {
            temp = nextAddr[i];
            blockPos = i;
        }
    }

    for(int i = 0; i < 4; i++)//找出四个页面中在上一次标记的页面并进行页面替换和缺页计数 
    {
        if(p->data.block == blockPos)
        {
            p->data.page = pageNum;
            count_OPT++;
            printf("访问第 %d 条指令   ", pos);
            printf("指令地址：%d \n", instrAddr);
            printf("指令未存在于内存中但内存块已满！页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
			"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);
        }
        p = p->next;
    }
}
void FIFO(int pageNum, int instrAddr, int pos)//先进先出置换算法(FIFO) 
{
	BlockList p = block1;//指向第一个块 
 	for( int i=0; i<4; i++ )
 	{
 		if( p->data.page == -1 )//块为空 
 		{
 			fifo=pos;
 			if( i==3 )
 			fifo++;
 			p->data.page = pageNum;
 			count_FIFO++;
 			printf("访问第 %d 条指令   ",pos);
 			printf("指令地址：%d\n",instrAddr);
 			printf("指令未存在于内存中，页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
			 "第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
			return;
		}
		if( p->data.page == pageNum )//页面已存在于内存中 
		{
			if( pos<5 )
			fifo = pos;
			printf("访问第 %d 条指令   ",pos);
 			printf("指令地址：%d\n",instrAddr);
 			printf("指令已存在于内存中，无需进行页面置换！\n用户指令第 %d 页第 %d 条的物理地址为："
			 "第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
			return;
		}
		p = p->next;
	}
	//FIFO替换策略 
	for( int i=0; i<(fifo-1)%4; i++ )
	p = p->next;
	fifo++;
	p->data.page = pageNum;
	count_FIFO++;
	
	printf("访问第 %d 条指令   ",pos);
 	printf("指令地址：%d\n",instrAddr);
 	printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
	 "第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
	
}
void LRU(int pageNum, int instrAddr, int pos)//最近最久未用置换算法(LRU)
{
	int tem=0;
	int mids;
	BlockList p = block1;//指向第一个块 
 	
 	for(int i=0;i<4;i++)
 	for( int i=0; i<4; i++ )
 	{
 		if( p->data.page == -1 )//块为空
 		{
 			p->data.page = pageNum;
 			count[lru] = pageNum;
 			lru++;
 			count_LRU++;
 			printf("访问第 %d 条指令   ",pos);
 			printf("指令地址：%d\n",instrAddr);
 			printf("指令未存在于内存中，页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
			 "第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
			return;
		}
		if( p->data.page ==pageNum )//页面已存在于内存中 
		{
			for(int d=0; d<lru; d++)//搜索已存在的页面的位置，传给mids 
			{
				if(count[d]==pageNum)//p->data.page
				{
					mids=d;
					break;
				}
			}
			if(mids==0)
			{
				for( int j=0; j<lru-1; j++)
				{
					count[j] = count[j+1];
				}
				lru--;
			}
			else if(mids==1&&lru!=2)
			{
				for( int j=1; j<lru-1; j++)
				{
					count[j] = count[j+1];
				}
				lru--;
			}
			else if(mids==2&&lru==4)
			{
				count[2] = count[3];
				lru--;
			}
			if( mids != 3 )
			{
				count[lru] = pageNum;
				lru++;
			}
			printf("访问第 %d 条指令   ",pos);
 			printf("指令地址：%d\n",instrAddr);
 			printf("指令已存在于内存中，无需进行页面置换！\n用户指令第 %d 页第 %d 条的物理地址为："
			 "第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
			return;
		}
	    p = p->next;
    }
	if( lru==4 )
	{
		for( int i=0; i<4; i++ )
		{
			if(count[0]==p->data.page)
			{
				p->data.page = pageNum;
				count_LRU++;
				printf("访问第 %d 条指令   ",pos);
 				printf("指令地址：%d\n",instrAddr);
 				printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
		 		"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
		 		for( int g=0; g<4; g++ )//替换之后的count数组变化 
		 		{
		 			count[g] = count[g+1];
		 			if( g==3 )
		 			lru--;
				}
				count[lru] = pageNum;
				lru++;
		 		return;
			}
			else
			p=p->next;
		}
	}
	else if( lru==0 )
	{
		count[lru] = pageNum;
		lru++;
		p->data.page = pageNum;
		count_LRU++;
		printf("访问第 %d 条指令   ",pos);
 		printf("指令地址：%d\n",instrAddr);
 		printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
		"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
		return;
	}
	else
	{
		count[lru] = pageNum;
		lru++;
		for( int j=0; j<4; j++ )
		{
			for( int i=0; i<lru; i++ )
			{
				if( p->data.page == count[i] )
				{
					tem=1;
					break;
				}
				else
				tem=0;
			}
			if( tem==0 )
			{
				p->data.page = pageNum;
				count_LRU++;
				printf("访问第 %d 条指令   ",pos);
 				printf("指令地址：%d\n",instrAddr);
 				printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
		 		"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
		 		return;
			}
			p=p->next;
		}
	}
}
void handle() //计算缺页率
{
	if( value==1 )
	{
		printf("**********最佳置换算法(OPT)**********\n\n");
		for( int i = 0; i < 320; i++ )
    	{
    		OPT(pageAddr[i], instrAddr[i], i+1);
   		}
   		printf("**********最佳置换算法(OPT)**********\n\n");
    	printf("缺页次数：%.0f\n", count_OPT);
    	printf("计算得到的缺页率为：%.4f \n\n\n", count_OPT / 320);
	}
	else if( value==2 )
	{
		fifo = 0;
 		printf("**********先进先出置换算法(FIFO)**********\n\n");
		for(int i = 0; i < 320; i++)
    	{
    		FIFO( pageAddr[i], instrAddr[i], i+1);
   		}
   		printf("**********先进先出置换算法(FIFO)**********\n\n");
    	printf("缺页次数：%.0f\n", count_FIFO);
    	printf("计算得到的缺页率为：%.4f \n\n\n", count_FIFO / 320);
	}
    else if( value==3 )
	{
		lru=0;
		printf("**********最近最久未用置换算法(LRU)**********\n\n");
		for(int i = 0; i < 320; i++)
    	{
    		LRU( pageAddr[i], instrAddr[i], i+1);
   		}
   		printf("**********最近最久未用置换算法(LRU)**********\n\n");
    	printf("缺页次数：%.0f\n", count_LRU);
    	printf("计算得到的缺页率为：%.4f \n\n\n", count_LRU / 320);
	}
	
}
void menu()
{
	printf("输入下列某一序号以开始执行！\n\n");
	printf("1、最佳置换算法(OPT)\n");
	printf("2、先进先出置换算法(FIFO)\n");
	printf("3、最近最久未用置换算法(LRU)\n\n");
}

int main()
{
//	block1 = new Block;
//  block2 = new Block;
//  block3 = (Block*)malloc(sizeof(Block));
//  block4 = (BlockList)malloc(sizeof(Block));
	while( true )
	{
		count_OPT = 0; //记录OPT缺页次数 
		count_FIFO = 0; //记录FIFO缺页次数 
		count_LRU = 0; //记录LRU缺页次数 
		init();//初始化 
		menu();//菜单 
		printf("你选择的序号是：");
		scanf("%d",&value);
    	handle();//执行算法的同时计算缺页率 
	}
    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
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395

该C语言代码的循环链表初始化和OPT算法部分借鉴了这篇博客。如有不妥告知修改。
欢迎各位前辈对代码批评指正，感谢你的观看！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/163441