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

操作系统课程设计操作系统课程设计请求页式存储管理 学院： 学号：姓名：辅导老师：设计四：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)；最少访问页面算法 (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页面置换算法原理算述当分配内存页面数(AP)小于进程页面数(PP)时，当然是把最先执行的AP个页面放入内存。当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面(称为LRU)。算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。LFU即最不经常使用页置换算法1 原理简述要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。LRU算法的硬件支持把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：1.一个进程在内存中的各个页面各有多久时间未被进程访问；2.如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：（1）寄存器用于记录某进程在内存中各页的使用情况。实页/RR7R6R5R4R3R2R1R0101010010210101100300O001004011010115110101106001 01011700000111801101101（2）栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。算法特点:LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10000次是等效的。 NUR页面置换算法原理简述所谓“最近未使用”，首先是要对“近”作一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面。那么可能会有以下几种情况：如果这样的页面只有一个，就将其换出，放入需要处理的新页面。如果有这样的页面不止一个，就在这些页面中任取一个换出(可以是下标最小的，或者是下标最大的)，放入需要处理的页面。如果没有一个这样的页面，就随意换出一个页面(可以是下标最小的，或者是下标最大的)。算法特点：有一个循环周期，每到达这个周期，所有页面存放是否被CPU处理的信息的属性均被置于初始态(没有被访问)。6实验流程图 开 始生成地址流输入算法号S1S4形成地址页号用户内存空间msize=2Msize32 OPT()FIFO()LRU()LFU()Msize加1S=? 是否用其他算法继续结 束NY1234YN提示出错，重新输入7. 实验运行结果等等。8. 实验源程序#include#includeusing namespace std;const int MaxNum=320;/指令数const int M=5;/内存容量int PageOrderMaxNum;/页面请求int SimulateMaxNumM;/页面访问过程int PageCountM,LackNum;/PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数float PageRate;/命中率int PageCount132;bool IsExit(int i)/FIFO算法中判断新的页面请求是否在内存中 bool f=false; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi)/在前一次页面请求过程中寻找是否存在新的页面请求 f=true; return f;int IsExitLRU(int i)/LRU算法中判断新的页面请求是否在内存中int f=-1; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi) f=j; return f;int Compare()/LRU算法找出内存中需要置换出来的页面int p,q;p=PageCount0;q=0; for(int i=1;iM;i+)if(pPageCounti)p=PageCounti;q=i;return q;void Init() /初始化页框for(int k=0;kMaxNum;k+)int n=rand()%320;/随机数产生320次指令PageOrderk=n/10;/根据指令产生320次页面请求 for(int i=0;iMaxNum;i+)/初始化页面访问过程 for(int j=0;jM;j+) Simulateij=-1; for(int q=0;qM;q+)/初始化最久未使用数组 PageCountq=0;void OutPut()/输出int i,j;cout页面访问序列:endl;for(j=0;jMaxNum;j+)coutPageOrderj ;coutendl;cout页面访问过程(只显示前10个):endl;for(i=0;i10;i+)for(j=0;jM;j+)if(Simulateij=-1)cout ;elsecoutSimulateij ;coutendl;cout缺页数= LackNumendl;cout命中率= PageRateendl;cout-endl;void FIFO()/FIFO算法int j,x=0,y=0;LackNum=0,Init(); for(j=0;jM;j+)/将前五个页面请求直接放入内存中for(int k=0;k=j;k+)if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k; /LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;if(!IsExit(x)/根据新访问页面是否存在内存中来更新页面访问过程LackNum+;Simulatexy%M=PageOrderx;y+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();void LRU()/LRU算法int j,x=0,y=0;LackNum=0,Init(); for(j=0;jM;j+)/将前五个页面请求直接放入内存中for(int k=0;k=j;k+)PageCountk+;if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k; LackNum+; for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/根据反回的p值来更新页面访问过程int k;k=Compare();for(int w=0;wM;w+)if(w!=k)PageCountw+;elsePageCountk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();/最近最不常用调度算法(LFU)void LFU()void NUR()void YourChoice(int choice)switch(choice)case 1:cout-endl;coutFIFO算法结果如下：endl;FIFO();break;case 2:cout-endl;coutLRU算法结果如下：endl;LRU();break;case 3:cout-endl;coutLFU算法结果如下：endl; /LFU();break;case 4:cout-endl;coutNUR算法结果如下：endl;/NUR();break;case 5:break;default:cout重新选择算法：1-FIFO 2-LRU 3-LFU 4-NUR 5-退出 choice;YourChoice(choice);void main()int choice,i=1;while(i)cout请选择算法：1-FIFO 2-LRU 3-LFU 4-NUR 5-退出 choice;if(choice