存储管理实验报告

1、综合性实验报告专业：网络工程 年级：12级 班级：网络工程 2014 2015学年第一学期课程名称计算机操作系统指导教师实验地点过街楼实验时间12.3-12.10-12.17-12.2412.4-12.11-12.18-12.25项目名称存储管理实验类型综合性一、实验目的通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。页面置换算法是虚拟存储管理实现的关键，通过本次实验理解内存页面调度 的机制，在模拟实现FIFO、LRU OPT LFU NUF几种经典页面置换算法的基础 上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。二、总体设

2、计1、编写函数计算并输出下述各种算法的命中率 OPT页面置换算法OPT所选择被淘汰的页面是已调入内存，且在以后永不使用的，或是在最长时间内不再被访冋的页面。 因此如何找出这样的页面是该算法 的关键。可为每个页面设置一个步长变量，其初值为一足够大的数，对 于不在内存的页面，将其值重置为零，对于位于内存的页面，其值重置 为当前访问页面与之后首次出现该页面时两者之间的距离，因此该值越大表示该页是在最长时间内不再被访问的页面，可以选择其作为换出页面。 FIFO页面置换算法FIF O总是选择最先进入内存的页面予以淘汰，因此可设置一个先进 先出的忙页帧队列，新调入内存的页面挂在该队列的尾部，而当无空闲 页

3、帧时，可从该队列首部取下一个页帧作为空闲页帧，进而调入所需页 面。 LRU页面置换算法LRU是根据页面调入内存后的使用情况进行决策的，它利用“最近 的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以 淘汰。该算法主要借助于页面结构中的访问时间 time来实现，time记 录了一个页面上次的访问时间，因此，当须淘汰一个页面时，选择处于 内存的页面中其 time 值最小的页面，即最近最久未使用的页面予以淘 汰。 LFU 页面置换算法LFU要求为每个页面配置一个计数器（即页面结构中的counter ）,一旦某页被访问，则将其计数器的值加 1，在需要选择一页置换时，则 将选择其计数器值最小

4、的页面，即内存中访问次数最少的页面进行淘 汰。 NURS面置换算法NUR要求为每个页面设置一位访问位（该访问位仍可使用页面结构 中的 counter 表示），当某页被访问时， 其访问位 counter 置为 1。需要 进行页面置换时，置换算法从替换指针开始（初始时指向第一个页面） 顺序检查处于内存中的各个页面， 如果其访问位为 0，就选择该页换出， 否则替换指针下移继续向下查找。 如果内存中的所有页面扫描完毕未找 到访问位为 0 的页面，则将替换指针重新指向第一个页面，同时将内存 中所有页面的访问位置 0，当开始下一轮扫描时， 便一定能找到 counter 为 0 的页面。2、在主函数中生成要

5、求的指令序列，并将其转换成页地址流；在不同的内存容量下调用上述函数使其计算并输出相应的命中率。三、实验步骤（包括主要步骤、代码分析等） 主要步骤：、通过随机数产生一个指令序列，共 320 条指令。其地址按下述原则生成： 50%勺指令是顺序执行的； 25%勺指令是均匀分布在前地址部分； 25%勺指令是均匀分布在后地址部分；具体的实施方法是：A. 在0 , 319的指令地址之间随机选区一起点 MB. 顺序执行一条指令，即执行地址为 M+1的指令；C. 在前地址0 , M+1中随机选取一条指令并执行，该指令的地址为M；D. 顺序执行一条指令，其地址为 M +1；E. 在后地址M； +2, 319中随

6、机选取一条指令并执行；F. 重复A E,直到执行320次指令。2、指令序列变换成页地址流，设： 页面大小为 1K； 用户内存容量为 4页到 32页； 用户虚存容量为 32K。在用户虚存中,按每页存放 10 条指令排列虚存地址,即 320 条指令在虚存 中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0 , 9）;第10条第19条指令为第1页（对应虚存地址为10，19）;第 310条第 319条指令为第 31 页（对应虚存地址为 310, 319）； 按以上方式,用户指令可组成 32页。3、计算并输出下述各种算法 （可任选两个 ）在不同内存容量下的命中率。A. FIFO 先进先出置换算法

