虚拟存储器管理方案实验报告

^`淮海工学院计算机科学系实验报告书课程名：《操作系统》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日^`一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。二、实验说明1．设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。pnpfntime虚页结构实页结构在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。2．关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。3．LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前pnpfnnext^`countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。4．算法中实页的组织因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图三个模块的流程图〈1〉登录模块开始打开w_input窗口关闭w_main窗口^`〈2〉参数输入模块〈3〉算法实现模块开始打开w_input窗口关闭w_accept窗口调用FCFS算法显示结果调用SSTF算法显示结果调用SCAN算法显示结果调用CSCAN算法显示结果开始打开w_accept窗口关闭w_input窗口输入当前磁头位置输入各磁道号位置^`四、主要程序清单模块之间的调用关系#includestdio.h#includestdlib.h#includetime.hintproducerand(intremainder);voidinitprocess();voidchosedisplace();structlinknode*fifo(structlinknode*head,intrandcount);voidOptimal(structlinknode*head,intrandprocess);structlinknode*LRU(structlinknode*head,intrandprocess);structlinknode*initlink();voidchoicestey();intallotment(structlinknode*head);boolcheckfifooptimal(structlinknode*head,intcheckpage);voidrecover(structlinknode*head,intrandprocess);voidrecovermemory();intprocess[10][20];//数组的横坐标为进程序列，纵坐标为每个进程的页号intprocessallotment[6];//存储每个进程已经分配的块数intfinishp[6];//标志进程是否完成（1完成0不完成）intfinishprocess=0;//进程完成的个数intfindpage[6];//每个进程命中的个数structlinknode*plinkhead[6];structlinknode*plink[6];登录模块参数输入模块算法实现模块^`intmemoryallotment[6];intstey=0;structlinknode{structlinknode*linkper;//空链表的前驱指针intpage;intprocesspage;intused;intmemorypage;structlinknode*linknext;//空链表的后继指针structlinknode*processper;//进程的前去指针structlinknode*processnext;//进程的后继指针};intmain(){structlinknode*head=initlink();initprocess();choicestey();intre=allotment(head);if(re==0){printf(内存分配出现问题。);system(pause);}chosedisplace();recovermemory();system(pause);}voidrecovermemory(){^`intn=0;printf(是否回收全部已分配的内存空间?\n回收输入1，不回收输入2\n);scanf(%d,&n);if(n==1){for(inti=1;i=5;i++)recover(plinkhead[i],i);}if(n==2)printf(您这么做会浪费内存空间);}voidrecover(structlinknode*head,intrandprocess){while(head!=0){head-used=0;head=head-processnext;}}voidchoicestey(){printf(请选择置换算法\n);printf(1表示FIFO\n2表示Optimal\n3表示LRU\n);boolflag=true;while(flag){^`scanf(%d,&stey);switch(stey){case1:{printf(您选择的是FIFO替换算法\n);flag=false;break;}case2:{printf(您选择的是Optimal替换算法\n);flag=false;break;}case3:{printf(您选择的是LRU替换算法\n);flag=false;break;}default:printf(输入错误，请重新输入\n);}}}voidchosedisplace()//选择置换算法{structlinknode*head;intrandcount;//进程序号boolfind;while(finishprocess5){randcount=producerand(5);while(processallotment[randcount]process[randcount][0]){find=false;head=plinkhead[randcount];if(stey==1||stey==2)find=checkfifooptimal(head,process[randcount][processallotment[randcount]+1]);if(find==true){^`findpage[randcount]++;}if(find==false)//如果在链表中没找到当前的页数{switch(stey){case1:{plinkhead[randcount]=fifo(plinkhead[randcount],randcount);break;}case2:{Optimal(plinkhead[randcount],randcount);break;}case3:{plinkhead[randcount]=LRU(plinkhead[randcount],randcount);break;}}}processallotment[randcount]++;}if(finishp[randcount]==0){finishprocess++;finishp[randcount]=1;^`}}structlinknode*p;printf(进程执行完后内存分配情况：\n);for(inti=1;i=5;i++){p=plinkhead[i];while(p!=0){printf(内存块号：%d\t进程号：%d\t号：%d\n,p-memorypage,p-processpage,p-page);p=p-processnext;}}for(inti=1;i=5;i++){printf(进程序列%d,i);printf(\t进程总页数为%d\t命中页为%d\t,process[i][0],findpage[i]);printf(进程的命中率为%.0f%%\n,((float)findpage[i])*100/process[i][0]);}}boolcheckfifooptimal(structlinknode*head,intcheckpage){while(head!=0)//遍历链表查单当前页是否在链表中{if(head-page==checkpage){returntrue;^`}else{head=head-processnext;}}returnfalse;}structlinknode*LRU(structlinknode*head,intrandprocess){structlinknode*bhead;bhead=head;while(head-processnext!=0){if(head-page==process[randprocess][processallotment[randprocess]+1])break;elsehead=head-processnext;}if(head-page!=process[randprocess][processallotment[randprocess]+1])//没找到{bhead-page=process[randprocess][processallotment[randprocess]+1];head-processnext=bhead;bhead-processper=head;bhe