存储器管理实验报告

操作系统实验报告2012年12月24日学号1008114124姓名L刘凯利时间12月27日专业计算机科学与技术班级计科二班实验题目：存储器管理实验目的：1.通过模拟实现最佳页面置换的算法，熟悉存储器管理方式；2.掌握虚拟存储请求页式存储管理中几种页面置换算法的基本思想，并用三种至少三种算法来模拟实现；3.比较对几种置换算法页面，对比他们的优缺点，并通过比较更换频率来对比它们的效率；实验原理：为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断）由系统将其所需页面调入内存。如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。实验步骤：先进先出(FIFO)置换算法通过淘汰最先进入内存的页面，即选淘汰在内存中驻留时间最久的页面。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2.最近久未使用(LRU)置换算法根据页面调入内存后的使用情况来进行决策的，赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最佳（OPT）置换算法所选择的被淘汰的页面，将是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。常用函数：voidFIFO():计算使用FIFO算法时的命中率，voidLRU():计算使用LRU算法时的命中率，voidOPT():计算使用OPT算法时的命中率，inttotal_pf:用户进程的内存页面数，intdisaffect:页面失效次数.程序Main.cpp:#include<iostream>#include<string>#include<vector>#include<cstdlib>#include<cstdio>#include<unistd.h>usingnamespacestd;#defineINVALID-1constintTOTAL_INSTRUCTION(320);constintTOTAL_VP(32);constintCLEAR_PERIOD(50);#include"Page.h"#include"PageControl.h"#include"Memory.h"intmain(){inti; CMemorya; for(i=4;i<=32;i++) {a.FIFO(i); a.LRU(i); cout<<"\n"; } return0;}Memory.h:#ifndef_MEMORY_H#define_MEMORY_HclassCMemory{public: CMemory(); voidinitialize(constintnTotal_pf); voidFIFO(constintnTotal_pf);voidLRU(constintnTotal_pf);voidOPT(constintnTotal_pf);private: vector<CPage>_vDiscPages;//硬盘页面总数 vector<CPageControl>_vMemoryPages;//内存页面总数 CPageControl*_pFreepf_head,*_pBusypf_head,*_pBusypf_tail; vector<int>_vMain,_vPage,_vOffset; int_nDiseffect;//页面失效次数};CMemory::CMemory():_vDiscPages(TOTAL_VP),//硬盘共32个页面 _vMemoryPages(TOTAL_VP),//内存共32个页面 _vMain(TOTAL_INSTRUCTION),/*共320条指令,在320条指令有很多指令可能具有相同的页地址不同的偏移地址，所以共32个页面，每页10条指令（在硬盘上的）*/ _vPage(TOTAL_INSTRUCTION),//共320个页地址 _vOffset(TOTAL_INSTRUCTION)//共320个偏移地址{ inti,S,nRand; srand(getpid()*10); nRand=rand()%32767; S=(int)319*nRand/32767+1; for(i=0;i<TOTAL_INSTRUCTION;i+=4)//共320个 { _vMain[i]=S; _vMain[i+1]=_vMain[i]+1;//连着上一个顺序执行 nRand=rand()%32767; _vMain[i+2]=(int)_vMain[i]*nRand/32767; _vMain[i+3]=_vMain[i+2]+1;//连着上一个顺序执行 nRand=(int)rand()%32767; S=(int)nRand*(318-_vMain[i+2])/32767+_vMain[i+2]+2; } for(i=0;i<TOTAL_INSTRUCTION;i++)//共320个 { _vPage[i]=_vMain[i]/10; _vOffset[i]=_vMain[i]%10; _vPage[i]%=32; }}voidCMemory::initialize(constintnTotal_pf){ intix; _nDiseffect=0; for(ix=0;ix<_vDiscPages.size();ix++) { _vDiscPages[ix].m_nPageNumber=ix;//硬盘中的页号 _vDiscPages[ix].m_nPageFaceNumber=INVALID;//在没有调入内存时为-1 _vDiscPages[ix].m_nCounter=0; _vDiscPages[ix].m_nTime=-1; } for(ix=1;ix<nTotal_pf;ix++) { _vMemoryPages[ix-1].m_pNext=&_vMemoryPages[ix]; _vMemoryPages[ix-1].m_nPageFaceNumber=ix-1;/*内存页号，此时PageNumber没有赋值因为此时没有产生调用*/ } _vMemoryPages[nTotal_pf-1].m_pNext=NULL; _vMemoryPages[nTotal_pf-1].m_nPageFaceNumber=nTotal_pf-1; _pFreepf_head=&_vMemoryPages[0];}voidCMemory::FIFO(constintnTotal_pf){ inti; CPageControl*p; initialize(nTotal_pf); _pBusypf_head=_pBusypf_tail=NULL; for(i=0;i<TOTAL_INSTRUCTION;i++)//共320条指令连续调用 { if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)/*判断是否已在内存中,如果已在内存就什么都不做，如果不在内存就进行调入,每次调入一页*/ { _nDiseffect+=1;//不在内存就加1统计缺页次数 if(_pFreepf_head==NULL)/*无空闲页面，进行置换，找出忙队列的第一个置换出。*/ { p=_pBusypf_head->m_pNext; _vDiscPages[_pBusypf_head->m_nPageNumber].m_nPageFaceNumber=INVALID;//要置换出，所以置-1 _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=_vPage[i];_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber; if(_pBusypf_tail==NULL) _pBusypf_head=_pBusypf_tail=_pFreepf_head; else { _pBusypf_tail->m_pNext=_pFreepf_head; _pBusypf_tail=_pFreepf_head; } _pFreepf_head=p; } } cout<<"FIFO:"<<1-(float)_nDiseffect/320;}voidCMemory::LRU(constintnTotal_pf){inti,j,nMin,minj,nPresentTime(0);initialize(nTotal_pf);for(i=0;i<TOTAL_INSTRUCTION;i++){if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID) { _nDiseffect++; if(_pFreepf_head==NULL)//无空闲页面 { nMin=32767; for(j=0;j<TOTAL_VP;j++)//getthesubscribeoftheleastusedpage //aftertherecycleiMinisthenumberoftimes //usedoftheleastusedpagewhileminjisitssubscribe if(nMin>_vDiscPages[j].m_nTime&&_vDiscPages[j].m_nPageFaceNumber!=INVALID) { nMin=_vDiscPages[j].m_nTime; minj=j; }_pFreepf_head=&_vMemoryPages[_vDiscPages[minj].m_nPageFaceNumber]; _vDiscPages[minj].m_nPageFaceNumber=INVALID; _vDiscPages[minj].m_nTime=-1; _pFreepf_head->m_pNext=NULL; }_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber; _vDiscPages[_vPage[i]].m_nTime=nPresentTime; _pFreepf_head=_pFreepf_head->m_pNext; }else _vDiscPages[_vPage[i]].m_nTime=nPresentTime;nPresentTime++;}cout<<"LRU:"<<1-(float)_nDiseffect/320;}voidCMemory::OPT(constintnTotal_pf){inti,j,max,maxpage,nDistance,vDistance[TOTAL_VP];initialize(nTotal_pf);for(i=0;i<TOTAL_INSTRUCTION;i++){if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)//页面不在内存中 {_nDiseffect++; if(_pFreepf_head==NULL){//如果没有空闲页面找到最不经常用的那个，将其置换出 for(j=0;j<TOTAL_VP;j++)if(_vDiscPages[j].m_nPageFaceNumber!=INVALID)vDistance[j]=32767;/*如果在内存中*/ else vDistance[j]=0;//如果不在内存中nDistance=1;for(j=i+1;j<TOTAL_INSTRUCTION;j++){if((_vDiscPages[_vPage[j]].m_nPageFaceNumber!=INVALID)&&(vDistance[_vPage[j]]==32767))vDistance[_vPage[j]]=nDistance;nDistance++;}max=-1;for(j=0;j<TOTAL_VP;j++) if(max<vDistance[j]){max=vDistance[j];maxpage=j;}_pFreepf_head=&_vMemoryPages[_vDiscPages[maxpage].m_nPageFaceNumber];_pFreepf_head->m_pNext=NULL;_vDiscPages[maxpage].m_nPageFaceNumber=INVALID;}//如果在有空闲页面或者最不经常用的已经置换出，把空队列的头指向的页面_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_pFreepf_head=_pFreepf_head->m_pNext;}}cout<<"OPT:"<<1-(float)_nDiseffect/320;}#endif#endif磁盘页面结构：Page.h:#ifndef_PAGE_H#define_PAGE_HclassCPage{public: intm_nPageNumber,//磁盘上的页号 m_nPageFaceNumber,//内存中的页号 m_nCounter, m_nTime;};#endif内存页面结构：PageControl.h:#ifndef_PAGECONTROL_H#define_PAGECONTROL_HclassCPageControl{public: intm_nPageNumber,m_nPageFaceNumber; classCPageControl*m_pNext;};#endif实验结果与分析：实验结果：FIFO:0.534375LRU:0.534375OPT:0.6375FIFO:0.55LRU:0.546875OPT:0.6625FIFO:0.56875LRU:0.559375OPT:0.6875FIFO:0.571875LRU:0.56875OPT:0.709375FIFO:0.590625LRU:0.58125OPT:0.73125FIFO:0.6125LRU:0.6OPT:0.75FIFO:0.628125LRU:0.6125OPT:0.765625FIFO:0.646875LRU:0.640625OPT:0.78125FIFO:0.659375LRU:0.66875OPT:0.796875FIFO:0.675LRU:0.68125OPT:0.809375FIFO:0.70625LRU:0.690625OPT:0.821875FIFO:0.721875LRU:0.709375OPT:0.834375FIFO:0.7375LRU:0.73125OPT:0.84375FIFO:0.753125LRU:0.746875OPT:0.853125FIFO:0.7625LRU:0.7625OPT:0.859375FIFO:0.765625LRU:0.784375OPT:0.865625FIFO:0.778125LRU:0.803125OPT:0.871875FIFO:0.79375LRU:0.803125OPT:0.875FIFO:0.815625LRU:0.815625OPT:0.878125FIFO:0.815625LRU:0.834375OPT:0.88125FIFO:0.834375LRU:0.840625OPT:0.884375FIFO:0.859375LRU:0.85OPT:0.8875FIFO:0.865625LRU:0.8625OPT:0.890625FIFO:0.86875LRU:0.875OPT:0.89375FIFO:0.86875LRU:0.890625OPT:0.896875FIFO:0.875LRU:0.89375OPT:0.9FIFO:0.88125LRU:0.896875OPT:0.9FIFO:0.884375LRU:0.896875OPT:0.9FIFO:0.9LRU:0.9OPT:0.9结果分析：理论上，三种置换算法的命中率由高到底排列应该是OPT>LRU>FIFO。实际上，从实验数据观测得到，存在这种由高到低的趋势，由page=4时可以观测到，但是效果不是很明显。效果不明显的原因：推测与指令流的产生方式有关系。因为指令流的产生方式要能体现局部性原理，所以该指令流产生设计为：50%的指令是顺序执的，25