C语言实现操作系统页面置换算法--大作业版（附代码）

1设计和实现FIFO,LRU,OPT和CLOCK算法

2设计和实现一个完整的可供选择不同算法的程序

3通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

4领略页面置换背后的资源调配思想，并将其运用到其他的操作系统的知识，以及运用到生活中的资源调配策略以及解决措施。

5理解并掌握各种算法的优缺点，理解FIFO的Belady异常，LRU的优秀性能，CLCOK的折中主义，OPT算法对预测将来做出判断的思想

1.核心基本原理

a.无论是采用什么页面置换算法，都要经过下面的判断

b.页面不在内存中，但是此时内存还未满，那就将页面存到内存中，然后输出,缺页次数++

c.页面不在内存中，且此时内存已满，需要把页面置换，缺页次数++，置换次数++

d.不同算法的区别主要是怎样置换

2．FIFO置换算法

a.相当于是认为最早调入内存的页面，他不再使用的概率比刚调入内存的概率大。

b.置换最先进入内存，就是在内存中驻留时间最长的的页面。

3．LRU置换算法

a.相当于是认为一个页面使用后，如果长时间没有使用，那么将来有更大概率是不会使用的。

b.置换最近最久没有有用过的页面。

4．OPT置换算法

a.相当于假如知道未来页面的使用情况，可以制定当前的最优策略。

b.置换的是未来长时间或者永远不再使用的页面。

c.与FIFO算法对应起来，FIFO是页面进入内存后的时间，而OPT是将来使用页面的时间。

5．CLOCK置换算法

a.相当于改良版的LRU，认为最近没用过的页面就扔掉，而且是类似于一个时钟，一个个页面指过去，所以每个页面都有相等机会被置换出去。

b.用循环数组，置换最近没有访问过的页面。

6．算法评价

1系统设计思路

1系统接受我们输入的页面数量，物理块数，访问序列的长度，然后系统自己生成随机的访问序列。

2复制了访问序列，这样我后续做其他操纵只在fork序列中而不对原序列产生影响。

3自己可以反复的选择不同的置换算法，当然，如果选择的内容不是系统提供的内容，也会提醒重新输入，或者选择退出。

2数据结构

3核心算法流程图

4实验测试数据

特定实验测试数据（调试用）

页面数量：6

内存块物理块数：3
访问序列的长度：10

初始化数据

理论分析

置换只发生于内存块满了，而且内存块中没有与页面相同的数据，置换内存中驻留时间最长的页面，也就是轮换着内存块0 1 2 0 1 2…

1. 3 5 1 4 0 3 5 5 0 4 内存块没有满并且访问的页面不在内存块之中，那就将其放入内存块
2. 3 5 1 4 0 3 5 5 0 4 发生置换，置换最早进入的内存块0的内容
3. 3 5 1 4 0 3 5 5 0 4 发生置换，置换内存块0的下一块内存块1的内容
4. 3 5 1 4 0 3 5 5 0 4 发生置换，置换内存块1的下一块内存块2的内容
5. 3 5 1 4 0 3 5 5 0 4 发生置换，置换内存块1的下一块内存块2的内容
6. 3 5 1 4 0 3 5 5 0 4 发生置换，置换内存块2的下一块内存块0的内容

所以总计置换次数为5 缺页次数为5+3=8次

所以缺页率为8/10*100%=80%

结果分析：

置换只发生于内存块满了，而且内存块中没有与页面相同的数据，换的是最近最久没有用过的页面，也就是time数组中数据最大的那一项。

时间数组访问到的页面或者置换掉的页面都置为0，而没有访问的都比上一次时间数组多1

1. 3 5 1 4 0 3 5 5 0 4 内存块没有满并且访问的页面不在内存块之中，那就将其放入内存块
2. 3 5 1 4 0 3 5 5 0 4 发生置换，时间数组为2 1 0 ，所以置换的是内存块0的内容
3. 3 5 1 4 0 3 5 5 0 4 发生置换，时间数组为0 2 1 ，所以置换的是内存块1的内容
4. 3 5 1 4 0 3 5 5 0 4 发生置换，时间数组为1 0 2 ，所以置换的是内存块2的内容
5. 3 5 1 4 0 3 5 5 0 4 发生置换，时间数组为2 1 0 ，所以置换的是内存块0的内容
6. 3 5 1 4 0 3 5 5 0 4 发生置换，时间数组为1 0 3 ，所以置换的是内存块2的内容