7、；B. LRU 最近最久未使用置换算法；C. OPT 最佳置换算法：先淘汰最不常用的页地址；D. NUR最近未使用置换算法；E. LFU 最少使用置换算法。命中率=1 -页面失效次数 /页地址流长度 在本实验中,页地址流长度为 320,页面失效次数为每次访问相应指令时, 该指令所对应的页不在内存的次数。代码分析：1 、主函数 main.cpp 的代码： #include #include #include #include #include #include using namespace std;#define INVALID -1 const int TOTAL_INSTRUCTION(3

8、20);const int TOTAL_VP(32);const int CLEAR_PERIOD(50);#include Page.h#include PageControl.h#include Memory.hint main()int i;CMemory a; for(i=4;i=32;i+) couti page frames t; a.OPT(i); a.FIFO(i); a.LRU(i); coutn; return 0;2、主函数中用到的头文件”Page.h” , ” PageControl.h ” , ” Memory.h” 的代码：Page.h:#ifndef _PAGE_

9、H#define _PAGE_Hclass CPage/ 页面结构 public:int m_nPageNumber,/ 页面号 m_n PageFaceNumber,/页 帧号 m_nCounter,/ 一个周期内访问该页面的次数 m_nTime;/ 访问时间;#endifPageControl.h:#ifndef _PAGECONTROL_H#define _PAGECONTROL_Hclass CPageControl/ 页帧控制结构public:int m_nPageNumber,m_nPageFaceNumber; class CPageControl * m_pNext;#endi

10、fMemory.h:#ifndef _MEMORY_H#define _MEMORY_H class CMemorypublic:CMemory();void initialize(const int nTotal_pf);void OPT(const int nTotal_pf);void FIFO(const int nTotal_pf);void LRU(const int nTotal_pf);private:vector _vDiscPages;vector _vMemoryPages;CPageControl *_pFreepf_head,*_pBusypf_head,*_pBus

11、ypf_tail;vector _vMain,_vPage,_vOffset;int _nDiseffect;CMemory:CMemory():_vDiscPages(TOTAL_VP),_vMemoryPages(TOTAL_VP),_vMain(TOTAL_INSTRUCTION),_vPage(TOTAL_INSTRUCTION),_vOffset(TOTAL_INSTRUCTION)int S,i,nRand;srand(getpid()*10);nRand=rand()%32767;S=(float)319*nRand/32767+1;for(i=0;iTOTAL_INSTRUCT

12、ION;i+=4)_vMaini=S;_vMaini+1=_vMaini+1;nRand=rand()%32767;_vMaini+2=(float)_vMaini*nRand/32767;_vMaini+3=_vMaini+2+1;nRand=rand()%32767;S=(float)nRand *(318-_vMaini+2)/32767+_vMaini+2+2; for(i=0;iTOTAL_INSTRUCTION;i+) _vPagei=_vMaini/10;_vOffseti=_vMaini%10;_vPagei%=32; void CMemory:initialize(const

13、 int nTotal_pf)int ix;_nDiseffect=0;for(ix=0;ix_vDiscPages.size();ix+)_vDiscPagesix.m_nPageNumber=ix;_vDiscPagesix.m_nPageFaceNumber=INVALID;_vDiscPagesix.m_nCounter=0;_vDiscPagesix.m_nTime=-1;for(ix=1;ixnTotal_pf;ix+)_vMemoryPagesix-1.m_pNext=&_vMemoryPagesix;_vMemoryPagesix-1.m_nPageFaceNumber=ix-

