《河南科技大学系统结构实验报告 实验二.doc》由会员分享，可在线阅读，更多相关《河南科技大学系统结构实验报告 实验二.doc（7页珍藏版）》请在三一文库上搜索。
1、实验二 计算机存储体系的页面替换算法一、 实验目的当计算机内存已满而又发生页面失效时，替换算法就要选择主存中哪个页作为被替换的页。通过本实验可以帮助学生理解虚拟存储器中页面替换的基本思想，深刻体会各种页面替换算法的性能差异。二实验环境开发工具使用windows平台下的vc+6.0。三 实验内容编写一个模拟算法，模拟实现虚拟存储器的先进先出、近期最少使用、优化等算法。在程序设计的过程中，要求体会各种页面替换算法的优点和缺点，并计算出各种替换算法的命中率。四 实验结果一、整个实验过程的思路可以整理如下：1. 初始化虚拟存储空间。2. 产生一个随机调用页面的序列。3. 实现各种页面替换算法。4. 计
2、算各种页面替换算法的命中率。二、实验中的几点注意事项：i. 虚拟存储空间的大小要合适。2. 根据能够存储页面的多少确定随机调用页面的序列。源代码如下：源代码如下：#include#includeusing namespace std;int inputSize;int memorySize;int *in; /请求序列int *memory; /模拟内存void FIFO();struct pageint pageNum;int memoryNum;int isInmemory;page pageTable10;/假设虚拟页面数10个，页表长度10int main()for(int i=0;i
3、10;i+)/初始化页表pageTablei.pageNum=i;pageTablei.memoryNum=-1;pageTablei.isInmemory =0; cout输入待调入页面数inputSize; cout输入可使用的物理块数memorySize; in= new intinputSize; memory=new intmemorySize; int temp;int select; srand( (unsigned)time( NULL ) );cout随机生成请求序列？(1是)select;if(1=select)cout随机生成页面请求序列(0-9)endl;for( i=
4、0;iinputSize;i+)temp=rand()%10;couttemp ;ini=temp;else cout输入inputSize个页面号(0-9)endl;for( i=0;itemp;ini=temp;coutendl; FIFO();delete in;delete memory;return 0;void FIFO() /FIFO替换算法实现函数coutFIFO替换算法:endl; for(int i=0;imemorySize;i+)memoryi=-1; int lackTime=0; /记录缺页次数 int firstIn=0; /记录最先被占用的物理块号，装有最先进入
5、内存的页面号 int isFull=0; /记录物理块是否已被占满，当isFull=3时表示已经装满，如果再缺页则发生替换 int page=0; /记录将要访问的页面号 do /物理块未被占满时 if(pageTableinpage.isInmemory =1) / ini在memory中coutinpage is in memoryendl;page+;if(page=inputSize)break;else continue;elselackTime+;coutinpage not in memory!endl; / 装入内存memoryisFull=inpage; for(int j=
6、0;j10;j+)if( pageTablej.memoryNum= isFull) pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break;pageTableinpage.isInmemory=1;pageTableinpage.memoryNum=isFull;isFull+;page+;if(page=inputSize)break;while(isFull!=memorySize); /物理块被占满时退出循环 for( i=page;iinputSize;i+) /此时page如果再次缺页则发生替换if(pageTableini.i
7、sInmemory =1)/ini在memory中coutini is in memoryendl;continue;else /ini不在memory中lackTime+;memoryfirstIn=ini;for(int j=0;j10;j+)if( pageTablej.memoryNum=firstIn)coutini not in memory!take place of page jendl; pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break; pageTableini.isInmemory=1;pageTableini.
8、memoryNum=firstIn;firstIn=(firstIn+1)%memorySize;cout缺页次数：lackTimeendl;cout缺页率： double(lackTime)/inputSize*100%endl;完成情况：初始界面：FIFO算法： Optimal算法： LRU算法： 五出现问题及解决方案1.问题：如何长生随机请求序列？解决方案：用srand( (unsigned)time( NULL ) );即可。2.问题： 发下安不管输入什么数值，都可以运行，后来找到出错地方，更正为：1=select六 思考题在计算机存储结构中，内存外存和CACHE内存都会用到替换算法，
9、它们之间有什么异同点？答：(1) 随机算法，即RAND算法（Random algorithm）。利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单，而且容易实现。但是，这种算法完全没有利用主存储器中页面调度情况的历史信息，也没有反映程序的局部性，所以命中率比较低。(2) 先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。(3) 近期最少使
10、用算法，即LFU算法（Least Frequently Used algorithm）。这 种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既 充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择 一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相对比较简单的方法。 (4) 最久没有使用算法，即LRU算法（Least Recently U
11、sed algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有与无，因此，实现起来比较容易。(5) 最优替换算法，即OPT算法（OPTimal replacement algorithm）。上 面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度 情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最 优替换算法。七实验总结通过这次实验，我了解到
12、了FIFO算法的使用以及当计算机内存已满而又发生页面失效时使用的替换算法，同时还理解虚拟存储器中页面替换的基本思想，深刻体会各种页面替换算法的性能差异。在虚拟存储器中，当发生页面失效时，需要从磁盘存储器中调入一页（或一段）到主存储器中。页面调度的时候，用了还能多循环控制的指令，假如循环中发下无法控制，通常会发生死锁。另附参考程序：#include “stdio.h”#define max 100 /*定义页面数组大小的上限*/#define size_pa 1024void add_tran()int arraymax2;/*页表，其中arrayn0为页号，arrayn1为块号*/int si
13、ze_PT；int no_page,no_block;/* no_page,no_block 分别是页号和块号*/int if_quit1; /*if_quit1退出子程序标志*/int i,j；/*j表示下一个将被置换的页面位置*/int add_logic,add_sys;/*逻辑地址和绝对地址*/int if_page;/*中断标志*/if_quit1=0;/*退出标志*/*初始化页表*/printf(“n please input size of the page table: ”);scanf(“%d”,&size_PT);j=size_PT-1;printf(“n now init
14、ialize the page table, please input page number and block number n”);for(i=0；I=size_PT;i+)printf(“page number:”)scanf(“%d”,&no_page);printf(“block number:”)scanf(“%d”,&no_block);arrayi0=no_page;arrayi1=no_block;printf(“initializing complete”);/*输出初始化页表*/printf(“nPage table: n”);for(i=0;isize_PT;i+)p
15、rintf(“page:%5d”,arrayi0);printf(“block:%5d”,arrayi1); printf(“n”)； printf(“n”)； /*地址变换*/ /*页面置换模拟：输入页面序列，缺页时按FIFO的策略进行页面置换。*/*输出置换情况，和缺页次数*/*假设页表大小不超过max，输入的页面数不超过max*1O*/，/*程序执行流程：*/*初始化：输入分配的块数，输入页面序列*/*输出依次访问一个页面后的页表，然后输出缺页中断总次数*/void page_si()/*主程序*/void main() int if_quitO；/*if-quit0退出主程序标志*/
16、int n_func; if_quit0=0; while(if_quit0=0) printf(“n please input number of the funotion you want to executen”)； printf(“l-address translating，2-page simulating, 0-exit,”)； scanf(“%d”，&n_func)； if(n_func=1) add_tran()； if(nfunc=2) page_si()； if(n_func=0) if_quitO=l； 按以上程序完善add_tran()函数中的地址变换过程，并补充完成页面置换算法的page_si()子程序。