操作系统课程设计--请求页式存储管理

操作系统课程设计1操作系统课程设计请求页式存储管理学院：学号：姓名：辅导老师：操作系统课程设计2设计四：1.设计目的请求页式管理是一种常用的虚拟存储管理技术。本设计通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。2.设计内容：通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分。具体的实施方法是：①在[0,319]的指令地址之间随机选取一起点m；②顺序执行一条指令；③在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m′；④顺序执行一条指令，其地址为m′+1；⑤在后地址[m′+2,319]中随机选取一条指令并执行；⑥重复上述步骤②~⑤，直到执行320次指令。将指令序列变换成为页地址流设：①页面大小为1K；②用户内存容量为4页到32页；③用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页(对应虚存地址为[0,9])；第10条~第19条指令为第1页(对应虚存地址为[10,19])；┇┇第310条~第319条指令为第31页(对应虚存地址为[310,319])。按以上方式，用户指令可组成32页。计算并输出下述各种算法在不同内存容量下的命中率。先进先出的算法(FIFO)；最近最少使用算法(LRR)；操作系统课程设计3最少访问页面算法(LFR)；最近最不经常使用算法(NUR)。3．实验环境每个学生一台微机，需要安装windows98或windows2000操作系统，配备VC、VB、java或C编程语言，每个学生上机时间不少于24个小时。（1）、分页请求系统为了能实现请求调页和置换功能，系统必须提供必要的硬件支持，其中，最重要的是：（1）请求分页的页表机制。它是在分页的页表机制上增加若干个项而形成的，作为请求分页的数据结构；（2）缺页中断机构。每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页面调入内存；（3）地址变换机构。它同样是在分页的地址变换机构的基础上发展形成的。为了实现请求调页还须得到OS的支持，在实现请求调页功能时，石油OS将所需的页从外存调入内存；在实现置换功能时，也是由OS将内存的某些页调至外存。4．实验提示提示：A.命中率=1-页面失效次数/页地址流长度B.本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。C.关于随机数产生方法，采用TC系统提供函数RAND()和RANDOMIZE()来产生。5.自己对算法的理解㈠FIFO页面置换算法⑴原理简述①在分配内存页面数(AP)小于进程页面数(PP)时，当然是最先运行的AP个页面放入内存。②这时有需要处理新的页面，则将原来内存中的AP个页面最先进入的调出(是以称为FIFO)，然后将新页面放入。③以后如果再有新页面需要调入，则都按⑵的规则进行。算法特点：所使用的内存页面构成一个队列。㈡LRU页面置换算法⑴原理算述操作系统课程设计4①当分配内存页面数(AP)小于进程页面数(PP)时，当然是把最先执行的AP个页面放入内存。②当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面(称为LRU)。算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。㈢LFU即最不经常使用页置换算法⑴原理简述要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。LRU算法的硬件支持把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：1.一个进程在内存中的各个页面各有多久时间未被进程访问；2.如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：（1）寄存器用于记录某进程在内存中各页的使用情况。实页/RR7R6R5R4R3R2R1R0101010010210101100300O00100401101011511010110600101011700000111801101101（2）栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。算法特点:LFU算法并不能真正反映出页面的使用情况，因为在每一时间操作系统课程设计5间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10000次是等效的。㈣NUR页面置换算法⑴原理简述所谓“最近未使用”，首先是要对“近”作一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面。那么可能会有以下几种情况：①如果这样的页面只有一个，就将其换出，放入需要处理的新页面。②如果有这样的页面不止一个，就在这些页面中任取一个换出(可以是下标最小的，或者是下标最大的)，放入需要处理的页面。③如果没有一个这样的页面，就随意换出一个页面(可以是下标最小的，或者是下标最大的)。算法特点：有一个循环周期，每到达这个周期，所有页面存放是否被CPU处理的信息的属性均被置于初始态(没有被访问)。6．实验流程图操作系统课程设计67.实验运行结果开始生成地址流输入算法号S1≤S≤4形成地址页号用户内存空间msize=2Msize≤32OPT()FIFO()LRU()LFU()Msize加1S=?是否用其他算法继续结束NY1234YN提示出错，重新输入操作系统课程设计7操作系统课程设计8等等。8.实验源程序#includeiostream#includetime.husingnamespacestd;constintMaxNum=320;//指令数constintM=5;//内存容量intPageOrder[MaxNum];//页面请求intSimulate[MaxNum][M];//页面访问过程intPageCount[M],LackNum;//PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数floatPageRate;//命中率intPageCount1[32];boolIsExit(inti)//FIFO算法中判断新的页面请求是否在内存中{boolf=false;for(intj=0;jM;j++){操作系统课程设计9if(Simulate[i-1][j]==PageOrder[i])//在前一次页面请求过程中寻找是否存在新的页面请求{f=true;}}returnf;}intIsExitLRU(inti)//LRU算法中判断新的页面请求是否在内存中{intf=-1;for(intj=0;jM;j++){if(Simulate[i-1][j]==PageOrder[i]){f=j;}}returnf;}intCompare()//LRU算法找出内存中需要置换出来的页面{intp,q;p=PageCount[0];q=0;for(inti=1;iM;i++){操作系统课程设计10if(pPageCount[i]){p=PageCount[i];q=i;}}returnq;}voidInit()//初始化页框{for(intk=0;kMaxNum;k++){intn=rand()%320;//随机数产生320次指令PageOrder[k]=n/10;//根据指令产生320次页面请求}for(inti=0;iMaxNum;i++)//初始化页面访问过程{for(intj=0;jM;j++){Simulate[i][j]=-1;}}for(intq=0;qM;q++)//初始化最久未使用数组{PageCount[q]=0;}操作系统课程设计11}voidOutPut()//输出{inti,j;cout页面访问序列:endl;for(j=0;jMaxNum;j++){coutPageOrder[j];}coutendl;cout页面访问过程(只显示前10个):endl;for(i=0;i10;i++){for(j=0;jM;j++){if(Simulate[i][j]==-1)cout;elsecoutSimulate[i][j];}coutendl;}cout缺页数=LackNumendl;cout命中率=PageRateendl;cout--------------------------------------------------------------endl;}操作系统课程设计12voidFIFO()//FIFO算法{intj,x=0,y=0;LackNum=0,Init();for(j=0;jM;j++)//将前五个页面请求直接放入内存中{for(intk=0;k=j;k++){if(j==k)Simulate[j][k]=PageOrder[j];elseSimulate[j][k]=Simulate[j-1][k];}//LackNum++;}for(x=M;xMaxNum;x++){for(intt=0;tM;t++)//先将前一次页面访问过程赋值给新的页面访问过程{Simulate[x][t]=Simulate[x-1][t];}if(!IsExit(x))//根据新访问页面是否存在内存中来更新页面访问过程{LackNum++;Simulate[x][y%M]=PageOrder[x];操作系统课程设计13y++;}}PageRate=1-((float)LackNum/(float)MaxNum);//算出命中率OutPut();}voidLRU()//LRU算法{intj,x=0,y=0;LackNum=0,Init();for(j=0;jM;j++)//将前五个页面请求直接放入内存中{for(intk=0;k=j;k++){PageCount[k]++;if(j==k)Simulate[j][k]=PageOrder[j];elseSimulate[j][k]=Simulate[j-1][k];}LackNum++;}for(x=M;xMaxNum;x++){for(intt=0;tM;t++)//先将前一次页面访问过程赋值给新的页面访问过程{操作系统课程设计14Simulate[x][t]=Simulate[x-1][t];}intp=IsExitLRU(x);if(p==-1)//根据反回的p值来更新页面访问过程{intk;k=Compare();for(intw=0;wM;w++){if(w!=k)PageCount[w]++;elsePageCount[k]=1;}Simulate[x][k]=PageOrder[x];LackNum++;}else{for(intw=0;wM;w++){if(w!=p)PageCount[w]++;elsePageCount[p]=1;}}}操作系统课程设计15PageRate=1-((float)LackNum/(float)MaxNum);//算出命中率OutPut();}//最近最不常用调度算法(LFU)voidLFU(){}voidNUR(){}voidYourChoice(intchoice){switch(choice){case1:cout----------------------------------------------------------endl;coutFIFO算法结果如下：endl;FIFO();b