资源描述
实验五实验五 请求页式存储管理中常用页面置请求页式存储管理中常用页面置换算法模拟换算法模拟班级：软件工程3班；学号：11270337；姓名：孙园萍实验五请求页式存储管理中常用页面置换算法模拟一、实验目的n（1）了解内存分页管理策略n（2）掌握调页策略n（3）掌握一般常用的调度算法n（4）学会各种存储分配算法的实现方法。n（5）了解页面大小和内存实际容量对命中率的影响。一、实验目的二、实验内容n（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；n（2）实现OPT算法(最优置换算法)、LRU算法(LeastRecently)、FIFO算法(FirstINFirstOut)的模拟；n（3）会使用某种编程语言。二、实验内容三、实验原理n分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。n在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_ReplacementAlgorithms)。n一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。三、实验原理分页存储管理将一个进程的逻辑地址空间分成若干大1、最佳置换算法、最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。2、先进先出、先进先出(FIFO)页面置换算法页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。1、最佳置换算法OPT(Optimal)3、最近最久未使用置换算法、最近最久未使用置换算法（1）LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。3、最近最久未使用置换算法（2）LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持、硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：a）寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。（2）LRU置换算法的硬件支持R7R6R5 R4 R3 R2 R1R0101010010210101100300000100401101011511010110600101011700000111801101101R7R6R5R4R3R2R1R0101b)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。b)栈程序清单程序清单实验步骤如下：/现定义数据结构和全局变量#include#include#defineM4#defineN17#defineMyprintfprintf(|-+-+-+-+-+-+-+-+-+-n)表格控制TypedefstructpageIntnum;/记录页面号Inttime;/记录调入内存时间page;/页面逻辑结构，结构为方便算法实现设计程序清单实验步骤如下：Page bM;/内存单元数Int cMN;/暂保存内存当前的状态：缓冲区Int queue100;/记录调入队列Int k;/调入队列计数变量/初始化内存单元、缓冲区Void Init(Page*b,int cMN)Int i,j;For(i=0;iN;i+)bi,num=-1;bi.time=N-i-1;For(i=0;iM;i+)For(j=0;jN;j+)cij=-1;/取得在内存中停留最久的页面，默认状态下为最早调入的页面PagebM;/内存单元数Int GetMax(Page*b)Int i;Int max=-1;Int tag=0;For(i=0;imax)Max=bi.time;Tag=i;Return tag;/判断页面是否已在内存中Int Equation(int fold,Page*b)Int i;For(i=0;i=0)bval.time=0;For(i=0;iM;i+)If(i!=val)bi.time+;Else Queue+k=fold;/记录调入页面 Val=GetMax(b);bval.num=fold;bval.time=0;For(i=0;iM;i+)if(i!=val)bi.time+;/FIFO与OPT的算法描述省略VoidLru(intfold,Page*b)/主程序void main()Int aN=1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4;Int i,j;Start:K=-1;Init(b,c)For(i=0;iN;i+)Lru(ai,b);C0i=ai;/记录当前的内存单元中的页面For(j=0;jM;j+)Cji=bj.num;/结果输出Printf(内存状态为：n);Myprintf;For(j=0;jN;j+)Printf(%2d,ai);Printf(n);Myprintf;/主程序For(i=0;iM;i+)For(j=0;jN;j+)If(cij=-1)printf(%2c,32);Else Printf(%2d,cij);Printf(/n);Myprintf;Printf(n 调入队列为：)；For(i=0;iK+1;i+)Printf(%3d,queuei);Printf(n缺页次数为：%6dn 缺页率：%16.6f,K+1,(float)(K+1)/N);Printf(/nAre you continuing!fy?);If(getchar()=y)goto start;For(i=0;iM;i+)谢谢观赏谢谢观赏谢谢观赏
展开阅读全文