操作系统实验——内存管理一、实验目的1、了解虚拟存储技术的特点，掌握虚拟存储器请求页面式存储管理中几种基本页面替换算法的基本思想和实现过程，并比较它们的效率。
2、了解编程技术和内存泄漏的原因
二、实验内容1、模拟实现请求页面型存储管理的几种基本页面替换算法
(1)最优淘汰算法(OPT ) )。
)2)先进先出算法(FIFO ) ) ) )。
)3)最近最早使用的算法(LRU ) )
三.实验原理1、虚拟存储系统
在UNIX上，为了提高内存使用率，提供内外内存进程交换机制的内存区域的分配和回收都是以页面为单位进行的； 一个进程只需将其一部分(段或页)放入内存即可完成。 它还支持要求分页的存储管理方法。
进程运行中需要访问部分程序和数据时，如果发现内存中不存在该存在的页面，立即提出请求(向CPU发出缺失中断)，系统将该需要的页面调入内存。 这种页面的调用方式称为“调用页面”。
为了实现寻呼请求，核心配置了页表、页框号、访问位、修正位、有效位、保护位四种数据结构。
2、页面替换算法
当CPU接收到缺页中断信号时，中断处理程序首先保存现场，分析中断原因，然后转入缺页中断处理程序。 该程序通过检索页面表，得到保存在该页面所在外部的物理块号码。 如果此时内存已满，可以容纳新页，请启动磁盘I/O将缺少的页调入内存并更改页表。 内存已满后，必须准备用某种替换算法从内存中选择一页进行交换。 是否重写光盘取决于页表的修改位。 然后，调用缺少的页面来修改页面表。 使用修改后的页表形成要访问的数据的物理地址，然后访问内存数据。 整个页面的调入过程对用户是透明的。
(1)最佳丢弃算法) OPT )选择并替换绝对不使用或今后最长时间内不再访问的页面。
)2)先进先出算法) FIFO )选择并替换最长地驻留在存储器中的页面。
)3)最近最长未使用算法(LRU ) :选择并替换过去最长未访问的页面。
四.实验流程图及所需数据结构
首先需要定义数据结构struct
struct page信息{ int id； //页码int visit； //被访问的标记； page信息* block； //物理块page信息* page； //页面int pagenum； //合并的页数int a[100] //用于显示的数组class pager { private : int count； //页面中断次数int change； //页面替换次数int blocknum=3； 实验思路：
首先，判断存储器中是否有当前需要调度的页面，如果有，就不需要进行页面不足中断，否则就需要进行页面不足中断
页面不足的情况可以分为以下两种。
)1)内存中有空闲位置，将当前调度的页面直接调用到内存中)一般出现在调度的开头) )。
)2)如果内存中不存在可用空间，则必须选择并调用内存中的一个页面，将当前计划的页面放入内存中。 此过程是页面替换，丢弃的依据是上述visit值较大的一方
` ` ` cppint findreplace () /查找要替换的页面({int pos=0； for(intI=0； i blocknum； I ) if (block [ I ].visit=block [ pos ].visit ) pos=i； }return pos； } Opt替换算法：丢弃未来不再使用或今后很长一段时间内不再访问的页面。 预读后续页，作为物理块中的页参考。 如果其中的页面没有后续出现或者出现的最慢，则该页面的访问参照位置(visit )最大，并废弃安装代码。 ` ` CPPfor ) intk=0； k blocknum； k ) for(intj=I； j pagenum； j(if ) block[k].id！=page [ j ].id ({ block [ k ].visit=1000； }else{block[k].visit=j； 黑； }}} FIFO先进先出算法：最先进的页面被淘汰，每次转入页面时只要指定该页面的访问参照处(visit )，就可以计算物理块中存在的时间，visit的值越大，进入的顺序最多
代码实现：
space=findspace (； if (空间！=-1({block[space]=page[I]； show (； }else{change； position=findreplace (； cout '即将访问的页面为' page[i].id '，将替换的页面为' block[position].id 'nn '； block[position]=page[i]； show (； }for(intI=0； i blocknum； I ) {block[i].visit； //页面进入后，再每进入一页停留时间1； } Lur最近最久没有使用替换算法了。
此算法已被淘汰，因为它是最近最早使用的，每次访问页面时，该页面的访问引用位置(visit )都必须为0。 每次置换时间表都增加常驻时间，也就是visit
br> 实现代码： space = findspace();if (space != -1){block[space] = page[i];show();}else{change++;position = findreplace();cout << "即将访问的页面是：" << page[i].id << ",将被置换出的页面是：" << block[position].id << "nn";block[position] = page[i];show();}for (int i = 0; i < blocknum; i++){block[i].visit++;//页面进入后，每再进入一个页面停留时间+1；} 五、实验结果截图：
六、实验代码 #include <iostream>#include<stdlib.h>#include<ctime>using namespace std;struct pageinformation{int id;//页面号int visit;//被访问标记};pageinformation* block;//物理块pageinformation* page;//页面int pagenum;//合并的页面数int a[100];//显示时用的数组class pager{private:int count;//页面中断次数int change;//页面置换次数int blocknum = 3;public:void convertopage()//分配页面{cout << "页面数量：";cin >> pagenum; cout << endl;cout << "输入值：";for (int i = 0; i < pagenum; i++){cin >> a[i];}page = new pageinformation[pagenum];for (int i = 0; i < pagenum; i++){page[i].id = a[i];}}void blockclear()//物理块分配初值{block = new pageinformation[3];for (int i = 0; i < 3; i++){block[i].id = -1;block[i].visit = 0;}}int findspace()//查找是否有空闲块{for (int i = 0; i < blocknum; i++){if (block[i].id == -1)return i;//找到}return -1;}int findexist(int curpage)//寻找内存中是否有该页面{for (int i = 0; i < blocknum; i++){if (block[i].id == page[curpage].id){return i;}}return -1;}int findreplace()//查找应予以置换的页面{int pos = 0;for (int i = 0; i < blocknum; i++){if (block[i].visit >= block[pos].visit)pos = i;}return pos;}void showall()//显示整体置换完的页面{for (int i = 0; i < pagenum; i++){cout<<"置换后的结果为： "<< a[i] << " ";if (i / 4 == 0) cout << endl;}cout << endl;}void show()//显示置换完一次后的block{cout << "此次置换后的block中为：";for (int i = 0; i < blocknum; i++){if (block[i].id != -1) cout<< block[i].id << " ";}cout << endl;}void opt()//最佳置换算法{int exist, space, position;double opt_missrate = 0;//缺页率count = 0;change = 0;for (int i = 0; i < pagenum; i++){exist = findexist(i);if (exist != -1){cout << "------------------" << endl;cout << "即将访问的是页面" << page[i].id << ",内存中已经有该页面" << endl;cout << "------------------" << endl;}else{count++;space = findspace();if (space != -1)//如果block中有空位 直接插入{block[space] = page[i];show();}else//block中没有空位，则选择未来没有出现的或者出现的最晚的页面{change++;for (int k = 0; k < blocknum; k++){for (int j = i; j < pagenum; j++){if (block[k].id != page[j].id){block[k].visit = 1000;}else{block[k].visit = j;break;}}}position = findreplace();cout << "即将访问的是页面：" << page[i].id << "，被置换的页面是" << block[position].id << endl;block[position] = page[i];show();}}}opt_missrate = (float)count / pagenum;cout << "缺页次数：" << count << endl;cout << "置换次数：" << change << endl;cout << "pot算法的缺页率是：" << opt_missrate * 100 << "&" << endl;}void FIFO()//先进先出算法{int exist, space, position;double fifo_missrate = 0;count = 0;change = 0;for (int i = 0; i < pagenum; i++){exist = findexist(i);if (exist != -1){cout << "----------------------------" << endl;cout << "即将访问的页面是：" << page[i].id << ",内存中已存在该页面" << "nn";cout << "----------------------------" << endl;}else{count++;space = findspace();if (space != -1){block[space] = page[i];show();}else{change++;position = findreplace();cout << "即将访问的页面是：" << page[i].id << ",将被置换出的页面是：" << block[position].id << "nn";block[position] = page[i];show();}}for (int i = 0; i < blocknum; i++){block[i].visit++;//页面进入后，每再进入一个页面停留时间+1；}}fifo_missrate = (float)count / pagenum;cout << "缺页次数：" << count << endl;cout << "置换次数：" << change << endl;cout << "fifo缺页率为：" << fifo_missrate * 100 << "%" << endl;}void lur()//最近最久未使用或者最少使用置换算法{int exist, space, position;double lur_missrate = 0;count = 0;change = 0;for (int i = 0; i < pagenum; i++){exist = findexist(i);if (exist != -1){cout << "----------------------------" << endl;cout << "即将访问的页面是：" << page[i].id << ",内存中已存在该页面" << "nn";cout << "----------------------------" << endl;block[exist].visit = 0;//每访问一次需要重置；}else{count++;space = findspace();if (space != -1){block[space] = page[i];show();}else{change++;position = findreplace();cout << "即将访问的页面是：" << page[i].id << ",将被置换出的页面是：" << block[position].id << "nn";block[position] = page[i];show();}}for (int i = 0; i < blocknum; i++){block[i].visit++;//页面进入后，每再进入一个页面停留时间+1；}}lur_missrate = (float)count / pagenum;cout << "缺页次数：" << count << endl;cout << "置换次数：" << change << endl;cout << "lur缺页率为：" << lur_missrate * 100 << "%" << endl;}};int main(){pager test;test.blockclear();test.convertopage();test.opt();test.FIFO();test.lur();} 七、实验总结
FIFO算法：总是淘汰在内存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。
优点：FIFO页面置换算法实现简单，要求的硬件支持较少。
缺点：（1）性能并不很好，效率不高；
存在Belady异常现象，即缺页率随内存块增加而增加。
OPT算法：最佳置换算法（Optimal Replacement, OPT）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。
优点：保证有最小缺页率。
缺点：实现上很困难。
LRU算法：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。
优点：效率高，实现简单
缺点：偶发性的、周期性的批量操作会导致LRU的命中率急剧下降，缓存五日内情况比较严重
具体根据实验结果分析可以很容易的发现，三种算法当中，OPT的缺页率是最低的，当内存块较大时，有可能出现三种算法缺页率相同的情况，但若是三种算法的缺页率不同，OPT的缺页率一定是最低的。
八、思考题
1、从几种算法的命中率看，哪个算法最高？哪个算法最低？对每个页面的执行结果进行分析。
Opt最高，lru与fifo相近:
2、OPT算法在执行过程中可能会发生错误，为什么？
因为opt算法是对将来出现最晚的 进行淘汰，这其中涉及到了对未来的判断，但因为在现实操作中，进程是动态执行的，可变性较大，无法对未来进行准确的判断，当判断与实际情况不符时，就会出现错误。Opt算法是一种理想的算法，现实中很难实现。