所以总计置换次数为5 缺页次数为5+3=8次

所以缺页率为8/10*100%=80%

结果分析：

置换只发生于内存块满了，而且内存块中没有与页面相同的数据，换的是未来长时间或者永远不再使用的页面，也就是future数组中数据最大的那一项,当然还有一个小技巧就是从当前位置往后看，观察哪个页面现在内存块中存的页面离的最远，当然如果没有的话就相当于无限远。

1. 3 5 1 4 0 3 5 5 0 4 内存块没有满并且访问的页面不在内存块之中，那就将其放入内存块
2. 3 5 1 4 0 3 5 5 0 4 发生置换，3 5 1 4 0 3 5 5 0 4 ，3和5都有了而1没有那就相当于1在未来都不会使用到了，那就置换页面1的内存块
3. 3 5 1 4 0 3 5 5 0 4 发生置换，3 5 1 4 0 3 5 5 0 4，4离本位置最远，所以置换的是页面4的内存块
4. 3 5 1 4 0 3 5 5 0 4 发生置换，3 5 1 4 0 3 5 5 0 4，由于4是最后一个访问序列，所以3 5 0往后的位置都是无限远，那么置换的就是第一个页面3的内存块了

所以总计置换次数为3 缺页次数为3+3=6次

所以缺页率为6/10*100%=60%

结果分析：

置换只发生于内存块满了，而且内存块中没有与页面相同的数据，换的是最近没有访问过的页面。而CLOCK算法采用的是循环数组，所以如果访问到该页面，该页面的clcok数组中标志为1，同时下一次的访问也是从下一个下标开始。如果访问的页面不在内存中但是内存都是访问过的也就是全为1，那么将所有的访问位设置为0，也就是说置换的必定是当前的页面，而且置换后只有当前的clock值为1；而如果内存中有没访问过的也就是clock中有0的，那就转那个页面，同时那个页面的clock设置为1。也就是有0换0，没0全变0，自己变1。

1. 2 4 3 4 0 2 5 2 4 0 内存块没有满并且访问的页面不在内存块之中，那就将其放入内存块
2. 2 4 3 4 0 2 5 2 4 0发生置换， 因为上一次clock中为1 1 1，而上次访问的是页面4，也就是内存块1，那这次访问的就是内存块2，然后只将该内存块的访问位设置为1，其他设置为0 
3. 2 4 3 4 0 2 5 2 4 0 发生置换， 因为上一次clock中为1 0 1 ，上次访问的是内存块0，这次访问的是内存块1，内存块1刚好访问位为0，就直接置换内存块1的内容
4. 2 4 3 4 0 2 5 2 4 0 发生置换，因为上一次clock中为1 1 1，而上次访问的是页面2，也就是内存块0，那这次访问的就是内存块1，然后只将该内存块的访问位设置为1，其他设置为0 

所以总计置换次数为3 缺页次数为3+3=6次

缺页率为6/10*100%=60%

FIFO中的Belady异常

随着资源分配的数量增多，缺页率反而增多了。

结果分析

可以看到从分配3个物理内存块到分配4个物理内存块，其缺页率从75%增到83.3%，也就是发生了Belady异常。

实验总结

1对于FIFO算法的思考

我是运用了一个变量标志上一次页面置换是在什么位置，但是在做题的时候往往使用划分的方法，如果是分配的内存块是3，那就将访问序列3个3个划分为一组，再看某个访问页面在小组中是在什么位置，那就置换哪个内存块。基于这样的思想，所以我还想到一种做法是置换的页面为