14、1;_vMemoryPagesnTotal_pf-1.m_pNext=NULL;_vMemoryPagesnTotal_pf-1.m_nPageFaceNumber=nTotal_pf-1;_pFreepf_head=&_vMemoryPages0;void CMemory:OPT(const int nTotal_pf) /*最佳页面置换算法 */int i,j,max,maxpage,d,distTOTAL_VP;initialize(nTotal_pf);for(i=0;iTOTAL_INSTRUCTION;i+) if(_vDiscPages_vPagei.m_nPageFaceNum

15、ber=INVALID) /* 页面失效 */_nDiseffect+; if(_pFreepf_head=NULL) /* 无空闲页面 */ for(j=0;jTOTAL_VP;j+) if(_vDiscPagesj.m_nPageFaceNumber!=INVALID)/ 所 有 位于内存页面的距离变量赋一足够大的数distj=32767;else / 不在内存的页面该变量则置为 0 distj=0;d=1;/* 对于位于内存且在当前访问页面之后将再次被访问的页面， dist 重置为当 前页 面与之后首次出现该页面时两者之间的距 离 */for(j=i+1;jTOTAL_INSTRUCTI

16、ON;j+)if(_vDiscPages_vPagej.m_nPageFaceNumber!=INVALID & dist_vPagej=32767)dist_vPagej=d;d+;max=-1;/ 查找 dist 变量值最大的页面作为换出页面 for(j=0;jTOTAL_VP;j+) if(maxm_pNext=NULL;_vDiscPagesmaxpage.m_nPageFaceNumber=INVALID;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head-m_nPageFa ceNumber; / 有空闲页面 , 改为有效_pFre

17、epf_head=_pFreepf_head-m_pNext; / 减少一个 free 页面coutOPT: 1-(float)_nDiseffect/320;/printf(OPT:%6.4f ,1-(float)diseffect/320);void CMemory:FIFO(const int nTotal_pf)int i;CPageControl *p;initialize(nTotal_pf);_pBusypf_head=_pBusypf_tail=NULL;for(i=0;im_pNext;_vDiscPages_pBusypf_head-m_nPageNumber.m_nPag

18、eFaceNumber=INVALID;_pFreepf_head=_pBusypf_head;_pFreepf_head-m_pNext=NULL;_pBusypf_head=p;p=_pFreepf_head-m_pNext;_pFreepf_head-m_pNext=NULL;_pFreepf_head-m_nPageNumber=_vPagei;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head-m_nPageFaceNu mber;if(_pBusypf_tail=NULL)_pBusypf_head=_pBusypf_tail=_p

19、Freepf_head;else_pBusypf_tail-m_pNext=_pFreepf_head;_pBusypf_tail=_pFreepf_head;_pFreepf_head=p; couttFIFO: 1-(float)_nDiseffect/320;void CMemory:LRU(const int nTotal_pf)int i,j,nMin,minj,nPresentTime(0); initialize(nTotal_pf);for(i=0;iTOTAL_INSTRUCTION;i+)if(_vDiscPages_vPagei.m_nPageFaceNumber=INV

20、ALID)_nDiseffect+;if(_pFreepf_head=NULL) nMin=32767;for(j=0;j_vDiscPagesj.m_nTime&_vDiscPagesj.m_nPageFaceNumber! =INVALID) nMin=_vDiscPagesj.m_nTime; minj=j;_pFreepf_head=&_vMemoryPages_vDiscPagesminj.m_nPageFaceNumber; _vDiscPagesminj.m_nPageFaceNumber=INVALID;_vDiscPagesminj.m_nTime=-1; _pFreepf_

21、head-m_pNext=NULL;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head-m_nPageFaceNu mber;_vDiscPages_vPagei.m_nTime=nPresentTime; _pFreepf_head=_pFreepf_head-m_pNext;else _vDiscPages_vPagei.m_nTime=nPresentTime;nPresentTime+;couttLRU: 1-(float)_nDiseffect/320; #en dif四、结果分析与总结 实验运行结果，如图:roQtlQcalhQst

22、;-/test/w程爵(毎的)_ nX编握足)查看切缪端Cl)标靈帮肋*Arootloc&lhost媒合买验程序，我的耳-/main4PAgCrrancsOPT0-65FIFO：0-53125LRCJ0.531255pagefrairfctOFT：0.68125FIFO：0.516875LRU：0.5593756pagerrareeOPT.0,709375FIFO：0.5656251.RL：0.565025 JpageframesOPT0,714375FIFO：0.564375LRC:0.5906258pagerramwsOPTs0.753125FIFOi0.59375LRU：0.606259

23、 P&CframesOFT0.76875FIFO：0-6LRCj0 02187510pagef ramcLOPTj0.784375FIFO,0.623LRCi0.63437511pagefraiuesOPT.0.SPIPOi0.653125LRUi0.644587512pageframes: 10.3125FIFO：0.665625LRC:0.66S62513framesOPT JO.82jFIFO：066123LR；0.69D625NframesOPT0.34375FIFO：0 28125IRC：0.712515P-agcframesOPTO.S4375FIFO：0.734375LRC；0.7375lti用胆OPT0.S5FIFO：0,734375曲0.7517pageframesOFT；0.85625FIFO：0.753125LRUi0.7623ISpageframes0PTJ0.8625FIFO：0.753L25F：0.7687519pageframesOFT06875FIFO：0AS625IRC：0.77812520P-iECframesOPT