页面淘汰算法课程设计.doc

操作系统课程设计报告一、 课程设计题目：页面淘汰算法实现二、 基本要求：l 设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响l 编写页面淘汰算法(FIFO、OPT、LRU)l 结果数据的显示或提取l 结果数据的分析 几点说明：l 设计并绘制算法流程，附加说明所需的数据结构l 如何标记时间的先后、最久的将来、最久未被使用三、算法描述：（1）先进先出页面置换算法（FIFO）（2）最佳置换算法（OPT）（3）最近最久未使用置换算法（LRU）四、 总体设计l 根据要求设计页面淘汰算法的活动图 运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0，退出程序。l 算法流程图 FIFO算法流程图： OPT算法流程图 LRU算法流程图：五、详细设计首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#define MemPageCount 4 #define InstructionCount 20 struct page int serial; /页面号 int time; /时间计数mempageMemPageCount; 其次，建立主函数，根据程序需要，定义相应的变量，建立switch语句，用以算法的选择，部分定义如下：int i,j,k,m,n;/指令页面集合,可以考虑让页面指令集合随机生成int instructionInstructionCount;int mem_counter; /内存页面集合计数器int switch_counter; /置换次数 最后，根据算法流程图，实现相应算法的代码编写。五、 结果分析：物理块数为3、页面数目为20：物理块数为4、页面数目为20：根据结果，我们不难发现，OPT算法，是三种算法中性能最好的，它的置换次数最少，LRU次之，不过性能最差的还是FIFO，由于缺页率=缺页次数/总的页面数，所以我们不难发现，随着物理块数的增加，缺页率都相应有所增加，但是OPT算法的增加较为明显，即产生了belady现象。六、 课程设计总结： 通过本次课程设计，让我对页面淘汰算法有了充分的了解，我不仅对我们常用的算法进行了编写，还对一些理想的算法也进行了编写，并且通过适当的方法，得以了验证。就该程序而言，随机性使得程序出现了更多的可能性，为我们验证算法提供很大的方便，电脑自动分配，大大的节约了我们的时间，但是我们通过实验不难发现，如果所设的页面项目过大，也会影响我们算法的性能执行效率。对我们所涉及的算法，让我有很大的感触。在FIFO 算法中，无论有无发生缺页或者置换，都需要对每个在内存中的页面的time 值进行增加操作，以保持最先进入的那个页面的time 值是最大的；一个新进来的页面，其time值设置为0。当然，该算法也可以通过队列结构来实现，利用队列的先进先出（FIFO）特性完成，无需设置time字段。distance 用于记录内存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为9999，如果某个页面在后续指令集合中不再出现，则用最大值9999 缺省取代；如果页面再次被使用，则两次使用所跨的页面数，为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。在LRU 算法中，无论是否发生缺页或者置换，除了命中（刚刚被访问过的页面）页面time 值清零之外，其它所有内存中的页面的time 值都加一，以保证最近刚刚被访问的页面的time 值最小，相应time 值最大的页面就是最近最久没有被访问的页面。上述两种算法，是我们在进程调度中使用最多的两种，你可能会问？为什么要使用进程调度，因为当我们的程序在运行时，若所访问的页面不再内存而需把它调入内存，但内存已无空闲空间，这时，为了保证该程序能正常运行，系统就必须从内存中调出一页程序或数据送到磁盘的兑换区中，但应将那个页面调出，我们就必须根据一定的算法来实现。所以，一个页面置换算法的好坏，将直接影响到我们系统的性能。相比较而言，我们最常用的是LRU算法，因为它是根据页面调入内存后的使用情况就行决策的，比FIFO算法要好很多。 这次课程设计，让我对算法的编写更加的熟练，同时更加了解页面置换的相关算法，也提高了我对算法设计的严密性，对以后的程序设计有很大帮助。实验代码如下：#include#include#include#define MemPageCount 4 /内存物理块数目#define InstructionCount 20 /指令页面数目struct pageint serial; /页面号int time; /时间计数mempageMemPageCount;int main()int i,j,k,m,n;/指令页面集合,可以考虑让页面指令集合随机生成int instructionInstructionCount;int mem_counter; /内存页面集合计数器int switch_counter; /置换次数int switch_flag; /置换的位置标志int lost_counter; /缺页次数int exist_flag; /判断是否已经在内存中的标志int distanceMemPageCount;/用于标记内存中已有页面哪个是最久的将来不使用的srand(time(NULL); /*time(NULL)是得到当前时间，srand()是取一个种子好生成随机数*/for(n=0;nInstructionCount;n+)instructionn=rand()%10;printf(当前随机生成的页面号为:n);for(n=0;nInstructionCount;n+)printf( %d,instructionn);printf(n);dolost_counter=0;switch_counter=0;mem_counter=0;switch_counter=0;lost_counter=0;switch_flag=0;exist_flag=0;printf(n请选择算法: 0、结束 1、FIFO算法 2、OPT算法 3、LRU算法:);scanf(%d,&m);printf(置换顺序依次为:n);switch(m)case 1:for(i=0;iMemPageCount;i+) /内存页面集合,初始化为-1mempagei.serial=-1;mempagei.time=0;/依次调入新的指令页面，如果内存页面满且新页面不存在，则置换页面for(i=0;iInstructionCount;i+)for(j=0;jMemPageCount;j+) /判断是否已在内存中if(mempagej.serial=instructioni)exist_flag=1;break;/如果内存中没有该页面，执行缺页和置换步骤if(exist_flag!=1)/内存页面集合未满,缺页不置换if(mem_counterMemPageCount)mempagemem_counter.serial=instructioni;mempagemem_counter.time=0;mem_counter=mem_counter+1;else /缺页且发生置换switch_flag=0;/取得最先进入的页面在memepage中的位置for(j=1;jmem_counter;j+)if(mempageswitch_flag.timemempagej.time)switch_flag=j;mempageswitch_flag.serial=instructioni; /置换页面mempageswitch_flag.time=0;switch_counter=switch_counter+1;lost_counter=lost_counter+1;for(j=0;jmem_counter;j+) /打印mempage的情况printf(%d ,mempagej.serial);printf(| ); /end if(exist_flag!=1)for(j=0;jmem_counter;j+) /所有页面时间加一mempagej.time=mempagej.time+1;exist_flag=0;printf(n缺页次数：%d 次、,lost_counter);printf(置换次数：%d 次n,switch_counter);break;case 2:for(i=0;iMemPageCount;i+) /内存页面集合,初始化为-1mempagei.serial=-1;mempagei.time=0;/依次调入新的指令页面，如果内存页面满且新页面不存在，则置换页面for(i=0;iInstructionCount;i+)for(j=0;jmem_counter;j+) /判断是否已在内存中if(mempagej.serial=instructioni)exist_flag=1;break;if(exist_flag!=1) /如果内存中没有该页面，执行缺页和置换步骤if(mem_counterMemPageCount) /内存页面集合未满,缺页不置换mempagemem_counter.serial=instructioni;mempagemem_counter.time=0;mem_counter=mem_counter+1;else /缺页且发生置换for(j=0;jMemPageCount;j+) /初始化距离为最大值distancej=9999;for(j=0;jMemPageCount;j+)/记录下内存页面中，再次被使用的距离for(k=i+1;kInstructionCount;k+)if(instructionk=mempagej.serial)distancej=k;break;switch_flag=0;/寻找未来最长时间内不被使用的页面在mempage中的位置/即寻找distance最大值for(k=1;kMemPageCount;k+)if(distanceswitch_flagdistancek)switch_flag=k;mempageswitch_flag.serial=instructioni;switch_counter=switch_counter+1;lost_counter=lost_counter+1;for(j=0;jmem_counter;j+) /打印mempage的情况printf(%d ,mempagej.serial);printf(| );/if(exist_flag!=1)exist_flag=0;printf(n缺页次数：%d 次、,lost_counter);printf(置换次数：%d 次n,switch_counter);break;case 3:for(i=0;iMemPageCount;i+) /内存页面集合,初始化为-1mempagei.serial=-1;mempagei.time=0;/依次调入新的指令页面，如果内存页面满且新页面不存在，则置换页面for(i=0;iInstructionCount;i+)for(j=0;jmem_counter;j+) /判断是否已在内存中if(mempagej.serial=instructioni)exist_flag=1;mempagej.time=0; /如果在内存中，time 值置为零，表示刚刚被使用过break;if(exist_flag!=1) /如果内存中没有该页面，执行缺页和置换步骤if(mem_counterMemPageCount) /内存页面集合未满,缺页不置换mempagemem_counter.serial=instructioni;mempagemem_counter.time=0;mem_counter=mem_counter+1;else /缺页且发生置换switch_flag=0;for(j=1;jmem_counter;j+) /取得最久未被使用的页面在mempage中的位置if(mempageswitch_flag.timemempagej.time)switch_flag=j;mempageswitch_flag.serial=instructioni;mempageswitch_flag.time=0;switch_counter=switch_counter+1;lost_counter=l