《实验五 虚拟内存页面置换算法.doc》由会员分享，可在线阅读，更多相关《实验五 虚拟内存页面置换算法.doc（20页珍藏版）》请在金锄头文库上搜索。
1、实验五 虚拟内存页面置换算法一、 需求分析11.输入的形式和输入值的范围22.输出的形式23.程序所能达到的功能34.测试数据4二、 概要设计51.抽象数据类型的定义52.主程序的流程63.程序各模块之间的层次(调用)关系7三、 详细设计71.void FIFO()72.void OPI()83.void LRU()10四、 调试分析111.发现的问题112.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；113.解决方法114.经验和体会12五、用户使用说明12六、测试结果12七附录14一、 需求分析l 需求在进程运行过程中，若其所访问的页面不在内存而需把
2、它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的更好频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不再访问的页面调出。l 实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。l 实验内容设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置
3、换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。l 程序要求1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。3）输入：最小物理块数m，页面个数n，页面访问序列P1, ,Pn，算法选择1-FIFO，2-OPI，3-LRU。4）输出：每种算法的缺页次数和缺页率。1.输入的形式和输入值的范围从dos控
4、制台界面按照输入提示输入数据（红色的数字即为输入的内容）：物理块(LackNum)：3页号数（PageNum）：20页面序列(PageOrder)：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1进程的最大页号数为100，物理块、页面序列的值为int类型的范围。2.输出的形式输入数据后，按ENTER键就可在dos控制台界面得到结果。按照实验要求分别输出程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。结果如下：首行是算法的名称，第二行是页号序列，接下来的3行数字是模仿物理块的情况，竖着看才是正确的结果，此图显示的是3块物理块时内
5、存占用情况。之后显示缺页次数和缺页率。3.程序所能达到的功能程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。4.测试数据二、 概要设计1.抽象数据类型的定义 程序中进程调度时间变量描述如下： const int MaxNumber=100; int PageOrderMaxNumber; int SimulateMaxNumberMaxNu
6、mber;int PageCountMaxNumber;int PageNum,LackNum;double LackPageRate;bool found;主要函数：void print();void init();void original();void FIFO();void OPI();void LRU();2.主程序的流程 3.程序各模块之间的层次(调用)关系三、 详细设计1.void FIFO()original();Simulate00=PageOrder0;int temp=0,flag=0;for(i=1;iPageNum;i+) /判断该页面是否存在内存中for(j=0;j
7、BlockNum;j+)if(PageOrderi=Simulateflagj)break; if(j=BlockNum)/该页面不在内存中for(k=0;kBlockNum;k+)/模拟置换过程 if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/淘汰最先进入内存的页面temp+;temp=temp%BlockNum;Simulateitemp=PageOrderi;LackNum+;flag=i;/该页面在内存中elsecontinue;2.void OPI()original();Simulate00=PageOrde
8、r0;int temp,flag=0;/flag表示上一个模拟内存的下标for(i=1;iPageNum;i+) /判断该页面是否存在内存中for(j=0;jBlockNum;j+)if(PageOrderi=Simulateflagj)break; /j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;/模拟置换过程for(k=0;kBlockNum;k+) if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/内存中页面进行选择/两种情况：内存已满和内存未满for(j=0;jBloc
9、kNum;j+)if(Simulateij=NULL)Simulateij=PageOrderi;LackNum+; flag=i;break;if(j!=BlockNum)/内存未满continue;/内存已满temp=0;/temp表示要置换的页面内存下标 for(j=0;jBlockNum;j+)/选取要置换的页面内存下标for(k=i+1;kPageNum;k+)/最长时间内不被访问的页面 if(Simulateij=PageOrderk) PageCountj=k;break; if(k=PageNum)/之后没有进行对该页面的访问PageCountj=PageNum;if(Page
10、CounttempPageCountj)temp=j;Simulateitemp=PageOrderi;LackNum+;flag=i; 3.void LRU()original();Simulate00=PageOrder0;int temp,flag=0;/flag表示上一个模拟内存的下标PageCount0=0;/最近的页面下标for(i=1;iPageNum;i+) /判断该页面是否存在内存中for(j=0;jBlockNum;j+)if(PageOrderi=Simulateflagj)PageCountj=i;break; /j!=BlockNum表示该页面已经在内存中if(j!=
11、BlockNum)continue;/模拟置换过程for(k=0;kBlockNum;k+) if(Simulateflagk=NULL) break; else Simulateik=Simulateflagk;/内存中页面进行选择/两种情况：内存已满和内存未满for(j=0;jBlockNum;j+)if(Simulateij=NULL)/内存未满Simulateij=PageOrderi;PageCountj=i;LackNum+; flag=i;break;if(j!=BlockNum)continue;/内存已满temp=0;/temp表示要置换的页面内存下标 for(j=0;jPa
12、geCountj)temp=j; Simulateitemp=PageOrderi;PageCounttemp=i;LackNum+;flag=i;四、 调试分析1.发现的问题在编写程序的最初，界面不是很好，看着很乱。最后求的缺页率也不是用百分数表示。2.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；该程序的的时间复杂度还算理想，是O(m*n),空间复杂度也是一样，复杂度为O(m*n),均不需要再改进了。 3.解决方法界面使用空格填充，使各行各列对齐。对于输出百分数，将缺页率乘以100，后加%输出。4.经验和体会通过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最佳（OPI）置换算法，最近最久未使用（LRU）置换