此外它页面置换确实非常的简单直接，但是它却出现了Belady异常。比如上面的案例中，FIFO发生Belady的最主要的原因是3 2 1 0 3 2 4 3 2 1 0 4 在访问页面4的时候，分配4个内存块的FIFO是把3置换出去了，而分配3个内存块的FIFO没有把3置换出去，但是访问的下一个页面却是3，所以分配4个内存块的页面置换次数更多。

所以我也更好的理解到，分配资源的时候如果只是单一的增加容量，但是不考虑他使用的频率等情况，有时候会适得其反。

2.对于OPT算法的思考

我使用了一个future数组记录内存块中的页面距离将来使用的距离。但是实际上在做题的时候我想到还可以直接从访问序列中观察，就是从当前的页面往后找与内存块中最晚相同的页面。

所以我也更好的理解到分配资源的时候要考虑将来的使用情况。

3对于LRU算法的思考

它与OPT算法很类似，OPT算法是基于当前页面往后序列的情况，而LRU算法是基于当前页面之前的序列的情况。虽然说两者的准确率都比较高，但是两者在现实中难以实现。此外LRU存储time数组进行记录数据确实很麻烦。

所以我也更好的理解到分配资源的时候要考虑之前的使用情况。

4对于CLOCK算法的思考

它就像一个时钟，使得每一个页面都可以平等的考虑到，所以这使我想到了CPU资源调度中的RR算法，他们似乎有一些共通点。

5对于代码编写调试的思考

在本文档中我举例的两个问题有一个共同的特点，就是没有初始化，所以下次编写代码的时候一定要注意有没有初始化。

此外当异常的可能原因有很多而无法确定的时候，可以对关键位置对整体代码进行划分，比如我上面要使用到clock，time，future数组，那就输出数组中的内容，而且在不同位置输出的内容加个标志符比如clock1，clock2，clock3，这样可以更加方便的帮助我缩小错误的范围。

6对于代码缺点的思考

本次代码只是根据最重要的原理进行简单页面置换，而实际上的虚拟内存中的资源变化还需要看页面有没有修改过，也就是说页表项可以有很多其他的指标，如果考虑了其他的指标，那么页面置换算法还有很高的提高空间。

7对于预期目的的思考

总体来说，本实验已经达到了我的预期目的，我也理解了为什么要有这样的页面置换算法，同时我将本次实验的算法思想与CPU资源调度，银行家PV操作，连续型的内存调度，等操作系统的其他知识进行对比，发现了很多的共通之处与不同之处，所以本次实验也有助于构架我的操作系统知识网络，对其他的操作系统知识有了更好的理解，此外也提高了我程序调试的能力。

#include
#include
#include
#define MAX_VISIRNUM 100 
void ShowVisit(int a[],int num)
{
	printf("访问序列:"); 
	for(int i=0;itime[max])
			max=k;
		}
		ram[max]=fork[i];
        time[max] = 0;
		replaceNum++;
		lackingNum++;
		printf("访问内存%d：",fork[i]);
		ShowRam(ram,PhyNum);
		printf("time:");for(int op=0;opfuture[max])
			max=k;
		}
		ram[max]=fork[i];
        future[max] = searchfuture(fork,i, VisitNum,ram[max]);
		replaceNum++;
		lackingNum++;
		printf("访问内存%d：",fork[i]);
		ShowRam(ram,PhyNum);
	 	}
	 	judge=-1; 
	 } 
	 ShowFinal( replaceNum, lackingNum, VisitNum); 
    
    
}

void CLOCK(int fork[], int PageNum, int PhyNum, int VisitNum)
{
	printf("********************************************************************************n");
	printf("*                                                                              *n");
	printf("*                                 CLOCK算法                                    *n");
	printf("*                                                                              *n");
	printf("********************************************************************************n");
	int ram[PhyNum];Init(ram,PhyNum);
	int clock[PhyNum];
	int replaceNum = 0;//置换次数 
    int lackingNum = 0;//缺//time记录的是访问号  
	int point=0;//指向循环队列中当前的位置
	int num=0;//统计循环查找的次数
	int NUM=0;//初始内存块有没有满  
	for(int pp =0;pp